Codeforces Good Bye 2022 CF 1770 A~E 题解

题目链接

A. Koxia and Whiteboards

注意每一步替换操作都是强制的，而不是可选的。所以就用一个multiset维护所有的数，每次选一个最小的替换掉即可。

(资料图片仅供参考)

时间复杂度\(O(nlogn)\)。

点击查看代码

#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;LL t,n,m,a[110],b[110];int main(){  fileio();  cin>>t;  rep(tn,t)  {    scanf("%lld%lld",&n,&m);    multiset  st;    rep(i,n) scanf("%lld",&a[i]),st.insert(a[i]);    rep(i,m)    {      scanf("%lld",&b[i]);      //if(*st.begin()

`B. Koxia and Permutation`

k=1的情况，输出任意排列都可以。k>1时，发现一个包含数n的长度为k的字段的权值至少为n+1，盲猜存在一种排法使得最大权值就是n+1。其实下面的排法就满足要求：\(n,1,n-1,2,n-2,3\cdots\)。比如n=7时，排列就是\(7,1,6,2,5,3,4\)。在这种排法下，如果一个子段的最大值\(x>\frac n2\)，由于它右边的数是\(n+1-x\)，左边的数是\(n-x\)，所以子段的权值绝对不会超过\(n+1\)。子段的最大值\(\le \frac n2\)时权值不可能达到\(n+1\)。所以这种构造是正确的。

时间复杂度\(O(n)\)。

点击查看代码

#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;int t,n,k;int main(){  fileio();  cin>>t;  rep(tn,t)  {    cin>>n>>k;    int lb=1,ub=n;    while(lb

`C. Koxia and Number Theory`

我们先\(O(n^2)\)地枚举数组中的每对数(a,b)，看看如果要求\(gcd(a+x,b+x)=1\)的话x需要满足什么条件。如果a=b显然无解。否则令a,b中较小的为c，较大的为c+d。则我们要求\(gcd(c+x,d)=1\)，也就是对于d的每个质因数，c+x都不能是这个质因数的倍数，也就是对于任意\(e|d,e是质数\)，满足\(x \neq -c (mod \ e)\)。枚举了所有\(O(n^2)\)对数之后我们会得到若干个限制，如果存在某个质数p，我们要求\(x\ mod \ p\neq 0,x\ mod\ p\neq 1\cdots x\ mod\ p\neq p-1\)，也就是所有p个限制都占满了，那肯定无解；否则根据中国剩余定理一定有解。

但是在上面枚举的过程中，\(d\)的数据范围是1e18，没法分解质因数。注意到一共只会产生\(\frac{n(n-1)}2\)个限制，所以在\(p>\frac{n(n-1)}2\)的情况下是不可能占满p个限制导致无解的，故只需考虑这个范围内的质数。

时间复杂度没仔细算，反正肯定是能过的。

点击查看代码

#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;LL t,n,a[110],cnt[800][6000],lim;vector  pri;bool isp(LL x){  for(LL i=2;i*i<=x;++i) if(x%i==0) return false;  return true;}void precalc(){  for(LL i=2;i<=6000;++i)    if(isp(i)) pri.pb(i);}int main(){  fileio();  precalc();  cin>>t;  repn(tn,t)  {    cin>>n;    rep(i,n) cin>>a[i];    LL tot=(n+1)*n/2+10;    lim=0;    rep(i,pri.size()) if(pri[i]<=tot) ++lim;    bool bad=false;    rep(i,n)    {      for(int j=i+1;j

`D. Koxia and Game`

按照游戏的过程正着分析看不出什么，我们倒着看看。方便起见把删数的那个人称为K，选数的那个人称为M。考虑这三个序列的最后一个数组成的multiset\(\{a_n,b_n,c_n\}\)，如果K删掉了某个元素使得剩下的两个元素不相等，那K是不可能赢的，因为M总能找出一个元素使得最后形成的序列不是排列。所以\(a_n,b_n,c_n\)三个数不能全不同，至少得有两个相同的，且K一定是留下两个相同的数。倒数第二个位置同理，顺着推下去其实前面的每个位置都同理。

所以现在问题变成了这样：有两个数列a和b，对于每个i你可以在\(a_i,b_i\)中选恰好一个数，要求最后选出的序列是排列，求方案数。对于\(a_i=b_i\)的位置，会额外有\(n\)的方案数(因为原问题中\(c_i\)在这里可以乱选)。如果有解的话，最后把这个额外的方案数乘上就行了，下面的思考过程忽略这个额外的方案数。

转化成图论问题：把每个数看成一个点，对于每个i，在\(a_i,b_i\)之间连一条无向边。这个图中可能有自环和重边。建完图之后发现图是由一些连通块组成的。如果一个连通块内的点数和边数不相等，显然无解。否则这个连通块就是一个基环树，我们需要为每个点选一条相邻的边与其匹配，使得每条边恰好被匹配一次，并求出方案数。如果基环是一个自环，那显然只有1种方案。否则有两种方案，因为基环有两种匹配的方向。所以每个连通块的方案数都是1或2，全部乘起来就行了。

时间复杂度\(O(nlogn)\)，因为要使用并查集维护图(其实直接搜也可以O(n))。

点击查看代码

