2020牛客暑期多校训练营（第十场）题解

校训练营（第十场）题解"/>

2020牛客暑期多校训练营（第十场）题解

文章目录

• • • A. Permutation
    • B. KMP Algorithm
    • C. Decrement on the Tree
    • D. Hearthstone Battlegrounds
    • E. Game
    • I. Tournament
    • J. Identical Trees

A. Permutation

p p p 是一个质数，找到 1 1 1 ~ p − 1 p-1 p−1 的排列 a a a，满足 ∀ i ∈ [ 1 , n ) , 2 a i ≡ a i + 1 ( m o d p ) \forall i\in[1,n),2a_i\equiv a_{i+1}\pmod p ∀i∈[1,n),2ai​≡ai+1​(modp) 或 3 a i ≡ a i + 1 ( m o d p ) 3a_i\equiv a_{i+1}\pmod p 3ai​≡ai+1​(modp)。

设 r r r 为满足 2 r ≡ 1 ( m o d p ) 2^r\equiv 1\pmod p 2r≡1(modp) 的最小的 r r r，将所有 i i i 向 2 i 2i 2i 连边，那么会得到若干个环，每个环大小都是 r r r，一个环内的点 × 3 \times 3 ×3 会同时到达另一个环，原因是设 k k k 为一个环的基数，那么环内所有点都可以表示为 k × 2 c k\times 2^c k×2c，一个环内的点 k × 2 c k\times 2^c k×2c 乘 3 3 3，那么就会到达 3 k × 2 c 3k\times 2^c 3k×2c，这个环的基数为 3 k 3k 3k。

也就是说，假如将每个环看成一个点，那么每个点的出度是固定的，那么从基数最小的环开始走，能乘二就乘二，不能就乘三，如果这样会走出无解那么就一定无解。

基数最小的环显然是基数为 1 1 1 的环，所以从 1 1 1 出发即可。

代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 1000010int T,n;
bool v[maxn];
int ans[maxn];int main()
{ios::sync_with_stdio(false);cin>>T;while(T--){cin>>n;memset(v,false,(n+1)*sizeof(bool));int now=1;v[now]=true;ans[1]=now;for(int i=2;i<n;i++){if(!v[now*2%n])now=now*2%n;else if(!v[now*3%n])now=now*3%n;else ans[1]=-1;v[ans[i]=now]=true;}if(ans[1]==-1)cout<<"-1";else for(int i=1;i<n;i++)cout<<ans[i]<<" ";cout<<endl;}
}

B. KMP Algorithm

令 m i s ( a , b ) = ∑ i = 1 n [ a i ≠ b i ] mis(a,b)=\sum_{i=1}^n [a_i\neq b_i] mis(a,b)=∑i=1n​[ai​​=bi​]，一个 d − p e r i o d i c d-periodic d−periodic 的字符串 s s s 满足 m i s ( s 1 , 2 , . . . , n − d , s d + 1 , d + 2 , . . . , n ) ≤ d mis(s_{1,2,...,n-d},s_{d+1,d+2,...,n})\leq d mis(s1,2,...,n−d​,sd+1,d+2,...,n​)≤d，给出两个 d − p e r i o d i c d-periodic d−periodic 的字符串 s , t s,t s,t，对于每个 i ∈ [ 1 , n − m + 1 ] i\in[1,n-m+1] i∈[1,n−m+1]，求 m i s ( s i , i + 1 , . . . , i + m − 1 , t ) mis(s_{i,i+1,...,i+m-1},t) mis(si,i+1,...,i+m−1​,t)。

要求的就是 ∑ i = 1 n − m + 1 ∑ j = 0 m − 1 [ s i + j ≠ t j + 1 ] \sum_{i=1}^{n-m+1}\sum_{j=0}^{m-1} [s_{i+j}\neq t_{j+1}] ∑i=1n−m+1​∑j=0m−1​[si+j​​=tj+1​]，熟练的OIer会将 t t t 翻转一下，就变成了 ∑ i = 1 n − m + 1 ∑ j = 0 m − 1 [ s i + j ≠ t m − j ] \sum_{i=1}^{n-m+1}\sum_{j=0}^{m-1} [s_{i+j}\neq t_{m-j}] ∑i=1n−m+1​∑j=0m−1​[si+j​​=tm−j​]，此时是个类似卷积的形式，分开考虑每一种字符，对于字符 k k k，令 f i = [ s i = k ] , g i = [ t i = k ] f_i=[s_i=k],g_i=[t_i=k] fi​=[si​=k],gi​=[ti​=k]，那么上面的类卷积状物变成：
∑ i = 1 n − m + 1 ∑ j = 0 m − 1 f i + j g m − j 令 h i + m = ∑ j = 0 m − 1 f i + j g m − j \sum_{i=1}^{n-m+1}\sum_{j=0}^{m-1} f_{i+j}g_{m-j}\\ 令h_{i+m}=\sum_{j=0}^{m-1} f_{i+j}g_{m-j} i=1∑n−m+1​j=0∑m−1​fi+j​gm−j​令hi+m​=j=0∑m−1​fi+j​gm−j​

