Luogu1275魔板

搜索 bitset

题面

有这样一种魔板：它是一个长方形的面板，被划分成$n$行$m$列的$n*m$个方格。每个方格内有一个小灯泡，灯泡的状态有两种(亮或暗)。我们可以通过若干操作使魔板从一个状态改变为另一个状态。操作的方式有两种：
（1）任选一行，改变该行中所有灯泡的状态，即亮的变暗、暗的变亮；
（2）任选两列，交换其位置。
你的任务就是根据给定两个魔板状态，判断两个状态能否互相转化。

解析

首先一眼看出个性质：每行亮的灯泡数只可能有两种或一种。
（然而这并没有什么卵用）
正经一点，这题状态只有$0$、$1$，$bitset$走起。
然后我由于列可任意交换，我们可以把列按字典序排序。
再枚举一下看有没有列能成为目标状态第一列即可。
在判定过程中，如果一行数字不同就翻转，到最后再排序，如果后面的列能一一对应就$yes$，否则继续。
（核心思想就是在模拟时，你只能把一行翻转一次，否则为后面翻转时会改变前面的）

int k,n,m,ans;
bitset<105>a[105],b[105],c;
il bool cmp(bitset<105>x,bitset<105>y)
{
  fp(i,1,n) if(x[i]^y[i]) return x[i]<y[i];
  return 0;
}
int main()
{
  //freopen("panel.in","r",stdin);
  //freopen("panel.out","w",stdout);
  k=gi();
  while(k--)
    {
      n=gi();m=gi();ans=0;
      fp(i,1,m) a[i].reset(),b[i].reset();
      fp(i,1,n) fp(j,1,m) a[j][i]=gi();
      fp(i,1,n) fp(j,1,m) b[j][i]=gi();
      sort(a+1,a+1+m,cmp);sort(b+1,b+1+m,cmp);
      fp(i,1,m)
    {
      c=a[i]^b[1];
      fp(j,1,m) a[j]^=c;
      sort(a+1,a+1+m,cmp);
      re int flag=1;
      fp(j,1,m) if(a[j]!=b[j]) {flag=0;break;}
      if(flag) {ans=1;break;}
      fp(j,1,m) a[j]^=c;
      sort(a+1,a+1+m,cmp);
    }
      puts(ans?"YES":"NO");
    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}