Atcoder beginer contest 261e / / bitwise thinking + DP

Topic link ：E - Many Operations (atcoder.jp)

The question ：

Give a number x, as well as n Operations （ti,ai）：

• When t = 1 when , take x & a

• When t = 2 when , take x | a

• When t = 3 when , take x ^ a

And print them separately n Number ：x Before proceeding 1 Print after operation , Go further before 2 Print after operation ,... , Go further before n Print after operation .

Ideas ：

because x、ai All less than  , Every operation is a bit operation , Then think according to each binary , At most 30 bits , The initial value of each can only be 0、1, Just preprocess it first , Each is initially 0、1 when , Before proceeding i Time （1~n） The value after operation , You can quickly find any number for front i The value after the first operation .

Code ：

//dp
#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

int n, x, t[N], a[N];
bool f[N][30][2];  //fi,j,k： For the second j position , For the initial k Under the circumstances , Before proceeding i The value after the first operation 

int main()
{
    cin >> n >> x;
    for(int i = 1; i <= n; i++) scanf("%d%d", &t[i], &a[i]);

    for(int i = 0; i < 30; i++) f[0][i][0] = 0, f[0][i][1] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < 30; j++)
            for(int k = 0; k < 2; k++) 
                if(t[i] == 1) f[i][j][k] = f[i - 1][j][k] & (a[i] >> j & 1);
                else if(t[i] == 2) f[i][j][k] = f[i - 1][j][k] | (a[i] >> j & 1);
                else if(t[i] == 3) f[i][j][k] = f[i - 1][j][k] ^ (a[i] >> j & 1);
    
    for(int i = 1; i <= n; i++)
    {
        int res = 0;
        for(int j = 0; j < 30; j++) res += f[i][j][x >> j & 1] << j;
        printf("%d\n", x = res);
    }

    return 0;
}