起床困难综合症
题意
drd 的防御战线由 n 扇防御门组成。
每扇防御门包括一个运算 op 和一个参数 t，其中运算一定是 OR,XOR,AND 中的一种，参数则一定为非负整数。
如果还未通过防御门时攻击力为 x，则其通过这扇防御门后攻击力将变为 x op t。
最终 drd 受到的伤害为对方初始攻击力 x 依次经过所有 n 扇防御门后转变得到的攻击力。
由于 atm 水平有限，他的初始攻击力只能为 0 到 m 之间的一个整数（即他的初始攻击力只能在 0,1,…,m 中任选，但在通过防御门之后的攻击力不受 m 的限制）。
为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使 drd 受到多少伤害。
思路
这道题的前提是 位运算的主要特点之一是在二进制表示下不进位
所以假设我们选择的初始值为x 那么我们可以分别考虑 x 的每一位应该选择 0 还是 1
最后组合到一起，就得到了最终的 x
那么第 k 位 选 1 还是 0 呢？
对于下面两种情况 选择 1 更优
已经填好的更高位的数值加上 1 << k 小于等于 m。
初始值为 1 得到的最终值比初始值为 0 得到的最终值大
若不满足上面两个条件，那么肯定是选 0 更优
每一位都确定好之后，就可以得到答案
代码
#include<bits/stdc++.h> // #define int long long #define INF 0x3f3f3f3f #define mod 1000000007 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) using namespace std; typedef long long LL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } const int N = 1e5 + 10; int n, m; pair<string, int>a[N]; int cal(int bit, int x) { for (int i = 1; i <= n; ++i) { int k = a[i].second >> bit & 1; if (a[i].first == "AND") x &= k; else if (a[i].first == "OR") x |= k; else x ^= k; } return x; } void solve() { cin >> n >> m; for (int i = 1; i <= n; ++i) { string str; int x; cin >> str >> x; a[i] = { str,x }; } int res = 0, val = 0; for (int i = 29; i >= 0; --i) { int res0 = cal(i, 0); int res1 = cal(i, 1); if (val + (1 << i) <= m && res0 < res1) { val += 1 << i; res += res1 << i; } else res += res0 << i; } cout << res << endl; } signed main() { // int t; cin >> t; // while (t--) solve(); return 0; }
