给出一个(4 imes 4)的网格图，网格图上的数字由0,1组成，每次操作可以选择一个位置，让该个位置所在的一行上，一列上所有的数字1变为0,0变为1,给出一个初始局面，询问最少的操作让所有数字变为0。
解
这是一道类异或问题，因此对于一个位置的重复操作是没有意义的，现在问题转化为对那些位置操作了。
网格图问题，按行处理的话，注意到一个位置上的改变，引起了每一行的改变，于是无法剪枝，只有16个格子，(2^{16}=65536)，不如直接暴力枚举。
于是用二进制枚举，将网格图拆行成列，二进制上的每一位对应了网格图上的一个位置是否进行操作（至于怎么对应，按你自己习惯），但是为了快速变换，实现预处理出点击一个位置，会对哪些格子造成改变，直接二进制下的位运算就体现了点击这个位置局面的改变，随便事先统计好每个数二进制位下1的个数，这样就可以做到(O(2^{16} imes 16)=1048576)。
参考代码：
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define li 65536
#define intmax 0x7fffffff
using namespace std;
int t[16],tot[li];
il void get(char&);
int main(){
for(int i(0),j,k,l;i<4;++i)
for(j=0;j<4;++j)
for(k=0;k<4;++k)
t[i*4+j]|=1<<k+i*4,
t[i*4+j]|=1<<j+k*4;
for(int i(0),j;i<li;++i)
for(j=15;j>=0;--j)
if(i>>j&1)++tot[i];
char c;int ans(intmax),gzy,s(0);
for(int i(0);i<16;++i)
get(c),s|=(c=='-'?0:1)<<i;
for(int i(0),j,k;i<li;++i){
if(tot[i]>=ans)continue;
for(j=15,k=s;j>=0;--j)
if(i>>j&1)k^=t[j];
if(!k)ans=tot[i],gzy=i;
}printf("%d
",ans);
for(int i(0);i<16;++i)
if(gzy>>i&1)
printf("%d %d
",i/4+1,i%4+1);
return 0;
}
il void get(char &c){
while(c=getchar(),c==' '||c=='
'||c=='
');
}