2020-11-14牛客小白月赛29-B

[by_041]

• 首先，题如其名，是一道关于位运算的操作题

• 内容是将一系列的位运算化简

• 很明显，位运算是有捷径的，如下：

  • 设有一个二进制第i位上是x（可能为1或0）的数
  • 与&一个第i位是1的数，这个二进制位置上的数还是原来的x
  • 与&一个第i位是0的数，这个二进制位置上的数无论如何都是0
  • 或|一个第i位是0的数，这个二进制位置上的数还是原来的x
  • 或|一个第i位是1的数，这个二进制位置上的数无论如何都是1
  • 亦或^一个数a一次就是取反二进制上a在这个位置是1的数

• 简单的说，对于一个bool量x

  1. x&1=x

  2. x&0=0

  3. x|1=1

  4. x|0=x

  5. x^1=!x

  6. x^0=x

• 所以，对于每一次操作，在有影响（上面的2、3、5三种情况）到的位置加入相应操作的标记最后整合就行

  1. 对于第i位&0的操作：清空之前该位置所有的操作，加上标记1
  2. 对于第i位|1的操作：清空之前该位置所有的操作，加上标记2
  3. 对于第i位^1的操作：查看上一步操作，若标记是3则撤销操作，否则加上标记3

• 操作保存在数组p[30][10]中，因为爽开大了，其实只要[20][4]的大小，这里吐槽一下题目，明明可以证明任何才做都能只用三次就完成的偏说五次（出题人心险恶）

• 然后最后再整合输出相应的操作数和操作就行啦~~

• 下面附上AC代码：

  #include<iostream>
  
  using namespace std;
  
  void swp(int&a,int&b)
  {a^=b;b^=a;a^=b;return;}
  int maxx(int a,int b)
  {return a>b?a:b;}
  int minn(int a,int b)
  {return a<b?a:b;}
  int input()
  {char ch=getchar();
   while(ch<'0'||ch>'9')
     ch=getchar();
   int a=ch-'0';
   while((ch=getchar())>='0'&&ch<='9')
     a=(a<<3)+(a<<1)+ch-'0';
   return a;
  }
  void output(int a)
  {
   if(a>9)
     output(a/10);
   putchar(a%10+'0');
   return;
  }
  
  int n,op,v,a1,a2,a3,a4,a5,p[30][10];
  
  int main()
  {
      n=input();
      while(n--)
      {
          op=input();
          v=input();
          if(op^1)
          {
              for(int i=0;v;i++,v>>=1)
              {
                  if(op==2&&(v&1))
                  {
                      p[i][(*p[i])=1]=2;
                      continue;
                  }
                  if(op==3&&(v&1))
                  {
                      if(p[i][*p[i]]==3)
                          (*p[i])--;
                      else p[i][++(*p[i])]=3;
                      continue;
                  }
              }
          }
          else
          {
              for(int i=0;i<=20;i++,v>>=1)
              {
                  if((v&1)==0)
                      p[i][(*p[i])=1]=1;
              }
          }
      }
      for(int i=0,k=0;i<=20;i++,k=0)
          {
              for(int j=1;j<=(*p[i]);j++)
                  {
                      if(p[i][j]==1)
                          {
                              a1+=(1<<i);
                              continue;
                          }
                      if(p[i][j]==2)
                          {
                              a2+=(1<<i);
                              continue;
                          }
                      if(p[i][j]==3)
                          {
                              k=1;
                              a3+=(1<<i);
                              continue;
                          }
                  }
          }
      printf("%d\n",(bool)a1+(bool)a2+(bool)a3+(bool)a4+(bool)a5);
      if(a1)printf("1 %d\n",(~a1)&(0xfffff));
      if(a2)printf("2 %d\n",a2);
      if(a3)printf("3 %d\n",a3);
      return 0;
  }