P6751 [IOI2019] 视觉程序题解

chen_03 · 2020-12-26 18:17:22 · 题解

我的做法是二进制加法器。似乎大多数人都不是这个做法？

首先，查询每一行、每一列的异或和。

以每一行为例，如果两个黑色像素在同一行，那么所有行的异或和都为 0；如果不在同一行，则它们所在的行的异或和为 1，黑色像素的竖直距离就是这两个 1 之间的距离。

如果我们把这个异或和再做一遍前缀异或和，那么黑色像素的竖直距离就是前缀异或和中 1 的数量。我们只要想办法统计 1 的数量即可。

每一列同理。注意到行的前缀异或和中，最后一个数一定为 0，所以我们可以把行和列的前缀异或和放在一起统计。

那么如何统计前缀异或和中 1 的数量呢？

我们想到了二进制加法器：从 0 开始，把前缀异或和中的数一个一个地加上去。实现起来，就是维护每一位上的数字分别是什么，以及每一位上有没有进位。由于每次加法都是加 0 或 1，所以每次进位操作可以只用一个指令。

我们要统计的数（距离）最多为 H+W-2\le 398，有 9 个二进制位，所以每次加法用 9 个指令维护每一位上的数字，用 8 个指令维护每一位上有没有进位（最高位上一定不会进位）。每一位上的数字用异或操作维护，进位用与操作维护。

统计出 1 的数量后，我们把它与 K 一位一位地进行比较。把每一位都异或一下，把异或操作的结果或起来，再取非即可。此前要用某种方法搞出一个结果一定为 0 的指令和一个结果一定为 1 的指令。

我的代码使用的指令数最多为 7200+，读入值的数量最多不超过 10^5，可以轻松通过本题。当然这个数量可以继续优化，但没必要。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int add_not(int);
int add_and(vector<int> Ns);
int add_or(vector<int> Ns);
int add_xor(vector<int> Ns);
int n,m,k,cnt,zero,one;
vector<int> vec;
inline void add(int pos){
    int bg=cnt-16;
    add_xor({bg,pos});
    cnt=add_and({bg,pos});
    for(int i=1;i<8;++i){
        add_xor({bg+i*2,cnt});
        cnt=add_and({bg+i*2,cnt});
    }
    cnt=add_xor({bg+16,cnt});
}
void construct_network(int H,int W,int K){
    n=H;m=W;k=K;
    vec.resize(m);
    for(int i=0;i<m;++i)vec[i]=i;
    cnt=add_xor(vec);
    vec.resize(m+1);
    for(int i=1;i<n;++i){
        for(int j=0;j<m;++j)vec[j]=i*m+j;
        vec[m]=cnt;
        cnt=add_xor(vec);
    }
    vec.resize(n+1);
    for(int i=0;i<m;++i){
        for(int j=0;j<n;++j)vec[j]=j*m+i;
        vec[n]=cnt;
        cnt=add_xor(vec);
    }
    zero=add_xor({0,0});
    for(int i=1;i<17;++i)
        cnt=add_or({zero});
    for(int i=n*m;i<n*m+n+m;++i)add(i);
    int bg=cnt-16;
    vec.resize(9);
    one=add_not(zero);
    for(int i=0;i<9;++i)
        vec[i]=add_xor({bg+2*i,(k>>i)&1?one:zero});
    add_not(add_or(vec));
}

P6751 [IOI2019] 视觉程序 题解

P6751 [IOI2019] 视觉程序题解