Codeforces Round 1068 (Div. 2) D，E 题解

D. Taiga’s Carry Chains

Miracles don’t happen to those who just wait.

— Toradora!

After classes at Ohashi High School, Ryuuji hands Taiga a positive integern nnand sets a simple challenge.

They will play for exactlyk kkmoves. In a single move, Taiga chooses a non-negative integerℓ \ellℓand setsn ← n + 2 ℓ n \gets n + 2^{\ell}n←n+2ℓ.

Ryuuji defines the score of one move as the number of binary carries that occur when adding2 ℓ 2^{\ell}2ℓto the current number in base2 22. The total score is the sum of score over allk kkmoves.

Taiga wants the total score to be as large as possible afterk kkmoves. What is the maximum total score she can achieve?

大桥高中放学后，龙寺递给大河一个正整数n并设定了一个简单的挑战。

他们将精确执行 k 步。在一次移动中，Taiga 选择一个非负整数 ℓ 并设置n ← n + 2 ℓ n \gets n + 2^{\ell}n←n+2ℓ.

Ryuuji 将一步棋的分数定义为将 2ℓ 添加到基数 2 中的当前数字时发生的二进制进位数。总得分是所有 k 动作的得分总和。

大河希望 k 移动后总得分尽可能大。她能达到的最高总分是多少？

题解：

可以发现一些性质，就是如果步骤足够大，可以把所有的二进制中的 0 全部填写为 1，这就是一个贪心上的最优解，但是我们往往没有那么大的步骤数，则此时可以有一些转化。

下面介绍两种思路：

• 直接把所有的间隔（连续的 0 的块）进行枚举，我们可以发现：int范围内二进制位数最多 32 位，则间隔不会超过 16，2 16 2^{16}216也就是10 5 10^5105的枚举数量，枚举一下会填写那些块，以及不会填写哪些块，就是一个状压枚举，之后瞎搞搞就行。大致就是先填充，填充完毕后对于剩下的块排序，把多余的 k 连接上去，可以证明这里面存在最优解，主打暴力。

voidsolve(){intn,k;cin>>n>>k;intB=__lg(n)+1,z=B-__popcount(n);if(k>z){cout<<k-z+B-1<<endl;return;}vector<int>g,num;for(inti=__lg(n);i>=0;i--){if((n>>i&1)==0){intj=i-1;while(j>=0&&((n>>j&1)==0))j--;j++;g.push_back(i-j+1);num.push_back((1LL<<(i+1))-1-((1LL<<j)-1));i=j;}}intans=0LL;intM=1LL<<(int)g.size();for(intmask=0;mask<M;mask++){intm=n,co=0LL;for(intbit=0;bit<(int)g.size();bit++){if(mask>>bit&1){m|=num[bit];co+=g[bit];if(co>=k){break;}}}if(co>=k)continue;intnum=k-co,res=0;vector<int>tem;for(inti=__lg(m);i>=0;i--){if(m>>i&1){intj=i-1;while(j>=0&&(m>>j&1))j--;j++;tem.push_back(i-j+1);i=j;}}sort(range(tem),greater<int>());for(inti=0;i<min((int)tem.size(),num);i++){res+=tem[i];}res+=max(0LL,num-(int)tem.size());ans=max(ans,res);}cout<<ans<<endl;}

• 第二种思路就是 DP了，题解里面写了，再对于官方题解代码做一些解释：

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintinf=1e9+7;constintmxb=64,mxk=32;intdp[mxb+2][mxk+2][2];voidMin(int&x,inty){x=min(x,y);}voidsolve(){intn,k;cin>>n>>k;intpc=__builtin_popcount(n);if(n==0){cout<<max(0ll,k-1)<<'\n';return;}if(k>=32){cout<<k+pc-1<<'\n';return;}for(inti=0;i<=mxb;i++)for(intj=0;j<=k;j++)dp[i][j][0]=dp[i][j][1]=inf;dp[0][0][0]=0;for(inti=0;i<mxb;i++){intni=(n>>i)&1ll;for(intu=0;u<=k;u++)for(intc=0;c<=1;c++){intcur=dp[i][u][c];if(cur>=inf)continue;{intsum=ni+c,bit=sum&1,nc=sum>>1;Min(dp[i+1][u][nc],cur+bit);}if(u+1<=k){intsum=ni+1+c,bit=sum&1,nc=sum>>1;Min(dp[i+1][u+1][nc],cur+bit);}}}intbst=inf;for(intu=0;u<=k;u++)for(intc=0;c<=1;c++){intval=dp[mxb][u][c];if(val<inf)Min(bst,val+c);}intans=k+pc-bst;cout<<ans<<'\n';}signedmain(){ios_base::sync_with_stdio(false);cin.tie(0),cout.tie(0);intT;cin>>T;for(;T--;)solve();return0;}

