0.前言
又是爆炸的一场
T1 只因数分解
出题人树脂666 是不是香菜逢仁鸡
成分过于复杂
题意：输入一个数\(n\) 分解一个\(m\)
定义只因数为 \(x\) 为 \(n!\) 的因数
构造一种方案 使得质因数小于等于\(n\)
思考：要知道的是\(m\leq n!\)
所以我们不妨考虑\(m\)拆成几个数 倒过来思考 就是阶乘进制
每一位都是\(n*(n-1)*(n-2)…(n-k)*a_k\)
因为\(a_k \leq n\) 所以这肯定是一个正确拆分
然后暴拆即可
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int g,sum[25],l;
ll n,m,ans,t;
ll q[25];
int main()
{
scanf("%d",&g);
while(g--)
{
scanf("%lld%lld",&n,&m);
l=0;
while(m)
{
ll t=1;
for(ll i=n;i>=1;i--)
if(t*i<=m) t*=i;
q[++l]=t;
m-=t;
}
printf("%d\n",l);
for(int i=1;i<=l;i++)
printf("%lld ",q[i]);
printf("\n");
}
return 0;
}
T2 宇宙射线 原题
老逼灯题目
Subtask1
太简单了 直接\(O(n!)\)枚举集合\(O(nm)\)判断即可 时间复杂度\(O(nm*n!)\)
Subtask2
看见\(n\)十分的小 因为当前面的数取定了 后面的数取到的数就是固定的
考虑 装压DP
定义 \(f[i]\) 表示\(i\)拆分二进制后对应位上都有的最优解 每次更新情况 \(O(n)\)转移
时间复杂度\(O(2^nn)\)
Code
#include<bits/stdc++.h>
#define N 605
#define ll long long
using namespace std;
ll mod=998244353;
ll pow2[N],f[(1<<20)+5],vis[(1<<20)+5];
int n,m,a[N],op[N][N];
int main()
{
scanf("%d%d",&n,&m);
pow2[0]=1;
for(int i=1;i<=n;i++)
pow2[i]=pow2[i-1]*2;
for(int i=1;i<=m;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
op[a[i]+i-1][0]=1;
for(int j=1;j<=n;j++)
scanf("%d",&op[a[i]+i-1][j]);
}
vis[0]=1;
for(int i=0;i<(1<<n);i++)
{
if(!vis[i]) continue;
int s=0,t=i;
for(int j=1;j<=n;j++)
if(i&(1<<j-1)) s++;
if(op[s][0])
{
for(int j=1;j<=n;j++)
if(!(i&(1<<op[s][j]-1)))
{
t|=(1<<op[s][j]-1);
break;
}
}
for(int j=1;j<=n;j++)
if(!(t&(1<<j-1)))
{
f[t|(1<<j-1)]=max(f[t|(1<<j-1)],f[i]+pow2[n-j]);
vis[t|(1<<j-1)]=1;
}
}
cout<<f[(1<<n)-1]%mod;
return 0;
}
50pts到手
Subtask3
考虑贪心。
因为 \(2^n>2^{n-1}+2^{n-2}+2^{n-3}+…2^0\)
因此 能拿前面的必须拿前面的
考虑枚举每个状态能不能拿 把能拿的所有东西丢进集合\(S\)里面
我们可以发现 每次拿可以检查一次：
- 从左扫一遍\(1\to m\)射线
- 如果当前实验不输入\(S\) 而且没有做过 那么可以直接让宇宙射线轰了这个实验
- 否则如果当前这个实验属于\(S\) 而且没有做过 那么必须做掉这个实验 不做就被射线轰了 所以记录一下有几个必做实验
- 判断必做实验的个数是不是大于\(a_i\) 如果当前条件是\(a_i\)个数之前 大于\(a_i\) 那么就是不行 不能把这个实验丢进集合里面
时间复杂度\(O(n^2m)\)
能通过此题
Code
#include<bits/stdc++.h>
#define N 605
#define ll long long
using namespace std;
ll mod=998244353;
ll pow2[N],ans;
int n,m,a[N],b[N][N];
int used[N],vis[N];
bool check(int x)
{
fill(used+1,used+1+n,0);
int sum=0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(!vis[b[i][j]]&&!used[b[i][j]])
{
used[b[i][j]]=1;
break;
}
if(!used[b[i][j]])
{
used[b[i][j]]=1;
sum++;
}
}
if(sum>a[i]) return 0;
}
return 1;
}
int main()
{
scanf("%d%d",&n,&m);
pow2[0]=1;
for(int i=1;i<=n;i++)
pow2[i]=pow2[i-1]*2%mod;
for(int i=1;i<=m;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&b[i][j]);
for(int i=1;i<=n;i++)
{
vis[i]=1;
if(check(i))
ans=(ans+pow2[n-i])%mod;
else vis[i]=0;
}
cout<<ans;
return 0;
}
T3崩原之战Ⅱ
____怎么你了
出题人给出化简题意：
本质不同的方案应该是选择一些要求集合，满足存在一种人才分配方案满足这些要求。
即你可以满足这个要求，但是不选择这个要求。
Subtask2
注意到 所有策划的要求无交集 那么肯定每个策划漫不满足都可以
直接输出\(2^n\)即可
期望得分20pts
Subtask1
注意到\(n\)很小 直接暴力 dfs枚举即可
期望得分20pts
错解
考虑 dp
首先把序列按照右端点排序 定义\(f_i\)考虑前\(i\)条线段 当前线段必选有多少种方案
\[f_i=1+\sum\limits_{j=1,c_i=c_j}^{i-1}f(j)+\sum\limits_{j=1,c_i\ne c_j,rj<li}^{i-1}f(j) \]因为前面的同颜色的可以随便选 不同颜色的与我没有交集也能是子问题
但是这样是错的 因为如果当时考虑了\(x\)线段 左端点是\(l_x\)
后面考虑了\(y\)线段 左端点是\(l_y\)
如果\(l_y < l_x\) 以前在\(x\)会考虑\(y\)的一段区间随便选 这是不合法的
比如 \([3,4],[6,7],[1,8]\) 颜色为\(0,1,1\)
容易得到\(f_2=2\) 因为\([3,4]\)可选可不选
但是\(f_3\)=2 因为\([6,7]\)可选可不选 但是\([3,4]\)不能选
如果直接从\(f_2\)转移 那么状态在\(f_2\)时是没有考虑\(1\to 5\)这一段的
所以转移会出错 得到\(f_3=f_2+1=3\)
时间复杂度 \(O(n^2)\)
半正解
根据错解我们得知 不能只考虑一条线段 考虑一组线段
考虑一组线段 转移时必须是和当前颜色不同颜色的线段转移过来
这样子可得
\[f_i=\sum\limits_{j=0,c_i\ne c_j,r_j<i_l}^{i}f_j*2^{ask(i-1,a[j].r,c)} \]其中\(ask(i,r,c)\)表示前\(i\)中有多少条线段左端点大于\(r\)且颜色为\(c\)
可以理解为 求\(r_j\to i_l\)中完全包含在内的线段
为什么呢？因为我们考虑的是不同颜色线段转移 我们考虑的是\(j\)线段为终点的颜色段 所以\(j\)后面的颜色都是一段 那么同一段有多少种这样的线段我们可以算出来 这些线段都有选和不选两种情况(注意：这里和原题意不符 看修改题意) 因此为\(2^x\)
初始化：我们定义\(r_0=0\)，\(f_0=1\) 表示从0为结尾，以第\(1\)条线段为起始的相同颜色段
统计答案：明显有一种情况 全都不满足(一个人都不去) 考虑每段颜色结尾 答案为\(ans=1+\sum\limits_{i=1}^nf_i\)
优化：判断两个颜色是否相同比较麻烦 \(dp\)可以再开一维颜色维 可以不写判断\(c_i\ne c_j\)去掉一个\(if\)语句
时间复杂度\(O(n^3)\)
期望得分 20pts
最朴素DP:
#include<bits/stdc++.h>
#define N 1000005
#define ll long long
using namespace std;
ll mod=998244353,pw[N],ans;
int T;
int n;
ll f[N][2],g[N][2];
struct node{
int l,r,x;
}a[N];
bool cmp(node a,node b)
{
return a.r<b.r;
}
int ask(int x,int r,int c)
{
int sum=0;
for(int i=1;i<=x;i++)
if(c==a[i].x&&a[i].l>=r) sum++;
return sum;
}
int main()
{
pw[0]=1;
for(int i=1;i<=N-4;i++) pw[i]=pw[i-1]*2%mod;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].x);
sort(a+1,a+1+n,cmp);
ans=0;
f[0][0]=f[0][1]=1;
for(int i=1;i<=n;i++)
{
f[i][0]=f[i][1]=0;
int c=a[i].x;
for(int j=0;j<i;j++)
{
if(a[j].r>=a[i].l) break;
f[i][c]+=f[j][c^1]*pw[ask(i-1,a[j].r+1,c)]%mod;f[i][c]%=mod;
}
ans+=f[i][a[i].x];ans%=mod;
}
ans++,ans%=mod;
printf("%lld\n",ans);
}
return 0;
}
一部分的优化
\(O(n^3)\)20pts
稳定发挥 甚至不如直接输出\(2^n\)
我们发现每次\(ask\)是肯定可以优化的 每次做一遍太慢了
观察到每次\(ask\)只是往前推一个\(i\) 里面\(r_j\)的参数不变 因此我们可以开一个\(g_{j,c}\)存下\(ask\)的值 每次修改完改一下\(g\)值即可
因为已经按\(r\)排序了 因此\(r\)是单调递增的 可以用一个二分去掉\(rj<al\)的这句话 直接找到循环终止点
时间复杂度\(O(n^2)\)
#include<bits/stdc++.h>
#define N 1000005
#define ll long long
using namespace std;
ll mod=998244353,pw[N],ans;
int T;
int n,r[N];
ll f[N][2],g[N][2];
struct node{
int l,r,x;
}a[N];
bool cmp(node a,node b)
{
return a.r<b.r;
}
int main()
{
pw[0]=1;
for(int i=1;i<=N-4;i++) pw[i]=pw[i-1]*2%mod;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].x);
sort(a+1,a+1+n,cmp);
ans=0;
for(int i=1;i<=n;i++)
r[i]=a[i].r;
fill(&g[0][0],&g[n+5][0],0);
f[0][0]=f[0][1]=1;
for(int i=1;i<=n;i++)
{
f[i][0]=f[i][1]=0;
int c=a[i].x,end=lower_bound(r+1,r+1+i,a[i].l)-r;
for(int j=0;j<end;j++)
f[i][c]+=f[j][c^1]*pw[g[j][c]]%mod,f[i][c]%=mod;
for(int j=0;j<end;j++)
g[j][c]++;
ans+=f[i][c];ans%=mod;
}
ans++,ans%=mod;
printf("%lld\n",ans);
}
return 0;
}
正解
\(O(n^2)\) emmmm 只能过Subtask1 优化了和没优化一个分
现在要继续改
我们发现 \(pw[g[j][c]]\) 其实可以变成 \(g[j][c]\) 不要让\(g\)数组当成\(2\)的指数 每次修改直接乘\(2\)即可
为了区分 将\(g\)数组变成\(h\)数组
for(int j=0;j<end;j++)
f[i][c]+=f[j][c^1]*h[j][c]%mod,f[i][c]%=mod;
for(int j=0;j<end;j++)
h[j][c]=h[j][c]*2%mod;
发现 \(f[j][1-c]\) 也是一个定值
可以直接初始化就给它丢进去
for(int j=0;j<end;j++)
f[i][c]+=h[j][c]%mod,f[i][c]%=mod;
for(int j=0;j<end;j++)
h[j][c]=h[j][c]*2%mod;
h[i][c^1]=f[i][c];
h[i][c]=0;
其实修改到这里已经差不多了
四条语句分别要做的是：
- 区间查询
- 区间乘2
- 单点修改
直接丢上两棵线段数维护即可
时间复杂度 \(O(n\log n)\)
期望得分100pts
#include<bits/stdc++.h>
#define N 1000005
#define ll long long
using namespace std;
ll mod=998244353,ans;
int T;
int n,r[N];
struct node{
int l,r,x;
}a[N];
struct tree{
ll tr[N*4],lz[N*4];
void clear(int n)
{
for(int i=1;i<=n*4;i++)
tr[i]=0,lz[i]=1;
}
void Pushup(int x)
{
tr[x]=(tr[x*2]+tr[x*2+1])%mod;
}
void Pushdown(int x)
{
if(lz[x]==1) return;
tr[x*2]*=lz[x];tr[x*2]%=mod;
lz[x*2]*=lz[x];lz[x*2]%=mod;
tr[x*2+1]*=lz[x];tr[x*2+1]%=mod;
lz[x*2+1]*=lz[x];lz[x*2+1]%=mod;
lz[x]=1;
}
void modify(int l,int r,int L,int x,ll v)
{
if(l>L||r<L) return ;
if(l==r)
{
tr[x]=v;
return;
}
Pushdown(x);
int mid=(l+r)/2;
modify(l,mid,L,x*2,v);
modify(mid+1,r,L,x*2+1,v);
Pushup(x);
return;
}
void updata(int l,int r,int L,int R,int x)
{
if(l>R||r<L) return;
if(l>=L&&r<=R)
{
tr[x]=tr[x]*2%mod;
lz[x]=lz[x]*2%mod;
return;
}
Pushdown(x);
int mid=(l+r)/2;
updata(l,mid,L,R,x*2);
updata(mid+1,r,L,R,x*2+1);
Pushup(x);
}
ll query(int l,int r,int L,int R,int x)
{
if(l>R||r<L) return 0;
if(l>=L&&r<=R) return tr[x];
Pushdown(x);
int mid=(l+r)/2;
return (query(l,mid,L,R,x*2)+query(mid+1,r,L,R,x*2+1))%mod;
}
}tr[2];
bool cmp(node a,node b)
{
return a.r<b.r;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].x);
sort(a+1,a+1+n,cmp);
ans=0;
for(int i=1;i<=n;i++)
r[i]=a[i].r;
tr[0].clear(n),tr[1].clear(n);
tr[0].modify(0,n,0,1,1);
tr[1].modify(0,n,0,1,1);
for(int i=1;i<=n;i++)
{
int c=a[i].x,end=lower_bound(r+1,r+1+i,a[i].l)-r;
int tmp=0;
tmp=tr[c].query(0,n,0,end-1,1);
tr[c^1].modify(0,n,i,1,tmp);
tr[c].updata(0,n,0,end-1,1);
ans+=tmp;
ans%=mod;
}
ans++,ans%=mod;
printf("%lld\n",ans);
}
return 0;
}
T4 跳水运动员
什么逆天背景(逃
不会 摆(
标签：int,8.8,ll,long,mod,小结,线段,模拟,define From： https://www.cnblogs.com/g1ove/p/17625806.html