此时就彻底变成卷积形式了，即 f ∗ g = h f*g=h f∗g=h， h h h 再左移 m m m 位就是答案。但是 26 n log ⁡ n 26n\log n 26nlogn 的复杂度我们依然接受不了，发现还有一个性质没有用：s,t都是d-periodic的。

设 F i = f i − f i + d , G i = g i − g i + d F_i=f_i-f_{i+d},G_i=g_i-g_{i+d} Fi​=fi​−fi+d​,Gi​=gi​−gi+d​，则有：
( F ∗ G ) [ i ] = ( f ∗ g ) [ i ] − 2 ( f ∗ g ) [ i + d ] + ( f ∗ g ) [ i + 2 d ] ( f ∗ g ) [ i ] = ( F ∗ G ) [ i ] + 2 ( f ∗ g ) [ i + d ] − ( f ∗ g ) [ i + 2 d ] (F*G)[i]=(f*g)[i]-2(f*g)[i+d]+(f*g)[i+2d]\\ (f*g)[i]=(F*G)[i]+2(f*g)[i+d]-(f*g)[i+2d] (F∗G)[i]=(f∗g)[i]−2(f∗g)[i+d]+(f∗g)[i+2d](f∗g)[i]=(F∗G)[i]+2(f∗g)[i+d]−(f∗g)[i+2d]

根据性质， F F F 和 G G G 都只有 d d d 位有值，于是可以暴力 d 2 d^2 d2 卷出 F ∗ G F*G F∗G，于是就可以求出 f ∗ g f*g f∗g 了。

代码如下：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 2000010
#define pb push_backint d,n,m;
char s1[maxn],s2[maxn];
struct par{int x,val;};
vector<par> f[27],g[27];
int h[maxn],ans[maxn];int main()
{scanf("%d",&d);scanf("%s",s1+1);n=strlen(s1+1);for(int i=1;i<=n;i++)s1[i]-='a'-1;scanf("%s",s2+1);m=strlen(s2+1);for(int i=1;i<=m;i++)s2[i]-='a'-1;reverse(s2+1,s2+m+1);for(int i=1;i<=d;i++)f[s1[i]].pb((par){i-d,-1});for(int i=1;i<=d;i++)g[s2[i]].pb((par){i-d,-1});for(int i=1;i<=n;i++)if(s1[i]!=s1[i+d]){f[s1[i]].pb((par){i,1});if(i+d<=n)f[s1[i+d]].pb((par){i,-1});}for(int i=1;i<=m;i++)if(s2[i]!=s2[i+d]){g[s2[i]].pb((par){i,1});if(i+d<=m)g[s2[i+d]].pb((par){i,-1});}for(int k=1;k<=26;k++){for(par i:f[k]){for(par j:g[k]){if(i.x+j.x>m)h[i.x+j.x-m]+=i.val*j.val;}}}for(int i=n;i>=1;i--)ans[i]=h[i]+2*ans[i+d]-ans[i+2*d];for(int i=1;i<=n-m+1;i++)printf("%d\n",m-ans[i]);
}

C. Decrement on the Tree

给出一棵边带权的树，一次操作可以选择两个点，将他们路径上所有边的权值 − 1 -1 −1，问最少操作几次可以将所有边权值变为 0 0 0，需要支持单边权值修改。

对于每个点，无论和它相连的边与别的边如何配对，在他这里是确确实实只有这些边，只需要将这些边尽可能多的匹配在一起就好了，如果权值最大的边比其他边的权值和都大，那么就不能将它和别的边匹配完，剩下的部分肯定要单独走。

这样的话每条路径实际上只会在两端被计算，由于两端各计算了一次所以答案要除以 2 2 2，修改的话随便维护一下就好了。

代码如下：

