LOJ#2244 起床困难综合症-LMLPHP

LOJ#2244 起床困难综合症-LMLPHPLOJ#2244 起床困难综合症-LMLPHP

解:m = 0的部分分,直接模拟。有and 0的部分分,直接模拟。<=1000的部分分,枚举攻击力之后模拟。所有操作相同的部分分,可以合并成只有一个操作。然后枚举m或者逐位贪心。

正解是逐位贪心,内层跑一遍1~n个操作。然后后面这个1~n其实可以优化,在外层用00000...0和11111...1来一次性搞完即可。

 #include <bits/stdc++.h>

 const int N = ;

 int a[N], opt[N], n, m;
char str[]; /// 0 AND & 1 OR | 2 XOR ^ namespace m0 {
inline void solve() {
int ans = ;
for(int i = ; i <= n; i++) {
if(opt[i] == ) {
ans = ans & a[i];
}
else if(opt[i] == ) {
ans = ans | a[i];
}
else if(opt[i] == ) {
ans = ans ^ a[i];
}
}
printf("%d\n", ans);
return;
}
} namespace bf {
inline void solve() {
int ans = ;
for(int i = ; i <= m; i++) {
int x = i;
for(int j = ; j <= n; j++) {
if(opt[j] == ) {
x = x & a[j];
}
else if(opt[j] == ) {
x = x | a[j];
}
else {
x = x ^ a[j];
}
}
ans = std::max(ans, x);
}
printf("%d\n", ans);
return;
}
} namespace same {
inline void solve() {
int x = a[];
for(int i = ; i <= n; i++) {
if(opt[i] == ) {
x = x & a[i];
}
else if(opt[i] == ) {
x = x | a[i];
}
else {
x = x ^ a[i];
}
}
int ans = ;
if(m <= ) {
for(int i = ; i <= m; i++) {
if(opt[] == ) {
ans = std::max(ans, i & x);
}
else if(opt[] == ) {
ans = std::max(ans, i | x);
}
else if(opt[] == ) {
ans = std::max(ans, i ^ x);
}
}
}
else {
int now = ;
for(int i = ; i >= ; i--) {
if(opt[] == ) {
if(((x >> i) & ) && (now | ( << i)) <= m) {
now |= ( << i);
}
}
else if(opt[] == ) {
if(((x >> i) & ) == && (now | ( << i)) <= m) {
now |= ( << i);
}
}
else {
if(((x >> i) & ) == && (now | ( << i)) <= m) {
now |= ( << i);
}
}
}
if(opt[] == ) {
ans = x & now;
}
else if(opt[] == ) {
ans = x | now;
}
else {
ans = x ^ now;
}
}
printf("%d\n", ans);
return;
}
} int main() {
bool flag1 = false, flag2 = true;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) {
scanf("%s%d", str, &a[i]);
if(str[] == 'O') opt[i] = ;
else if(str[] == 'X') opt[i] = ;
else if(a[i] == ) {
flag1 = true;
}
if(i > && opt[i] != opt[i - ]) {
flag2 = false;
}
} if(!m || flag1) {
m0::solve();
return ;
}
if(n <= && m <= ) {
bf::solve();
return ;
}
if(flag2) {
same::solve();
return ;
} int ans = , now = ;
for(int i = ; i >= ; i--) {
int t1 = , t0 = ;
for(int j = ; j <= n; j++) {
if(opt[j] == ) {
t0 &= (a[j] >> i) & ;
t1 &= (a[j] >> i) & ;
}
else if(opt[j] == ) {
t0 |= (a[j] >> i) & ;
t1 |= (a[j] >> i) & ;
}
else {
t0 ^= (a[j] >> i) & ;
t1 ^= (a[j] >> i) & ;
}
}
if(t0) {
ans |= ( << i);
}
else if(t1 && (now | ( << i)) <= m) {
now |= ( << i);
ans |= ( << i);
}
}
printf("%d\n", ans);
return ;
}

AC代码

05-11 21:51