【JZOJ4616】二进制的世界

description

---

analysis

• (DP)，这是(Claris)神仙的题…？

• 既然是(2^{16})可以拆成两个(2^8)的位运算

• 照着打就行了

---

code

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long
#define fo(i,a,b) for (ll i=a;i<=b;++i)
#define fd(i,a,b) for (ll i=a;i>=b;--i)

using namespace std;

ll f[260][260][2];
char opt[10];
ll n,type,ans1,ans2;

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
	while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int main()
{
	freopen("binary.in","r",stdin);
	freopen("binary.out","w",stdout);
	n=read(),scanf("%s",&opt),type=read();
	fo(j,1,n)
	{
		ll tmp=read(),x=tmp/256,y=tmp%256;
		if (j>1)
		{
			ans1=ans2=0;
			fo(i,0,255)
			{
				if (!f[i][y][1])continue;
				ll z;
				if (opt[0]=='a')z=i&x;
				else if (opt[0]=='o')z=i|x;
				else z=i^x;
				ll tot=(z<<8)+f[i][y][0];
				if (tot>ans1)ans1=tot,ans2=f[i][y][1];
				else if (tot==ans1)ans2+=f[i][y][1];
			}
			printf("%lld",ans1);
			if (type)printf(" %lld",ans2);
			printf("
");
		}
		fo(i,0,255)
		{
			ll z;
			if (opt[0]=='a')z=i&y;
			else if (opt[0]=='o')z=i|y;
			else z=i^y;
			if (z>f[x][i][0])f[x][i][0]=z,f[x][i][1]=1;
			else if (z==f[x][i][0])++f[x][i][1];
		}
	}
	return 0;
}