题解：CF1994G Minecraft

· · 题解

CF1994G 题解

题面

原题传送门（洛谷）

原题传送门

实现

暴力

首先，看到异或，我们可以想到可以把每一位分开讨论，发现每一位的所有 a 贡献的答案为其 0 的个数或者 1 的个数，（贡献为 0 的个数则 x 对应的这一位为 1，贡献为 1 则相反）但注意，这个问题并没有这么简单，因为这是二进制加法，加法则可能会产生进位，所以我们还要维护进位的次数。

于是，就可以从个位（就是最后一位）开始往前爆搜了（至少我在我模拟赛做到这题的时候由于没时间了只好打爆搜，赛后打出正解很遗憾），每一次只要判断当前位的奇偶性是否与给定的 s 相匹配，然后就可以爆搜，这里进位二进制是逢二进一，所以进位个数应除以二，注意最高位（也就是第一位）不能再有进位！！！

于是，这就是我模拟赛的时候打出的代码。。。

代码（暴力）

v#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int MN=1e6+5;
ll n,k,sm,a[MN],t[MN],s[MN],ans[MN];
bool flag;
void write(ll n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
ll ksm(ll a, ll b){ll res=1;while(b){if(b&1)res*=a;a*=a;b>>=1;}return res;}
char gc(){char ch=getchar();while(ch!='0'&&ch!='1')ch=getchar();return ch;}
void print(ll num){for(int i=k-1; ~i; i--) write((num>>i)&1);putchar('\n');}
void dfs(ll step, ll num){
    if(flag) return; 
    if(!step&&!num){flag=true;return;}
    if(((n-t[step]+num)&1)==(s[step]&1)) ans[step]=1,dfs(step-1,(n-t[step]+num)>>1); 
    if(flag) return;
    if(((t[step]+num)&1)==(s[step]&1)) ans[step]=0,dfs(step-1,(t[step]+num)>>1);
}
void solve(){
    for(int i=1; i<=k; i++) t[i]=0,s[i]=0;
    n=read();k=read();flag=false;
    if(k<=10){sm=0;for(int i=1; i<=k; i++) sm+=ksm(2,k-i)*(gc()^48);for(int i=1; i<=n; i++){a[i]=0;for(int j=1; j<=k; j++) a[i]+=ksm(2,k-j)*(gc()^48);}for(int i=0; i<(1<<k); i++){ll num=0;for(int j=1; j<=n; j++) num+=(a[j]^i);if(num==sm){print(i);return;}}write(-1);putchar('\n');return;}
    for(int i=1; i<=k; i++) s[i]=(gc()^48);
    for(int i=1; i<=n; i++) for(int j=1; j<=k; j++) t[j]+=(gc()^48);
    dfs(k,0);
    if(!flag) write(-1);
    else for(int i=1; i<=k; i++) write(ans[i]);putchar('\n');
}
int main(){
    // freopen("raining.in","r",stdin);
    // freopen("raining.out","w",stdout);
    ll T=read();while(T--)solve();
    return 0;
}

正解

其实在考场上写爆搜的时候我就知道这是个 dp 了，考后也是实践好了。

设 dp_{i,j} 为从后往前推到了第 i 位并且当前位会对下一位产生 j 个进位的合法性，转移式子也很好写，我用的是主动转移，初始第 k+1 位进位个数为 0 是肯定有的，所以有初始化 dp_{k+1,0}\gets 1。

然后先预处理每一位上 1 的个数 t_i，那么 0 的个数也可以得出来为 n-t_i。

接下来开始枚举位数 i 和进位数 j，若有当前状态是合法的，则有如下转移：

\left\{\begin{array}{l}dp_{i-1,\lfloor\frac{t_{i-1}+j}{2}\rfloor}\gets1,(t_{i-1}+j)\bmod2=s_{i-1}\bmod2\\dp_{i-1,\lfloor\frac{n-t_{i-1}+j}{2}\rfloor}\gets1,(n-t_{i-1}+j)\bmod2=s_{i-1}\bmod2\end{array}\right.

最后只要判断 dp_{1,0} 的合法性即可。（就是第 1 位进位 0 次的情况）

如果合法，那么我们就要考虑怎么输出答案，我的做法就是每一次主动转移，被动转移方记录上答案，最后一步步调回来就好了，记这个数组为 pre，则有转移。

\left\{\begin{array}{l}pre_{i-1,\lfloor\frac{t_{i-1}+j}{2}\rfloor}\gets0,(t_{i-1}+j)\bmod2=s_{i-1}\bmod2\\pre_{i-1,\lfloor\frac{n-t_{i-1}+j}{2}\rfloor}\gets1,(n-t_{i-1}+j)\bmod2=s_{i-1}\bmod2\end{array}\right.

第一行中因为是让 1 的个数做贡献，所以要让对应的 x 为 0，第二行同理。

现在考虑如何倒推，设当前在第 i 位，第 i+1 位有 j 次进位，当前有 num 次进位，怎么从 num 推导出 j 呢，这里以第一个式子为例，第二个式子留给读者自己推。

首先由转移式子我们有 num=\lfloor\frac{t_i+j}{2}\rfloor。

而第一行成立的前提条件为 (t_i+j)\bmod2=s_{i}\bmod2。

所以我们就有 t_i+j=num\times2+s_i\bmod2。

移项得 j=num\times2+s_i\bmod2-t_i。

第二个式子同理。

所以我们从第一位跳 k 次输出答案即可，具体见代码。

实现细节

我的这种方法还是写起来有一定的细节，具体总结如下。

  1. 由于本题的空间较为刁钻，所以需要动态数组。
  2. 多测记得清空。
  3. 至于动态数组每个数据的第二维要开多少，对于每一位，其单独会产生的进位最多进 \lfloor\frac{n}{2}\rfloor 位，叠加一下，每一位最多进 \lfloor\frac{3n}{4}\rfloor 位，所以差不多开 n 就够了。

代码（正解）

提交记录

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define ll long long
using namespace std;
const int MN=2e6+5;
ll n,k,t[MN],s[MN];
vector<bool> dp[MN],pre[MN];
void write(ll n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
char gc(){char ch=getchar();while(ch!='0'&&ch!='1')ch=getchar();return ch;}
void solve(){
    for(int i=0; i<=k+1; i++) t[i]=0,s[i]=0,dp[i].clear(),pre[i].clear();
    n=read();k=read();
    for(int i=0; i<=k+1; i++) dp[i].resize(n+1),pre[i].resize(n+1);
    for(int i=1; i<=k; i++) s[i]=(gc()^48);
    for(int i=1; i<=n; i++) for(int j=1; j<=k; j++) t[j]+=(gc()^48);
    dp[k+1][0]=1;
    for(int i=k+1; i>1; i--) for(int j=0; j<=n; j++) if(dp[i][j]){
        if(((t[i-1]+j)&1)==(s[i-1]&1)) dp[i-1][(t[i-1]+j)>>1]=1,pre[i-1][(t[i-1]+j)>>1]=0;
        if(((n-t[i-1]+j)&1)==(s[i-1]&1)) dp[i-1][(n-t[i-1]+j)>>1]=1,pre[i-1][(n-t[i-1]+j)>>1]=1;
    }
    if(!dp[1][0]) write(-1);
    else{
        ll num=0;
        for(int i=1; i<=k; i++){
            write(pre[i][num]?1:0);
            if(pre[i][num]) num=(num<<1)+(s[i]&1)-n+t[i];
            else num=(num<<1)+(s[i]&1)-t[i];
        }
    }putchar('\n');
}
int main(){
    // freopen("raining.in","r",stdin);
    // freopen("raining.out","w",stdout);
    ll T=read();while(T--)solve();
    return 0;
}