题目链接:E - Many Operations (atcoder.jp)
题目 / Problem
给定N个操作,每个操作有3种模式,与运算、或运算、异或运算,数字x初始化为C,到第i层操作的时候将x按顺序执行一遍[1, i]的所有操作,问每次完成一层后x的值。
思路 / Thought
可以将数字x的每一个二进制位都维护一个函数f[i][0 / 1],表示初始为0 / 1的二进制位上的数字经过前i次操作后变成了什么数字。
复杂度为O(W * N),W就是二进制位数,选个30就够用了。
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; bitset<32> f[2]; signed main() { ios::sync_with_stdio(0); int N, C;scanf("%lld %lld", &N, &C); f[1] = (1LL << 31) - 1; bitset<32> x(C); for(int i = 1;i <= N; ++ i) { int T, A;scanf("%lld %lld", &T, &A); if(T == 1) f[0] = f[0] & bitset<32>(A), f[1] = f[1] & bitset<32>(A); else if(T == 2) f[0] = f[0] | bitset<32>(A), f[1] = f[1] | bitset<32>(A); else if(T == 3) f[0] = f[0] ^ bitset<32>(A), f[1] = f[1] ^ bitset<32>(A); int ans = 0; for(int j = 30;j >= 0; -- j)ans = ans << 1 | (x[j] = f[x[j]][j]); printf("%lld\n", ans); } return 0; }
Comments NOTHING