【2019 CCPC 哈尔滨站 G. Game Store】【Nim-K+线性基+bitset优化三进制加法】题意分析代码

110 阅读 0 评论 73 点赞

我是靠谱客的博主健康手套，这篇文章主要介绍【2019 CCPC 哈尔滨站 G. Game Store】【Nim-K+线性基+bitset优化三进制加法】题意分析代码，现在分享给大家，希望可以做个参考。

题意

题目链接
有一个商店，商店里每天会增加一个石子集合，集合里有两堆石子数相同的石子，且每个集合有一个价格。Alice每天会在商店里选价格和尽量大的一些集合，满足把这些集合里的石子堆放在一起，然后Bob任意拿掉一些石子堆，无论Bob怎么拿，玩Nim-K游戏先手总有必胜策略。
$nle500000,a_ile 10^{18}$ ，强制在线

分析

Nim-K的结论就是，如果二进制的每一位都满足石子数这一位 $1$ 的个数是 $k + 1$ 的倍数，则先手必败，否则先手必胜。
那么很显然要维护的就是模 $3$ 意义下的最大权线性无关组，具体做法就是从枚举新加入的数的每一位非零位，如果线性基表示这一位的位置为空，则直接放上去，否则取两者之中权值较小的继续往下做。
表算还要用bitset优化三进制加法，尽管如此仍然跑的极慢，反正我用了一晚上卡常都没卡过去。

代码

复制代码

#include<bits/stdc++.h>

typedef unsigned long long LL;

const int N=65;

int n,stack[N];
LL ans,val[N],bin[N];
struct bi
{
	LL b1,b2;
	void reset() {b1=b2=0;}
	void set(int x) {if (x<60) b1|=bin[x]; else b2|=bin[x-60];}
	int get(int x) {return x<30?(b1>>(x*2))&3:(b2>>((x-30)*2))&3;}
	bi operator & (const bi &a) const {return (bi){b1&a.b1,b2&a.b2};}
	bi operator | (const bi &a) const {return (bi){b1|a.b1,b2|a.b2};}
	bi operator ^ (const bi &a) const {return (bi){b1^a.b1,b2^a.b2};}
	bi operator << (const int &x) const {return (bi){b1<<x,(b2<<x)&(bin[60]-1)};}
	bi operator >> (const int &x) const {return (bi){b1>>x,b2>>x};}
}a,vec[N],c1,c2;
 
LL read()
{
	LL x=0;char ch=getchar();
	while (ch<'0'||ch>'9'){ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x;
}

void pri(LL x)
{
	int top=0;
	if (!x) {puts("0");return;}
	while (x) stack[++top]=x%10,x/=10;
	while (top) putchar(stack[top--]+'0');
	puts("");
}

void add(LL x,LL y)
{
	a.reset();
	int top=0;
	for (int i=0;i<60&&x;i++)
	{
		if (x&1) a.set(i*2);
		x>>=1;
	}
	for (int i=59;i>=0;i--)
		if (a.get(i))
		{
			if (!val[i])
			{
				vec[i]=a;ans+=(val[i]=y);
				break;
			}
			if (val[i]<y)
			{
				ans+=y-val[i];std::swap(val[i],y);
				std::swap(a,vec[i]);
			}
			bi b=vec[i];
			if (a.get(i)==b.get(i)) b=((b&c1)<<1)^((b&c2)>>1);
			a=a^b^((a&b&c2)>>1)^((a&b&c1)<<1);
			a=a^((((a>>1)&c1)^((a<<1)&c2))&a);
		}
}

int main()
{
	bin[0]=1;
	for (int i=1;i<=60;i++) bin[i]=bin[i-1]*2;
	for (int i=0;i<60;i++) c1.set(i*2),c2.set(i*2+1);
	scanf("%d",&n);
	while (n--)
	{
		LL x=read(),y=read();
		x^=ans;y^=ans;
		add(x,y);
		pri(ans);
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>

typedef unsigned long long LL;

const int N=65;

int n,stack[N];
LL ans,val[N],bin[N];
struct bi
{
	LL b1,b2;
	void reset() {b1=b2=0;}
	void set(int x) {if (x<60) b1|=bin[x]; else b2|=bin[x-60];}
	int get(int x) {return x<30?(b1>>(x*2))&3:(b2>>((x-30)*2))&3;}
	bi operator & (const bi &a) const {return (bi){b1&a.b1,b2&a.b2};}
	bi operator | (const bi &a) const {return (bi){b1|a.b1,b2|a.b2};}
	bi operator ^ (const bi &a) const {return (bi){b1^a.b1,b2^a.b2};}
	bi operator << (const int &x) const {return (bi){b1<<x,(b2<<x)&(bin[60]-1)};}
	bi operator >> (const int &x) const {return (bi){b1>>x,b2>>x};}
}a,vec[N],c1,c2;
 
LL read()
{
	LL x=0;char ch=getchar();
	while (ch<'0'||ch>'9'){ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x;
} 

void pri(LL x)
{
	int top=0;
	if (!x) {puts("0");return;}
	while (x) stack[++top]=x%10,x/=10;
	while (top) putchar(stack[top--]+'0');
	puts("");
}

void add(LL x,LL y)
{
	a.reset();
	int top=0;
	for (int i=0;i<60&&x;i++)
	{
		if (x&1) a.set(i*2);
		x>>=1;
	}
	for (int i=59;i>=0;i--)
		if (a.get(i))
		{
			if (!val[i])
			{
				vec[i]=a;ans+=(val[i]=y);
				break;
			}
			if (val[i]<y)
			{
				ans+=y-val[i];std::swap(val[i],y);
				std::swap(a,vec[i]);
			}
			bi b=vec[i];
			if (a.get(i)==b.get(i)) b=((b&c1)<<1)^((b&c2)>>1);
			a=a^b^((a&b&c2)>>1)^((a&b&c1)<<1);
			a=a^((((a>>1)&c1)^((a<<1)&c2))&a);
		}
}

int main()
{
	bin[0]=1;
	for (int i=1;i<=60;i++) bin[i]=bin[i-1]*2;
	for (int i=0;i<60;i++) c1.set(i*2),c2.set(i*2+1);
	scanf("%d",&n);
	while (n--)
	{
		LL x=read(),y=read();
		x^=ans;y^=ans;
		add(x,y);
		pri(ans);
	}
	return 0;
}