Codeforces Round 1090 (Div. 4) 题解

A. The 67th Integer Problem防止越界直接输出x即可#includebits/stdc.h#defineintlonglong#defineN#definedebug(x)cout#x:x ;usingnamespacestd;intT,n,m;voidsolve(){cinn;coutn\n;}signedmain(){T1;cinT;while(T--){solve();}return0;}B. The 67th 6-7 Integer Problem可以发现不反转的数一定是初始序列中最大的那个#includebits/stdc.h#defineintlonglong#defineN#definedebug(x)cout#x:x ;usingnamespacestd;intT,n,m;inta[10];voidsolve(){// cinn;intsum0;for(intt1;t7;t)cina[t];for(intt1;t7;t){sum-a[t];}sort(a1,a17);cout2*a[7]sum\n;}signedmain(){T1;cinT;while(T--){solve();}return0;}C. The 67th Permutation Problem发现最大值无法贡献我们可以贡献第2大的值但这会导致第3大的值无法贡献。所以我们选择的中位数最大可能是第2468…大的值。#includebits/stdc.h#defineintlonglong#defineN#definedebug(x)cout#x:x ;usingnamespacestd;intT,n,m;voidsolve(){cinn;for(intt3*n,u11;u1n;u1){coutt t-1 u1 ;t-2;}cout\n;}signedmain(){T1;cinT;while(T--){solve();}return0;}D. The 67th OEIS Problem考虑让gcdgcdgcd全为质数对于一个数让它包含两个不同的质因子ai−1pt∗piaipi∗pjai1pj∗pka_{i-1}p_t*p_ia_ip_i*p_ja_{i1}p_j*p_kai−1​pt​∗pi​ai​pi​∗pj​ai1​pj​∗pk​gcd⁡(ai−1,ai)pigcd⁡(ai,ai1)pj\gcd(a_{i-1},a_{i})p_i\gcd(a_{i},a_{i1})p_jgcd(ai−1​,ai​)pi​gcd(ai​,ai1​)pj​#includebits/stdc.h#defineintlonglong#defineN1005000#definedebug(x)cout#x:x ;usingnamespacestd;intT,n,m;intvalid[N];vectorintprime;voidinit(intx){for(intt2;tx;t){if(!valid[t]){prime.push_back(t);}for(autop:prime){if(t*px)break;valid[t*p]1;if(t%p0){break;}}}}voidsolve(){// debug(prime.size())cinn;for(intt0;tn;t){intu1;if(t0)u1prime[t];elseu1prime[t]*(prime[t-1]);coutu1 ;}cout\n;}signedmain(){init(200000);T1;cinT;while(T--){solve();}return0;}E. The 67th XOR Problem注意到异或具有自反性也就是说一步操作在两次之后就会消失。所以直接找两个数最大异或和即可。#includebits/stdc.h#defineintlonglong#defineN4100#definedebug(x)cout#x:x ;usingnamespacestd;intT,n,m;inta[N];voidsolve(){cinn;intmaxn0;for(intt1;tn;t){cina[t];}for(intt1;tn;t){for(inti1;in;i){if(ti)continue;maxnmax(maxn,a[t]^a[i]);}}coutmaxn\n;}signedmain(){T1;cinT;while(T--){solve();}return0;}F. The 67th Tree Problem我们发现根节点的子树大小就是xyxyxy也就是说根节点是奇点还是偶点已经确定好了排除根节点开始构造。我们发现可以通过一个奇数点一个偶数点的构造或者仅一个奇数点的构造不能仅一个偶数点的构造因为这样一定还会产生一个奇数点。如果去掉根节点后偶数点比奇数点多的话就是无解情况#includebits/stdc.h#defineintlonglong#defineN#definedebug(x)cout#x:x ;usingnamespacestd;intT,n,m;voidsolve(){intx,y;cinxy;intnxx,nyy;if((xy)1){ny-1;}elsenx-1;if(nx0nxny){coutYES\n;intcnt1;for(intt1;tnx;t){cout1 cnt\n;coutcnt cnt\n;}for(intt1;tny-nx;t){cout1 cnt\n;}}elsecoutNO\n;}signedmain(){T1;cinT;while(T--){solve();}return0;}G. The 67th Iteration of “Counting is Fun”观察样例后我们发现有以下几种情景一个点的邻居刚坐下它也跟着坐下这种情况说明可以是受到邻居条件制约也可能是受到人数条件制约。一个点的邻居坐下之后它没有立刻跟着坐下这种情况说明是受到人数条件制约。一个点的邻居还没坐下它就坐下了这种情况无解输出000所以我们按照时间先后顺序处理点#includebits/stdc.h#defineintlonglong#defineN200005#definedebug(x)cout#x:x ;usingnamespacestd;intT,n,m;intb[N];intmodd676767677;vectorintv[N];boolvalid[N];intc[N];voidsolve(){cinnm;for(intt0;tn2;t){valid[t]0;}for(intt0;tm;t){v[t].clear();}for(intt1;tn;t){cinb[t];v[b[t]].push_back(t);}c[0]v[0].size();for(intt1;tm-1;t){c[t]c[t-1]v[t].size();}// queuepairint,int q;for(intt1;tn;t){if(!b[t]){valid[t]1;}}intans1;// valid[0]valid[n1]1;for(intt1;tm-1;t){for(autoi:v[t]){if(valid[i-1]0valid[i1]0){// debug(t)debug(i)coutendl;cout0\n;return;}else{intminn1e18;if(i!1valid[i-1]1)minnmin(minn,b[i-1]);if(i!nvalid[i1]1)minnmin(minn,b[i1]);if(b[i]!minn1){ans*(c[b[i]-1]-c[b[i]-2])%modd;ans%modd;}else{ans*c[b[i]-1]%modd;ans%modd;}}}for(autoi:v[t]){valid[i]1;}}coutans\n;}signedmain(){T1;cinT;while(T--){solve();}return0;}