[P1985] 题解

· · 题解

位运算好题。

我们考虑将输入进来的 01 数组转换为一维数组，也就是把每一行看成一个二进制字符串再转化成数字。

这样的好处就是，中间进行操作的时候会方便很多。只需要行和行之间进行操作就可以了。

在这种情况下我们如何转化呢？可以参考整数输入的例子。

例如：我们要输入一个数组：1\ 1\ 4\ 5\ 1\ 4，我们要将其转化成变量 114514。

每次读入的时候将原先的答案 \times 10，将要输入进来的数字空出位置。

设输入的数为 x，每次只要将 a_i \times 10+x 就可以了。

同样，在 01 串下，每次可以将数字左移一位—— 111 \rightarrow 1110，再或一下新的 0/1 就可以了。

也就是 a[i] = (a[i] << 1) | x。

这样我们就解决了输入的问题。

for(int i = 1; i<=n; i++) {
    t[i] = 0;
    for(int j = 1; j<=m; j++) {
        cin>>x;
        t[i] = t[i]<<1|x;
    }
}

这里补充一下位运算的一些简单的性质。会的就不用看了。

如果想截取一个数字 x 的后 n 位（在二进制下），可以使用 x & ((1 << n) - 1) 来解决。

1<<n 代表 n 位的 10000 \cdots（共 n-1 个 0），我们如果将它 -1 这个 01串就会变成 11111 \cdots（n-1 个 1）。众所周知，与 运算符只有在两位同时为 1 的时候才会为 1，所以 x 多出 n 的那几位都会为 0，这样也就完美的截取了 x 的前 n 位。

这道题涉及一个递推的性质。

如何递推呢？只需要填出第一行，后面的就可以按照前面的贪心地来变化。

这样只要枚举第一行的所有修改可能，然后每次按照上次没有改过来的 1 尽量让他变成 0 就可以了。（贪心策略）

所以时间复杂度仅为 \mathcal{O}(2^m n)。

cz[1] = i;
for(int j = 1; j<=n; j++) a[j] = t[j];//因为a数组会改变，t数组才是初始数组
    for(int j = 1; j<=n; j++) {
        cnt+=ljp(cz[j]);//统计
        a[j]^=(cz[j]^(cz[j]>>1)^(cz[j]<<1))&((1<<m)-1);//操作当前列
        a[j+1]^=cz[j];//先操作下一行。
        cz[j+1] = a[j];//下一列的操作是这一列。
    }

然后我们要打擂台取最小，编一个函数来计算数字中有多少个 1。以此判断出是否是最优解。

你也可以使用 __builtin_popcount 来解决。

int ljp(int n) {
    int sum = 0;//计数器
    while(n>0) {
        if(n&1==1) sum++;//如果当前位是1计数器就+1
        n>>=1;//这一位看完了，看下一位。
    }
    return sum;
}

对于无解的情况下，如果答案还是原来的值，就输出 \texttt{IMPOSSIBLE}。

完整代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,x,cnt,mn = INT_MAX,ans[17],t[17],a[17],cz[17];//ans为存储答案，t为初始数组，cz为操作。
int ljp(int n) {//统计有几个1
    int sum = 0;
    while(n>0) {
        if(n&1==1) sum++;
        n>>=1;
    }
    return sum;
}
int main() {
    cin>>n>>m;
    for(int i = 1; i<=n; i++) {
        t[i] = 0;
        for(int j = 1; j<=m; j++) {
            cin>>x;
            t[i] = t[i]<<1|x;//输入操作
        }
    }
    for(int i = 0; i<(1<<m); i++) {
        cnt = 0;
        cz[1] = i;
        for(int j = 1; j<=n; j++) a[j] = t[j];
        for(int j = 1; j<=n; j++) {
            cnt+=ljp(cz[j]);
            a[j]^=(cz[j]^(cz[j]>>1)^(cz[j]<<1))&((1<<m)-1);
            a[j+1]^=cz[j];
            cz[j+1] = a[j];
        }
        if(a[n]==0&&cnt<mn) {//取最小
            mn = cnt;
            for(int k = 1; k<=n; k++) ans[k] = cz[k];//保存答案
        }
    }
    if(mn==INT_MAX) {//判断无解
        cout<<"IMPOSSIBLE"<<endl;
        return 0;
    }
    for(int i = 1; i<=n; i++) {
        for(int j = m; j>=1; j--) {
            cout<<(ans[i]>>(j-1)&1)<<' ';//输出，注意要还原。
        }
        cout<<endl;
    }
    return 0;
}