宏量运算｜动态规划前缀和

第五题 - Many Operations

题目跳转：宏量运算。

一道位运算的恶心题目，跟上一题一样，可以用前缀和动态规划的思想来解决。因为每一位都是相互独立的，所以只需要按位进行 $\mathtt{dp}$ 预处理就可以了。定义状态 $dp_{i, j(0/1), k}$ 表示对于第 $i$ 位来说，一开始的值为 $j(0/1)$，经过前 $k$ 次操作后这一位的值。而状态转移方程就是 $dp_{i, j, k} = dp_{i, j, k-1}$。之后不断迭代就可以求出最后的解。

本题的主要难点是位运算的一些操作，有些同学对位运算的操作不太熟悉，这里提供一些常见的位运算操作：

1. 获取一个数字的第 $j$ 位：(x >> j) & 1。
2. 判断数字是否是奇数：x & 1。
3. 将一个数字乘上 $2^j$：(1 << j) * x。

本题的时间复杂度约为 $\Theta(60N)$。

因此，本题的 AC 代码如下：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 2e5 + 5;
int n, c;
int dp[50][5][N];
int t[N], a[N];

signed main(){
    cin >> n >> c;
    for (int i=1; i<=n; i++)
        cin >> t[i] >> a[i];
    // cout << log2(1e9) << endl; 
    for (int i=0; i<30; i++){
        for (int j=0; j<2; j++){
            dp[i][j][0] = j;
            for (int k=1; k<=n; k++){
                // 三种状态，分别判断一下就可以了了。
                bool x = a[k] & (1 << i);
                if (t[k] == 1) dp[i][j][k] = dp[i][j][k-1] & x;
                else if (t[k] == 2) dp[i][j][k] = dp[i][j][k-1] | x;
                else dp[i][j][k] = dp[i][j][k-1] ^ x;
            }
        }
    }
    for (int i=1; i<=n; i++){
        int ans = 0, k = c;
        for (int j=0; j<30; j++) {
            // 基础位运算操作。
            ans += dp[j][k & 1][i] * (1 << j);
            k >>= 1;
        }
        cout << ans << endl;
        c = ans;
    }
    return 0;
}