P2114 [NOI2014] 起床困难综合症

https://www.luogu.com.cn/problem/P2114

位运算的题都考虑从高到低。那么可以确定最高位。那么就看看转移到最高位需不需要这一位为 1，然后将这一位置 1，继续下一位。

/(f[i][j],g[i][j]/) 分别表示到第 i 个操作，第 j 位能否为 1，以及能否不为 1。

/(pre[i][j]/) 表示这一位为 1 需不需要起始状态这一位为 1。

为什么是对的呢？因为 /(2^i=1+/sum_{j=0}^{i-1}2^j/)，所以贪心喽。

#include <bits/stdc++.h>
using namespace std;
inline int rd() {
	int sum=0,f=1; char ch=getchar();
	while(ch>'9'||ch<'0') {
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0') {
		sum=sum*10+ch-'0'; ch=getchar();
	}
	return sum*f;
}
const int N=(int)(1e5+5),M=29;
struct node {
	int op,v;
}a[N];
int pre[30][N];
bitset<N>f[30],g[30];
int n,m,ans;
char s[10];

void dfs(int mx,int num) {
	if(mx<0) {
		return ;
	}
	for(int i=0;i<=mx;i++) if((1<<i)+num<=m) f[i][0]=1,pre[i][0]=1;
	for(int i=0;i<=mx;i++) g[i][0]=1,pre[i][0]=-1;
	for(int i=1;i<=n;i++) {
		for(int j=0;j<=mx;j++) {
			if(a[i].op==1) {
				if((a[i].v>>j)&1) {
					if(f[j][i-1]) {
						f[j][i]=1; pre[j][i]=pre[j][i-1];
					}
					if(!f[j][i-1]||g[j][i-1]) g[j][i]=1;
				} else {
					f[j][i]=0; g[j][i]=1;
				}
			}
			if(a[i].op==2) {
				if((a[i].v>>j)&1) {
					pre[j][i]=-1; f[j][i]=1; g[j][i]=0;
				} else {
					if(f[j][i-1]) {
						f[j][i]=1; pre[j][i]=pre[j][i-1];
					}
					if(!f[j][i-1]||g[j][i-1]) g[j][i]=1;
				}
			}
			if(a[i].op==3) {
				if((a[i].v>>j)&1) {
					if(g[j][i-1]) {
						f[j][i]=1; pre[j][i]=-1;
					}
					if(f[j][i-1]) g[j][i]=1;
				} else {
					if(f[j][i-1]) {
						f[j][i]=1; pre[j][i]=pre[j][i-1];
					}
					if(!f[j][i-1]||g[j][i-1]) g[j][i]=1;
				}
			}
//			cout<<i<<' '<<j<<" "<<f[j][i]<<'/n';
		}
	}
	for(int i=mx;i>=0;i--) {
		if(f[i][n]) {
			ans+=(1<<i);
			if(pre[i][n]==1) dfs(i-1,num+(1<<i));
			else dfs(i-1,num);
			break ;
		}
	}
}

signed main() {
	n=rd(); m=rd();
	for(int i=1;i<=n;i++) {
		scanf("%s",s+1); a[i].v=rd();
		if(s[1]=='A') a[i].op=1; //and
		else if(s[1]=='O') a[i].op=2; //or
		else a[i].op=3; //xor
	}
	dfs(M,0);
	cout<<ans;
	return 0;
}