2月做题记录

2月做题记录
最后一个2月份了,年份都不用写了;即使实力不强也希望这份题单能给后人一些帮助

一类多项式题、一类形式的处理思路:牛客网Wannafly挑战赛24F wyf的超级多项式

有意思的模型:CF1172C2 Nauuo and Pictures

「在家=摸鱼」系列

EA的练习赛D 最优性剪枝

请先思考后再展开

首先显然将答案写成$\sum_x x被访问到的概率$,这个是基本的期望线性性,然后这里x被访问到的条件为没有访问过dep更小的点

于是容易得到一个复杂度不重要暴力:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vc<int> son[N];int ff[N],val[N],dep[N];
void pre(int x){ dep[x]=dep[ff[x]]+1;val[x]=(!sz(son[x])?dep[x]:INF);for(auto y:son[x]) pre(y),chmin(val[x],val[y]); }
void main()
{
int n=qread();fo(i,2,n) son[ff[i]=qread()].PB(i);pre(1);
fo(x,1,n) sort(all(son[x]),[&](int x,int y){return val[x]<val[y];});
ll ans=0;
fo(x,1,n)
{
ll now=1;
for(int anc=ff[x],lst=x;anc;lst=anc,anc=ff[anc])
{
int cnt=0;for(auto y:son[anc]) if(y!=lst and val[y]<dep[x]) cnt++;
now=now*invm(cnt+1)%MOD;
}add(ans,now);
}write(ans);
}

容易发现很明显每个点的权值应该是容易维护的。具体的,将孩子排序,从孩子i切换到孩子i+1时,变化的只有$[val_i,val_{i+1})=\frac{1}{i} \to \frac{1}{i+1}$,于是用个树状数组维护乘法差分即可,$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
namespace BIT
{
ll bit[N];void clear(){ fo(i,1,N-1) bit[i]=1; }
int lowbit(int x){return x&-x;}
void mul(int x,ll c){ while(x<N) bit[x]=bit[x]*c%MOD,x+=lowbit(x); }
void MUL(int l,int r,ll c){ mul(l,c),mul(r,invm(c)); }//[l,r)*=c
ll ask(int x){ ll ret=1;while(x>=1) ret=ret*bit[x]%MOD,x-=lowbit(x);return ret; }
};
ll ans=0;
void solve(int x)
{
add(ans, BIT::ask(dep[x]-1) );
int m=sz(son[x]);
#define V(i) (i>m?N:val[son[x][i-1]])
fo(i,2,m) BIT::MUL(V(i),V(i+1),invm(i));
fo(i,1,m)
{
int y=son[x][i-1];solve(y);
if(i<m) BIT::MUL(V(i),V(i+1),i*invm(i+1)%MOD);
}
fo(i,1,m-2) BIT::MUL(V(i),V(i+1),i+1);if(m>1) BIT::MUL(V(m-1),N,m);
}

EA的练习赛E 燔祭

请先思考后再展开

考虑恰用了k种值,因为保证了父亲总是不小于儿子,从大到小加入点,根据拓展prufer(原本的点看做一个带权大点,内部有根,加入点的时候当做无向图处理,这样得到的仍是有根树)易知$val(k,j)=向k个点加入j个点的方案数=(1*k+j*1)^{1+j-2}*k$,直接$dp(cnt,k+j)+=dp(cnt-1,k)*val(k,j)$即可

$O(n^3)$,可以用FFT优化至$O(n^2log)$

1
2
3
4
fo(k,1,n) fo(j,1,n-k) val[k][j]=k*qpower(k+j,j-1)%MOD*C[n-k][j]%MOD;
fo(t,1,n) dp[1][t]=C[n][t]*qpower(t,t-1)%MOD;
fo(cnt,1,n-1) fo(k,1,n) fo(j,1,n-k) add( dp[cnt+1][k+j],dp[cnt][k]*val[k][j]%MOD );
ll ans=0;for(ll cc=m,cnt=1;cnt<=n and cnt<=m;cnt++,cc=cc*invm(cnt)%MOD*(m-cnt+1)%MOD) add(ans, dp[cnt][n]*cc%MOD );write(ans);

另外有$O(n^3ln)$的插值做法,官方题解也是这个做法,不知为何题解和代码写得鬼长

牛客网Wannafly挑战赛24F wyf的超级多项式

感觉这道题给出了一类题、一类形式的处理思路

请先思考后再展开

