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

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

• 所以，对于每一次操作，在有影响（上面的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;
  }