牛客小白月赛29 B 二进制 题解

Description

给出一堆的按位操作运算，构造五次以内的三种按位操作——，， 使得最终结果与原来的操作相同。

Solution

时隔一个月?回来做这道当时不会做的构造题。
考虑二进制上的每一位，无论他原来是 还是 ，我们只需要构造经过一系列的变换后每一位保证与原来的操作相同即可。
于是只需要考虑三次操作，分别进行，，
其中操作数需要对原来的操作序列进行模拟，然后得出结果。
具体方法如下：对于每一位取该位 和
经过操作序列的作用后

• 该位需要做一次或运算
• 该位需要做一次异或运算
• 需要做一次与运算

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
typedef long long ll;
int op[N], r[N];
int ansl[N], ansr[N];
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
  int n; cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> op[i] >> r[i];
  }
  int op1 = 0, op2 = 0, op3 = 0;
  int ans = 0;
  for(int i = 0; i < 20; i++) {
    int x = 0, y = (1 << i);
    for(int j = 1; j <= n; j++) {
      if(op[j] == 1) {
        x &= r[j], y &= r[j];
      } else if(op[j] == 2) {
        x |= r[j], y |= r[j];
      } else {
        x ^= r[j], y ^= r[j];
      }
    }
    x = ((x >> i) & 1), y = ((y >> i) & 1);
    if(x || y) { // 有至少一个为1, 取与运算, 保证该位能为1
      op1 += (1 << i);
    }
    if(x && y) { // 都为1 用或运算
      op2 += (1 << i);
    } 
    if(x && !y) { // x该为是0, 现在变成了1, y该位是1, 现在是0,取了异或
      op3 += (1 << i);
    }
  }
  cout << 3 << '\n';
  cout << 1 << ' ' << op1 << '\n';
  cout << 2 << ' ' << op2 << '\n';
  cout << 3 << ' ' << op3 << '\n';
  return 0;
}