容易想到写出F的生成函数$F(x)=\sum_{j=1}^k \frac{a_j}{1-v_jx}$,这种时候套路地考虑通分,$C(x)=\prod_{j=1}^k (1-v_jx),F(x)=\frac{A(x)}{C(x)}$

注意到$C(x)=1-\sum_{i=1}^k c_ix^i$,因此把C乘到左边后会非常像个递推式,具体而言就是$A(x)=F(x)-\sum_{i=1}^k \sum_{j=0}^{\infty} c_iF_jx^{i+j}$,因为A在后面是没有值的,$对于i>k,F_i=\sum_{j=1}^k c_j F_{i-j}$,发现分治FFT求出c之后对于本题可以直接$O(k(n-k))$递推,事实上熟练的选手会发现这其实是个常系数线性递推,可以做到$O(k^2)或O(klogk)$

CF1278F Cards

请先思考后再展开

$$
E(x^k)=\sum_{x=0}^n C_n^x p^x (1-p)^{n-x}x^k,斯特林数展开并交换和号得\sum_{j=0}^k S_2(k,j)C_n^jj!\sum_{x=j}^n C_{n-j}^{x-j} p^x(1-p)^{n-x}=\sum_{j=0}^k S_2(k,j) n^{\underline j} p^j
$$

1
2
3
S2[0][0]=1;fo(i,1,N-1) fo(j,1,i) S2[i][j]=(S2[i-1][j-1]+S2[i-1][j]*j)%MOD;
int n=qread(),m=qread(),k=qread();m=invm(m);
ll ans=0;for(ll val=1,j=0;j<=k;j++,val=val*m%MOD*(n-j+1)%MOD) add(ans,S2[k][j]*val%MOD);write(ans);

CF1303F Number of Components

请先思考后再展开

我的$O(nmc*\alpha(nm))$做法:对于每种颜色,先正序处理出这种颜色的联通块个数,再倒序处理其他颜色联通块,这样就只有合并了,dsu维护即可,被hack过是因为我以为数据范围数min而不是max,所以当时写的带个log且常数较大,code

CF1301F Super Jaber

请先思考后再展开

思考一条路径长啥样,容易发现我们可以把要跳跃的那些颜色看做一个大点,中间不跳跃的那些其实就是两个颜色的bfs距离。floyd后枚举起始和终止的大点是什么即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int n,m,K,a[N][N];
int floyd[KK][KK];
vc<pii> pt[KK];int dis[KK][N][N];
const int tx[]={0,0,-1,1},ty[]={-1,1,0,0};
void bfs(int col)
{
queue<pii> q;for(auto in:pt[col]) dis[col][in.FR][in.SE]=0,q.push(in);
while(sz(q))
{
int x=q.front().FR,y=q.front().SE;q.pop();chmin(floyd[col][a[x][y]],dis[col][x][y]+1),chmin(floyd[a[x][y]][col],dis[col][x][y]+1);
fo(t,0,3){
int xx=x+tx[t],yy=y+ty[t];
if(dis[col][xx][yy]>dis[col][x][y]+1 and 1<=xx and 1<=yy and xx<=n and yy<=m) dis[col][xx][yy]=dis[col][x][y]+1,q.push({xx,yy});
}
}
}
void main()
{
mem(dis,0x3f);mem(floyd,0x3f);fo(i,0,KK-1) floyd[i][i]=0;
n=qread(),m=qread(),K=qread();fo(i,1,n) fo(j,1,m) pt[a[i][j]=qread()].PB({i,j});fo(col,1,K) bfs(col);
fo(k,1,K) fo(i,1,K) fo(j,1,K) chmin(floyd[i][j],floyd[i][k]+floyd[k][j]);
fo(tim,1,qread())
{
int x1=qread(),y1=qread(),x2=qread(),y2=qread();int ans=abs(x1-x2)+abs(y1-y2);
fo(i,1,K) fo(j,1,K) chmin(ans, floyd[i][j]+1+dis[i][x1][y1]+dis[j][x2][y2] );write2(ans);
}
}

CF1172C2 Nauuo and Pictures

题意:n张图,给定是否喜欢,给定初始权值wi,抽到每张图的概率为$\frac{w_i}{\sum w_j}$,喜欢就wi++否则wi–,问做m轮后每个w的期望,$n \le 2e5,m \le 3e3$

请先思考后再展开