这里 dp 表示最小的 1 的个数，从最低位 -> 最高位进行转移，d p [ i ] [ j ] [ c ] dp[i][j][c]dp[i][j][c]表示从低位开始处理到了第 i 位，进行了 j 次操作，且当前位置有没有从上一位进行进位，的最小1的个数。

sum 表示当前位考虑进位，考虑 +1 之后的值，然后 bit 表示本位最后是啥，nc 表示进位没有。

然后就转移就行了。

E. Shiro’s Mirror Duel

time limit per test: 3 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

There’s no such thing as luck in this world. The victor is decided before the game even starts.

— No Game No Life

This is an interactive problem.

One day, Sora and Shiro feel bored again, so they decide to settle it with a game.

At the beginning, Sora gives Shiro a permutation∗ ^{\text{∗}}∗p 1 , p 2 , … , p n p_1,p_2,\ldots,p_np1​,p2​,…,pn​of lengthn nn. In each operation, Shiro may select two distinct indicesx xxandy yy(1 ≤ x ≠ y ≤ n 1\le x\ne y\le n1≤x=y≤n). Then Sora flips a fair coin:

• With probability0.5 0.50.5, Sora swapsp x p_xpx​andp y p_ypy​;
• With probability0.5 0.50.5, Sora swapsp n − x + 1 p_{n-x+1}pn−x+1​andp n − y + 1 p_{n-y+1}pn−y+1​.

After the operation, Sora replies with the actual pair of indices that were swapped, so that Shiro can update her local permutation accordingly.

Shiro’s goal is to sort the permutationp ppin ascending order by using at most⌊ 2.5 n + 800 ⌋ \lfloor 2.5n+800\rfloor⌊2.5n+800⌋operations. Help her!

∗ ^{\text{∗}}∗A permutation of lengthn nnis an array consisting ofn nndistinct integers from1 11ton nnin arbitrary order. For example,[ 2 , 3 , 1 , 5 , 4 ] [2,3,1,5,4][2,3,1,5,4]is a permutation, but[ 1 , 2 , 2 ] [1,2,2][1,2,2]is not a permutation (2 22appears twice in the array), and[ 1 , 3 , 4 ] [1,3,4][1,3,4]is also not a permutation (n = 3 n=3n=3but there is4 44in the array).

题解写的很清楚的，主要思路来就是在一种看似随机的过程中找到一个等式，使得最后一定能完成，代码：

PIIquery(intx,inty){cout<<"? "<<x<<' '<<y<<endl;PII res;cin>>res.first>>res.second;returnres;}voidsolve(){intn;cin>>n;vector<int>p(n+1),pos(n+1);automirror=[&](intx)->int{returnn-x+1;};for(inti=1;i<=n;i++){cin>>p[i];pos[p[i]]=i;}if(n&1){while(pos[(n+1)/2]!=(n+1)/2){auto[u,v]=query(pos[(n+1)/2],(n+1)/2);swap(pos[p[u]],pos[p[v]]);swap(p[u],p[v]);}}for(inti=1;i<=n;i++){if(pos[i]+pos[mirror(i)]!=n+1){auto[u,v]=query(pos[i],mirror(pos[mirror(i)]));swap(pos[p[u]],pos[p[v]]);;swap(p[u],p[v]);}}for(inti=1;i<=n;i++){while(pos[i]!=i||pos[mirror(i)]!=mirror(i)){if(pos[i]!=i){auto[u,v]=query(i,pos[i]);swap(pos[p[u]],pos[p[v]]);;swap(p[u],p[v]);}else{auto[u,v]=query(mirror(i),pos[mirror(i)]);swap(pos[p[u]],pos[p[v]]);;swap(p[u],p[v]);}}}cout<<"!"<<endl;}