#include <cstdio>
#include <cstring>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 100010
#define ll long longint n,m;
struct edge{int x,y,z;}e[maxn];
multiset<int> s[maxn];ll sum[maxn];
void add(int x,int z){s[x].insert(z);sum[x]+=z;}
void del(int x,int z){s[x].erase(s[x].find(z));sum[x]-=z;}
ll ans=0;
ll calc(int x){int ma=*(--s[x].end());if(ma>sum[x]-ma)return 2*ma-sum[x];else return sum[x]&1;
}int main()
{ios::sync_with_stdio(false);cin>>n>>m;for(int i=1,x,y,z;i<n;i++){cin>>x>>y>>z;e[i]=(edge){x,y,z};add(x,z);add(y,z);}for(int i=1;i<=n;i++)ans+=calc(i);cout<<ans/2<<"\n";for(int i=1,x,y,p,z;i<=m;i++){cin>>p>>z;x=e[p].x,y=e[p].y;ans-=calc(x)+calc(y);del(x,e[p].z);del(y,e[p].z);add(x,e[p].z=z);add(y,z);ans+=calc(x)+calc(y);cout<<ans/2<<"\n";}
}

D. Hearthstone Battlegrounds

有四种剧毒鱼人，圣盾加亡语、圣盾、亡语、无，亡语是召唤一个 1 / 1 1/1 1/1 的植物，给出两人阵容，问如果 A A A 可以随意安排攻击顺序， A A A 能否战胜 B B B。

比较明显的策略是让 A A A 尽可能召唤出亡语去破 B B B 的圣盾，当 B B B 没了圣盾之后，剩下两个人就看谁的攻击频率高了（不算 1 / 1 1/1 1/1）。

但是如果两人攻击频率一样，那么就要看最后谁剩的亡语多，那么在模拟的时候肯定要让 B B B 也尽可能召唤出亡语，这样他一召唤出来 A A A 就可以消灭掉，最后 B B B 剩的植物就尽可能少。

总的来说，要让两人的亡语都尽可能多的触发，并且让 A A A 的植物去破 B B B 的盾，那么 B B B 要节省盾留给 A A A 破于是优先上无圣盾的怪去和 A A A 打。

代码如下：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;int T,a,b,c,d,e,A,B,C,D,E;int main()
{ios::sync_with_stdio(false);cin>>T;while(T--){cin>>a>>b>>c>>d;e=0;cin>>A>>B>>C>>D;E=0;while(a+b+c+d&&A+B+C+D){if(c+d)E=0;if(e&&A+B){if(A)A--,C++;else B--,D++;e=0;}if(c)c--,e++;else if(a)a--,c++;else if(d)d--;else b--,d++;if(C)C--,E++;else if(D)D--;else if(A)A--,C++;else B--,D++;}if(A+B+C+D||(a+b+c+d==0&&E>=e))cout<<"No\n";else cout<<"Yes\n";}
}

E. Game

有一些方块堆积在一起，第 i i i 堆高度为 h i h_i hi​，你可以从某个点将方块整体往左推，问你最后 max ⁡ { h i } \max\{h_i\} max{hi​} 最小是多少。

答案就是前缀平均值中的最大值，这个最大值限制了你不可能将方块推得更低。

代码如下：

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;int T,n;int main()
{scanf("%d",&T);while(T--){scanf("%d",&n);int ans=0;long long tot=0;for(int i=1,x;i<=n;i++){scanf("%d",&x);tot+=x;ans=max(ans,(int)ceil(1.0*tot/i));}printf("%d\n",ans);}
}

I. Tournament

有 n n n 支球队，他们之间要两两进行比赛，共 n ( n − 1 ) 2 \frac {n(n-1)} 2 2n(n−1)​ 场，一支球队的停驻时间为它第一场比赛的时间到它最后一场比赛的时间，你要构造一个比赛排列方案使所有球队我的总停驻时间最小。

膜一手这位大佬。

容易想到一个暴力的不优秀的构造：像样例那样， i , j i,j i,j 升序枚举然后直接输出。

考虑再暴力构造的基础上优化：对于一场比赛 ( i , j ) ( i < j ) (i,j)(i<j) (i,j)(i<j)，如果将它移到 ( 1 , j + 1 ) (1,j+1) (1,j+1) 的前面一位，那么前 i − 1 i-1 i−1 支球队总时间 + 1 +1 +1，后 n − j n-j n−j 支球队总时间 − 1 -1 −1，总共增加了 i − 1 − ( n − j ) i-1-(n-j) i−1−(n−j)

那么容易得到一个策略，如果 i − 1 − ( n − j ) < 0 i-1-(n-j)<0 i−1−(n−j)<0，那么将这场比赛放到 ( 1 , j + 1 ) (1,j+1) (1,j+1) 的前面，转化一下就是 i < n − j + 1 i<n-j+1 i<n−j+1。

