2 seconds
256 megabytes
standard input
standard output
Petya learned a new programming language CALPAS. A program in this language always takes one non-negative integer and returns one non-negative integer as well.
In the language, there are only three commands: apply a bitwise operation AND, OR or XOR with a given constant to the current integer. A program can contain an arbitrary sequence of these operations with arbitrary constants from 0 to 1023. When the program is run, all operations are applied (in the given order) to the argument and in the end the result integer is returned.
Petya wrote a program in this language, but it turned out to be too long. Write a program in CALPAS that does the same thing as the Petya’s program, and consists of no more than 5 lines. Your program should return the same integer as Petya’s program for all arguments from 0 to 1023.
The first line contains an integer n (1 ≤ n ≤ 5·105) — the number of lines.
Next n lines contain commands. A command consists of a character that represents the operation (“&“, “|” or “^” for AND, OR or XOR respectively), and the constant xi 0 ≤ xi ≤ 1023.
Output an integer k (0 ≤ k ≤ 5) — the length of your program.
Next k lines must contain commands in the same format as in the input.
|
1 2 3 4 |
3 | 3 ^ 2 | 1 |
|
1 2 3 |
2 | 3 ^ 2 |
|
1 2 3 4 |
3 & 1 & 3 & 5 |
|
1 2 |
1 & 1 |
|
1 2 3 4 |
3 ^ 1 ^ 2 ^ 3 |
|
1 |
0 |
You can read about bitwise operations in https://en.wikipedia.org/wiki/Bitwise_operation.
Second sample:
Let x be an input of the Petya’s program. It’s output is ((x&1)&3)&5 = x&(1&3&5) = x&1. So these two programs always give the same outputs.
题意
给n步与，或，异或计算，然后求五步以内的等同与，或，异或计算。
思路
位运算的时候每一个bit的运算的都是彼此独立的，然后对于每一个bit上的n次同一位运算（与计算或者或计算或者异或计算）都可以用一个bit上的一次位运算来表示，也就是说对于题目中的情况最多只用三次位运算即可，可用公式描述：
\(\begin{equation} \begin{aligned}f(x) = \ & xAND({xa_1})AND({xa_2})AND({xa_3})…\\&\ OR({xo_1})OR({xo_2})OR({xo_3})…\\&\ XOR({xx_1})XOR({xx_2})XOR({xx_3})…\\ =\ &xAND({xa_i}) OR({xo_j})XOR({xx_k}), \ (0\leq x \leq 1023)\end{aligned}\end{equation}\)
关键就在于找到哪一个bit上要进行哪一种位运算，即找到\({xa_i},{xo_j},{xx_k}\)，又因为位运算每个bit彼此独立的特点，要想模拟出所有bit的计算，只需要模拟\(f(0)\)和\(f(1023)\)即cover住所有case，对于\(f(0)\)和\(f(1023)\)又存在下列对应关系：
\(f(0)=1, f(1023) = 1 \Rightarrow {xa_i}=1, {xo_j}=1, {xx_k}=0 \)
\(f(0)=1, f(1023) = 0 \Rightarrow {xa_i}=1, {xo_j}=0, {xx_k}=1 \)
\(f(0)=0, f(1023) = 1 \Rightarrow {xa_i}=1, {xo_j}=0, {xx_k}=0 \)
\(f(0)=0, f(1023) = 0 \Rightarrow {xa_i}=0, {xo_j}=0, {xx_k}=0 \)
所以就是先模拟所有的位运算，最后基于\(f(0)=1, f(1023) = 1 \Rightarrow {xa_i}=1, {xo_j}=1, {xx_k}=0 \)即可求得\({xa_i},{xo_j},{xx_k}\)。
需要注意的是最后的输出结果并不唯一，只要符合题目要求即可，不一定跟样例输出保持一致。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
/* * File Name: 879C.cpp * Author: razrLeLe * Mail: razrlele@gmail.com */ #include <vector> #include <set> #include <deque> #include <queue> #include <algorithm> #include <functional> #include <iostream> #include <cstdio> #include <cmath> #include <cstdlib> #include <string> #include <cstring> #include <string.h> #include <map> #include <cctype> #include <list> #include <stack> #define ll long long using namespace std; #define INF 0x3f3f3f3f #define LOCAL int main(int argc, char ** argv) { #ifdef LOCAL freopen("/Users/razrlele/build/in.data", "r", stdin); //freopen("/Users/razrlele/build/out.data", "w", stdout); #endif int n; int num_and, num_or, num_xor; num_and = 0, num_or = 0, num_xor = 0; int x = 0, y = 0x3ff; char op; int op_num; scanf("%d", &n); for (int i = 0; i < n; i++){ getchar(); scanf("%c%d", &op, &op_num); switch(op) { case '&': x &= op_num, y &= op_num; break; case '|': x |= op_num, y |= op_num; break; case '^': x ^= op_num, y ^= op_num; break; default: break; } } for (int i = 0; i < 10; i++) { int bit = 1 << i; if (x & bit) { if( y & bit){ num_and |= bit; num_or |= bit; } else { num_and |= bit; num_xor |= bit; } } else { if (y & bit) { num_and |= bit; } } } printf("3\n"); printf("& %d\n", num_and); printf("| %d\n", num_or); printf("^ %d\n", num_xor); return 0; } |