$\operatorname{二进制}$

题目链接：https://ac.nowcoder.com/acm/problem/213756

到主站看：https://blog.csdn.net/weixin_43346722/article/details/109953092

题目

scimoon 有一个坏掉的计算器，这个计算器仅接受 $0\sim 2^{20}-1$ 的数

这个计算器只支持一种操作，举个例子，输入一个数 $x$ ，这个数会按顺序进行 $n$ 次操作，在第 $i$ 次操作中，有一个操作符 $op_i$ 和一个数 $a_i$

如果 $op_i=1$ 表示这次操作是将数 $x$ 与 $a_i$ 做 与运算

如果 $op_i=2$ 表示这次操作是将数 $x$ 与 $a_i$ 做 或运算

如果 $op_i=3$ 表示这次操作是将数 $x$ 与 $a_i$ 做 异或运算

操作过后 $x$ 将会变为运算的结果

scimoon 觉得这个计算器非常地慢，于是他想对这 $n$ 个运算做一些简化，这个艰巨的任务交给了你

具体而言，你的任务是：用不超过 $5$ 次上面的操作，使得对于任何 $0\le x\le 2^{20}-1$ ，你的操作的输出与计算器的输出一致

可以证明必然存在解

可能存在多组解，你只需要输出一组可能的解即可

输入

第一行一个整数 $n$ ，表示计算器的操作次数

接下来 $n$ 行，每行两个整数 $op$ 与 $a$ ，按顺序描述了每次操作

输出

第一行一个 $m$ ，表示你的操作次数

你必须保证你输出的 $m\le 5$

接下来 $m$ 行每行仿照输入中 $op\ a$ 的格式输出每次操作

样例输入

1
1 14514

样例输出

1
1 14514

数据范围

$n≤5×10 ^ 5 ,1≤op≤3,0≤a≤2 ^ {20} −1$

思路

这道题。。。二进制运算吧。
挺烦的。

我们首先可以想到，如果相邻的两个运算是同一个类型，我们完全可以合并，用的运算就是他们要的运算。（就是 $a\&b\&c=a\&(b\&c)$ ）
然后我们大概也可以看出是要最后只剩下每种各一个，那我们就来看怎么弄。

首先，确定顺序：
我们来看看每个操作的本质。异或就决定要不要取反，那我们可以放在最后面。或就是它的 $1$ 会起决定性作用，那我们可以把它摆在第二个。那与就摆在第一个了。

接着我们来看每个操作中的 $1$ 和 $0$ 分别会对我们最终三个操作产生什么改变。

异或操作。由于我们最后一个操作也是异或，就可以直接合并在一起
或操作。那或操作我们就一位一位看。
如果这一位是 $0$ ，那上面试怎样就是怎样，我们不用管。
如果这一位是 $1$ ，那这一位就一定是 $1$ ，就把与和或的这一位都改成 $1$ ，异或改成 $0$
与操作。同样，也一位一位看。
如果这一位是 $1$ ，那上面试怎样就是怎样，我们不用管。
如果这一位是 $0$ ，那这一位就一定是 $0$ ，就把与、或、异或都改成 $0$ 。

那最后输出简化得到的三个运算即可。

代码

#include<cstdio>

using namespace std;

int n, huo, yu = -1, yihuo, op, a, ans[3], size[3];
bool yuyes;

int main() {
    scanf("%d", &n);
    for (int times = 1; times <= n; times++) {
        scanf("%d %d", &op, &a);

        if (op == 1) {//与操作
            if (!yuyes) {
                yuyes = 1;
                yu = a;
            }

            for (int i = 0; i <= 25; i++)
                if ((a >> i) % 2 == 0) {
                    if ((yu >> i) % 2) yu -= 1 << i;
                    if ((yihuo >> i) % 2) yihuo -= 1 << i;
                }

            continue;
        }
        if (op == 2) {//或操作
            for (int i = 0; i <= 25; i++)
                if ((a >> i) % 2) {
                    huo |= 1 << i;
                    if (yu != -1) yu |= 1 << i;
                        else yu = 1 << i;
                    if ((yihuo >> i) % 2) yihuo -= 1 << i; 
                    yuyes = 1;
                }

            continue;
        }
        if (op == 3) {//异或操作
            yihuo ^= a;
        }
    }

    if (huo != 0) {
        ans[++ans[0]] = huo;
        size[1] = 2;
    }
    if (yu != -1) {
        ans[++ans[0]] = yu;
        size[ans[0]] = 1;
    }
    if (yihuo != 0) {
        ans[++ans[0]] = yihuo;
        size[ans[0]] = 3;
    }

    printf("%d\n", ans[0]);
    for (int i = 1; i <= ans[0]; i++) printf("%d %d\n", size[i], ans[i]);

    return 0;
}