剩下的就是直接升序输出，代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;int T,n;int main()
{ios::sync_with_stdio(false);cin>>T;while(T--){cin>>n;for(int j=1;j<=n;j++){for(int i=1;i<min(j,n-j+1);i++){cout<<i<<" "<<j<<"\n";}}for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){if(i>=min(j,n-j+1))cout<<i<<" "<<j<<"\n";}}}
}

J. Identical Trees

给出两棵有标号的树，你要尽可能少的修改其中一棵树的标号，然后使得两棵树完全相同。

考虑树形 dp \text{dp} dp，令 f [ a ] [ b ] f[a][b] f[a][b] 表示第一棵树的子树 a a a 最少改几个点的编号可以和第二棵树的子树 b b b 相同，如果 a , b a,b a,b 子树不同构那么就直接赋值为 inf ⁡ \inf inf。

转移的时候考虑让 a , b a,b a,b 的儿子的子树两两配对，配对出来的最小修改次数就是答案，可以用最小费用最大流优化。

假如你的 c a s e case case 通过率在 70 % 70\% 70% ~ 90 % 90\% 90%，那么你可能是判断树是否同构时用到的哈希构造的不够优秀，哈希内要尽可能包含该节点拥有的别的节点没有的信息。

代码如下：

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 2010
#define ll long longint n,rt1,rt2;
vector<int> e1[maxn];
vector<int> e2[maxn];
int sz1[maxn],sz2[maxn];
ll ha1[maxn],ha2[maxn],*Ha;
bool cmp(int x,int y){return Ha[x]<Ha[y];}
void dfs(int x,int id){vector<int> &e=(id==1?e1[x]:e2[x]);ll *ha=(id==1?ha1:ha2);for(int y:e)dfs(y,id);Ha=ha;sort(e.begin(),e.end(),cmp);ha[x]=e.size()+1;for(int y:e)ha[x]=(ha[x]*37ll+ha[y])%990452799045277ll;
}
struct Network{int S,T;struct edge{int x,y,z,c,next;}e[5000010];int first[maxn],len;void buildroad(int x,int y,int z,int c){e[++len]=(edge){x,y,z,c,first[x]};first[x]=len;}void ins(int x,int y,int z,int c){buildroad(x,y,z,c);buildroad(y,x,0,-c);}void clear(){while(len>1)first[e[len--].x]=0;len=1;}int q[maxn],st,ed,dis[maxn],fa[maxn];bool v[maxn];bool SPFA(){memset(v,false,(T+1)*sizeof(bool));memset(dis,63,(T+1)*sizeof(int));memset(fa,0,(T+1)*sizeof(int));st=1;ed=2;q[st]=S;dis[S]=0;while(st!=ed){int x=q[st++];v[S]=false;st=st>T?1:st;for(int i=first[x];i;i=e[i].next){int y=e[i].y;if(e[i].z&&dis[y]>dis[x]+e[i].c){dis[y]=dis[x]+e[i].c;fa[y]=i;if(!v[y])v[q[ed++]=y]=true,ed=ed>T?1:ed;}}}return fa[T];}int MCMF(){int re=0;while(SPFA()){int mi=1e9;for(int i=fa[T];i;i=fa[e[i].x])mi=min(mi,e[i].z);for(int i=fa[T];i;i=fa[e[i].x]){e[i].z-=mi,e[i^1].z+=mi;re+=mi*e[i].c;}}return re;}
}G;
int f[maxn][maxn];
int solve(int x1,int x2){if(ha1[x1]!=ha2[x2]||e1[x1].size()!=e2[x2].size())return n;if(e1[x1].size()+e2[x2].size()==0)return x1!=x2;for(int y1:e1[x1])for(int y2:e2[x2])f[y1][y2]=solve(y1,y2);G.clear();int num1=0,num2;for(int y1:e1[x1]){num1++;num2=0;for(int y2:e2[x2]){num2++;if(f[y1][y2]<n)G.ins(num1,num2+e1[x1].size(),1,f[y1][y2]);}}G.S=e1[x1].size()+e2[x2].size()+1;G.T=G.S+1;num1=0;for(int y1:e1[x1])num1++,G.ins(G.S,num1,1,0);num2=0;for(int y2:e2[x2])num2++,G.ins(num2+e1[x1].size(),G.T,1,0);return G.MCMF()+(x1!=x2);
}int main()
{cin>>n;for(int i=1,fa;i<=n;i++){cin>>fa;if(!fa)rt1=i;else e1[fa].push_back(i);}for(int i=1,fa;i<=n;i++){cin>>fa;if(!fa)rt2=i;else e2[fa].push_back(i);}dfs(rt1,1);dfs(rt2,2);cout<<solve(rt1,rt2);
}