发现在这个模型中,可以把若干个数合并,或一个分裂成若干个。直觉是直接变成全1,于是自然地发现,$\forall i,\frac{E_i}{\sum E_j}=\frac{w_i}{\sum w_j}$,写个$m^2$的显然dp就做完了

CF1313F Concatenation with intersection

题意:给出两个长度为n的字符串A和B,以及一个长度为m的字符串S,求有多少$([l_1,r_1],[l_2,r_2])满足A_{l_1 \sim r_1}+B_{l_2 \sim r_2}=S$

请先思考后再展开

发现如果我们枚举S的前缀i由A负责,将A中能得到前缀i的开头记为集合aa,将B中能得到后缀m-i的结尾记为集合bb,则$ans+=\sum_{i \in aa,j \in bb} j-i+1 \in [1,m)$

先通过二分hash或exkmp预处理出A中每个位置,不断减小a集合增大b集合,树状数组去对方那里找即可,$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const int N=1e6+10;char S[3][N];
const int base=131,mod=993244853;ll bs[N];
ll hash[3][N];ll G(int op,int l,int r){return (hash[op][r]+MOD-hash[op][l-1]*bs[r-l+1]%MOD)%MOD;}
//��״����
struct BIT
{
int bit[N];int lowbit(int x){return x&-x;}
void ad(int x,int c){ while(x<N) bit[x]+=c,x+=lowbit(x); }
int ask(int x){ chmin(x,N-1);int ret=0;while(x>=1) ret+=bit[x],x-=lowbit(x);return ret; }
int ask2(int l,int r){return ask(r)-ask(l-1);}
}bit[3];
vc<int> del[N],ins[N];
void main()
{
PRE();
bs[0]=1;fo(i,1,N-1) bs[i]=bs[i-1]*base%MOD;
int n=qread(),m=qread();scanf("%s%s%s",S[1]+1,S[2]+1,S[0]+1);
fo(op,1,2) fo(i,1,n) hash[op][i]=(hash[op][i-1]*base+S[op][i]-'a'+1)%MOD;fo(i,1,m) hash[0][i]=(hash[0][i-1]*base+S[0][i]-'a'+1)%MOD;
fo(i,1,n)
{
int mx=0;
for(int tl=1,tr=min(n-i+1,m);tl<=tr;)
{
int mid=(tl+tr)/2;
if(G(1,i,i+mid-1)==G(0,1,mid)) mx=mid,tl=mid+1; else tr=mid-1;
}del[mx+1].PB(i);//debug("A[%d]=%d\n",i,mx);
}
fo(i,1,n)
{
int mx=0;
for(int tl=1,tr=min(i,m);tl<=tr;)
{
int mid=(tl+tr)/2;
if(G(2,i-mid+1,i)==G(0,m-mid+1,m)) mx=mid,tl=mid+1; else tr=mid-1;
}ins[mx].PB(i);//debug("B[%d]=%d\n",i,mx);
}
ll ans=0,sum=0;fo(i,1,n) bit[1].ad(i,1);for(auto i:ins[m]) bit[2].ad(i,1),sum+=bit[1].ask2(i-m+2,i);
for(int ii=1,jj=m-1;ii<m;ii++,jj--)
{
for(auto i:del[ii]) bit[1].ad(i,-1),sum-=bit[2].ask2(i,i+m-2);
for(auto i:ins[jj]) bit[2].ad(i, 1),sum+=bit[1].ask2(i-m+2,i);
ans+=sum;//deb(sum);
}write(ans);
}

题外话:这场vp居然0罚时,而且不考虑看错题可能可以压线AK,于是就心安理得颓起来了

CF1304D Shortest and Longest LIS

请先思考后再展开

想不通为什么这么多人会做,也不知道怎么辩护,那就欣赏下wqy的code吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
scanf("%d%s",&n,s+1);
for(int i=1;i<=n;i++)p[i]=n-i+1;
for(int i=1;i<n;)
{
int j=i;while(s[j]=='<')j++;
reverse(p+i,p+j+1);i=j+1;
}
for(int i=1;i<=n;i++)printf("%d ",p[i]);printf("\n");
for(int i=1;i<=n;i++)p[i]=i;
for(int i=1;i<n;)
{
int j=i;while(s[j]=='>')j++;
reverse(p+i,p+j+1);i=j+1;
}
for(int i=1;i<=n;i++)printf("%d ",p[i]);printf("\n");

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/c542c4cc.html
转载请注明出处,谢谢!