#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;const LL MOD=998244353;LL t,n,a[100010],b[100010],cnt[100010],fa[100010],sc[100010],sz[100010];LL Find(LL x){return fa[x]==x ? x:fa[x]=Find(fa[x]);}int main(){  fileio();  cin>>t;  rep(tn,t)  {    cin>>n;    rep(i,n) scanf("%lld",&a[i]);    rep(i,n) scanf("%lld",&b[i]);    repn(i,n) cnt[i]=sc[i]=0,fa[i]=i,sz[i]=1;    LL mul=1;    rep(i,n)    {      if(a[i]==b[i]) ++sc[a[i]],++cnt[a[i]],(mul*=n)%=MOD;      else      {        ++cnt[a[i]];        if(Find(a[i])!=Find(b[i])) fa[Find(a[i])]=Find(b[i]);      }    }    repn(i,n) if(Find(i)!=i) cnt[Find(i)]+=cnt[i],sc[Find(i)]+=sc[i],++sz[Find(i)];    bool bad=false;    repn(i,n) if(Find(i)==i)    {      if(cnt[i]!=sz[i]){bad=true;break;}      if(sc[i]==0) (mul*=2)%=MOD;    }    if(bad) puts("0");    else printf("%lld\n",mul);  }  termin();}

`E. Koxia and Tree`

我一开始想的是：对每个点求出进行完所有操作后这个位置包含蝴蝶的概率，然后用这个概率加权求出两两之间的距离和。不幸的是这么做是错的，因为每个点包含蝴蝶的概率并不独立，它们之间是有关联的，比如k=1时答案应该是0，这个方法算出的答案就不是0。

换一种思路。先把1定为树的根。对于每个子树，我们想求出从它的根到其父亲的那条边，在画出蝴蝶两两之间路径时期望被走了多少次。把所有边的这个值加起来就得到了蝴蝶两两之间距离和的期望，除以蝴蝶对数就得到答案了。对于点i，令\(sz_i=\)初始状态下(没开始操作的时候)i的子树内的蝴蝶数量。发现所有操作做完后i子树内的蝴蝶数量只有三种可能：\(sz_i-1,sz_i,sz_i+1\)，因为每条边最多运送一只蝴蝶，也最多只有一只蝴蝶能被运进或运出子树。如果能分别求出这三种情况发生的概率，也就能求出最终答案了。比如子树内蝴蝶数量为\(sz_i\)的概率是p，则对蝴蝶两两之间距离和的期望的贡献是\(sz_i\cdot(n-sz_i)\cdot p\)。这里我们计算期望时只有一个变量，不存在什么独立性的问题，所以正确性是有的。

对于一个点i，假设从它连向父亲的边的编号为j。如果我们知道在进行了j-1次操作后点i有蝴蝶的概率(p)与点i的父亲有蝴蝶的概率(q)，那就能求出上面说的三个概率了。这里p和q是独立的、没有关联的，因为前j-1次操作都是在这条边两侧的两个连通块内进行的，互不影响。所以这么做是有正确性的。

从前到后依次进行操作，并同时维护每个点有蝴蝶的概率，这点也是很容易做到的。假设当前边连接(x,y)，则令\(p_x=p_y=np,其中np=\frac{p_x+p_y}2\)即可，按照题目定义推一推就能得到。

时间复杂度\(O(n)\)。

点击查看代码

#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;const LL MOD=998244353;LL qpow(LL x,LL a){LL res=x,ret=1;while(a>0){if(a&1) (ret*=res)%=MOD;a>>=1;(res*=res)%=MOD;}return ret;}LL n,k,a[300010],inv2=qpow(2,MOD-2),ans=0,dep[300010],sz[300010];vector  g[300010];vector  e;LL dfs(LL pos,LL par){  sz[pos]=a[pos];  rep(i,g[pos].size()) if(g[pos][i]!=par)  {    dep[g[pos][i]]=dep[pos]+1;    sz[pos]+=dfs(g[pos][i],pos);  }  return sz[pos];}int main(){  fileio();  cin>>n>>k;  LL x;rep(i,k){scanf("%lld",&x);a[x]=1;}  LL y;  rep(i,n-1)  {    scanf("%lld%lld",&x,&y);    e.pb(mpr(x,y));    g[x].pb(y);g[y].pb(x);  }  dfs(1,0);  rep(i,n-1)  {    x=e[i].fi;y=e[i].se;    if(dep[x]>dep[y]) swap(x,y);//x上y下    LL pls=a[x]*(1LL-a[y]+MOD)%MOD*inv2%MOD,sub=a[y]*(1LL-a[x]+MOD)%MOD*inv2%MOD,mid=(1LL-pls-sub+MOD+MOD)%MOD;    (ans+=sz[y]*(k-sz[y])%MOD*mid)%=MOD;    (ans+=(sz[y]+1)*(k-sz[y]-1)%MOD*pls)%=MOD;    (ans+=(sz[y]-1)*(k-sz[y]+1)%MOD*sub)%=MOD;    LL sum=(a[x]+a[y])%MOD;    (sum*=inv2)%=MOD;    a[x]=a[y]=sum;  }  LL tot=(k-1)*k/2%MOD;  (ans*=qpow(tot,MOD-2))%=MOD;  cout<