jzoj 4616. 【NOI2016模拟7.12】二进制的世界

Question

Solution

这题考场就打了个暴力。
结果有人$O(2^{16}*n)$过了。。。
正解是“折半”，$O(2^8*n)$
我们设$f[i][j]$：
有两个数$x,y$。
$x=a*256+b$
$y=c*256+d$
（此处的$i$就表示a，$j$就表示$d$）
$f[i][j]$就表示这样情况下的后八位操作后的最大值，
而$g[i][j]$表示其方案数。

加入操作：

我们设当前加入的数为$x$，$x=a*256+b$
我们枚举一个$d$（就是上述的$d$）
我们将所有的$f[a][d]$与$b$ $opt$ $d$取$max$

查询操作：

我们设要查询的数为$x$，$x=a*256+b$
我们枚举一个$c$（就是上述的$c$）
我们对于一个$f[c][b]$，前八位直接用$a$ $opt$ $c$得到，后八位则是用$f[c][b]$来得到的。
也就是说，我们设$k=(a$ $opt$ $c)*256+f[c][b]$，然后将$k$与答案$ans$进行比较即可。

Code

#include<cstdio>
#define N 100010
using namespace std;
int n,type,a[N],le,ri,s1,s2;
int ma[261][261],hav[261][261];
char s[5];

inline int read()
{
	int x=0; char c=getchar();
	while (c<'0' || c>'9') c=getchar();
	while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}

inline int get(int x,int y)
{
	if (s[1]=='a') return x&y;
	if (s[1]=='o') return x|y;
	if (s[1]=='x') return x^y;
}

int main()
{
	freopen("binary.in","r",stdin);
	freopen("binary.out","w",stdout);
	n=read(),scanf("%s",s+1),type=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=1,k;i<=n;i++)
	{
		le=a[i]/256,ri=a[i]%256;
		if (i!=1)
		{
			s1=s2=0;
			for (int j=0;j<=255;j++)
			{
				if (!hav[j][ri]) continue;
				k=get(le,j)*256+ma[j][ri];
				if (s1<k) s1=k,s2=hav[j][ri];
				else if (s1==k) s2+=hav[j][ri];
			}
			if (type==1) printf("%d %d
",s1,s2);
			else printf("%d
",s1);
		}
		for (int j=0;j<=255;j++)
		{
			k=get(ri,j);
			if (ma[le][j]==k) hav[le][j]++;
			else if (ma[le][j]<k) ma[le][j]=k,hav[le][j]=1;
		}
	}
	return 0;
}