Reku
0%

SG函数

Posted on Edited on In Views: Valine:

唉...今天又学习了一下SG函数...都是之前挖的坑QAQ

Have you ever played Overwatch? Mercy, a female hero in the game, is the guardian angel of the whole team. Her Valkyrie Suit helps keep her close to teammates like healing, resurrecting or strengthening them with the beams emanating from her Caduceus Staff. Alice and Bob are two crazy players of this Blizzard's new game. They both love using the hero Mercy. One day, they want to figure out who is the best angel. So they come for you. There are three teams to be saved. Alice and Bob take turns to save them. In one turn, they can only select one team and heal n people. n's value is chosen from the Fibonacci array(1,2,3,5,8...) Alice and Bob are both eager to become the best angel. And they will adopt the best strategy. The one who saves all the remaining teammates will be the winner. Your job is to judge who is the best angel. Input There are multiple cases(no more than 100) in the input file. On the first line, there is only one integer T, representing the number of test cases. In each case, there are three numbers x, y, z, representing the numbers of teammates in three teams. x, y, z <= 100000 Output For each case, if the offensive(first to select) will always win, then the best angel is Alice. Otherwise, output Bob. Sample Input 2 1 4 1 1 1 1 Sample Output Bob Alice

竟然会考这种SG函数裸题...

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
#include<bits/stdc++.h>
using namespace std;
int f[100010]={};
bool t[100010]={};
vector<int> ff;
int a,b;
int main()
{
    a=1; b=2;
    ff.push_back(1);
    while(a<=100000&&b<=100000)
    {
        ff.push_back(b);
        int c;
        c=a;
        a=b;
        b=c+b;
    }
    f[0]=0;
    for(int i=1;i<=100000;i++)
    {
    	memset(t,0,sizeof(t));
        bool bj=0;
        for(int j=0;j<ff.size();j++)
        {
            if(i-ff[j]>=0)
            {
                t[f[i-ff[j]]]=1;
            }
        }
        for(int j=0;j<=100000;j++)
        {
        	if(t[j]==0)
        	{
        		f[i]=j;
        		break;
			}
		}
    }
    int T;
    int x,y,z;
    cin>>T;
    while(T--)
    {
        cin>>x>>y>>z;
        int ans;
        ans=f[x]^f[y]^f[z];
        if(ans!=0) cout<<"Alice"<<endl;
        else cout<<"Bob"<<endl;
    }
    return 0;
}

http://www.lydsy.com/JudgeOnline/problem.php?id=1874

Description

小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的，每个人每次可以从一堆石子中取出若干个石子，每次取石子的个数有限制，谁不能取石子时就会输掉游戏。 小H先进行操作，他想问你他是否有必胜策略，如果有，第一步如何取石子。 Input

输入文件的第一行为石子的堆数N 接下来N行，每行一个数Ai，表示每堆石子的个数 接下来一行为每次取石子个数的种类数M 接下来M行，每行一个数Bi，表示每次可以取的石子个数，输入保证这M个数按照递增顺序排列。 Output

输出文件第一行为“YES”或者“NO”，表示小H是否有必胜策略。 若结果为“YES”,则第二行包含两个数，第一个数表示从哪堆石子取，第二个数表示取多少个石子，若有多种答案，取第一个数最小的答案，若仍有多种答案，取第二个数最小的答案。

简单sg函数判断一下就行

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
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[15],b[15];
int p[1010];
bool v[1010];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>b[i];
	}
	for(int i=1;i<=1000;i++)
	{
		memset(v,0,sizeof(v));
		for(int j=1;j<=m;j++)
		{
			if(i-b[j]>=0)
			{
				v[p[i-b[j]]]=1;
			}
		}
		for(int j=0;j<=1000;j++)
		{
			if(v[j]==0)
			{
				p[i]=j;
				break;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans^=p[a[i]];
	}
	if(ans==0)
	{
		cout<<"NO"<<endl;
		return 0;
	}
	cout<<"YES"<<endl;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i]-b[j]>=0)
			{
				int ans=0;
				for(int k=1;k<=n;k++)
				{
					if(k!=i) ans^=p[a[k]];
					else ans^=p[a[k]-b[j]];
				}
				if(ans==0)
				{
					cout<<i<<" "<<b[j]<<endl;
					return 0;
				}
			}
		}
	}
	return 0;
}

http://www.lydsy.com/JudgeOnline/problem.php?id=1188

Description

聪聪和睿睿最近迷上了一款叫做分裂的游戏。 该游戏的规则试： 共有 n 个瓶子， 标号为 0,1,2.....n-1, 第 i 个瓶子中装有 p[i]颗巧克力豆，两个人轮流取豆子，每一轮每人选择 3 个瓶子。标号为 i,j,k, 并要保证 i < j , j < = k 且第 i 个瓶子中至少要有 1 颗巧克力豆，随后这个人从第 i 个瓶子中拿走一颗豆 子并在 j,k 中各放入一粒豆子（j 可能等于 k） 。如果轮到某人而他无法按规则取豆子，那么他将输 掉比赛。胜利者可以拿走所有的巧克力豆！ 两人最后决定由聪聪先取豆子，为了能够得到最终的巧克力豆，聪聪自然希望赢得比赛。他思考 了一下，发现在有的情况下，先拿的人一定有办法取胜，但是他不知道对于其他情况是否有必胜 策略，更不知道第一步该如何取。他决定偷偷请教聪明的你，希望你能告诉他，在给定每个瓶子 中的最初豆子数后是否能让自己得到所有巧克力豆，他还希望你告诉他第一步该如何取，并且为 了必胜，第一步有多少种取法？ 假定 1 < n < = 21,p[i] < = 10000

Input

输入文件第一行是一个整数t表示测试数据的组数，接下来为t组测试数据（t<=10）。每组测试数据的第一行是瓶子的个数n，接下来的一行有n个由空格隔开的非负整数，表示每个瓶子中的豆子数。

Output

对于每组测试数据，输出包括两行，第一行为用一个空格两两隔开的三个整数，表示要想赢得游戏，第一步应该选取的3个瓶子的编号i,j,k，如果有多组符合要求的解，那么输出字典序最小的一组。如果无论如何都无法赢得游戏，那么输出用一个空格两两隔开的三个-1。第二行表示要想确保赢得比赛，第一步有多少种不同的取法。

挺有意思的一道题 把每个石子看做一个单独的博弈游戏，该石子的sg函数值是mex{sg[j]^sg[k] (j和k为所有合法的选择)} 然后当a[i]为偶数时，显然所有的sg异或和会抵消消失，当a[i]为奇数时，只需要求一次异或和就可以了

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
#include<bits/stdc++.h>
using namespace std;
void work()
{
	int n;
	int a[25]={};
	int sg[25]={};
	bool t[25*25]={};
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=n;i>=1;i--)
	{
		memset(t,0,sizeof(t));
		for(int j=n;j>i;j--)
		{
			for(int k=n;k>=j;k--)
			{
				t[sg[j]^sg[k]]=1;
			}
		}
		for(int j=0;j<=n*n;j++)
		{
			if(t[j]==0)
			{
				sg[i]=j;
				break;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]%2==1) ans^=sg[i];
	}
	if(ans==0)
	{
		cout<<"-1 -1 -1"<<endl;
		cout<<0<<endl;
		return;
	}
	int num=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=0)
		{
			for(int j=i+1;j<=n;j++)
			{
				for(int k=j;k<=n;k++)
				{
					a[i]--; a[j]++; a[k]++;
					int ans=0;
					for(int u=1;u<=n;u++)
					{
						if(a[u]%2==1) ans^=sg[u];
					}
					if(ans==0)
					{
						num++;
						if(num==1)
						{
							cout<<i-1<<" "<<j-1<<" "<<k-1<<endl;
						}
					}
					a[i]++; a[j]--; a[k]--;
				}
			}
		}
	}
	cout<<num<<endl;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--) work();
	return 0;
}

有一个100 * 100的棋盘，其中左下角的编号为(0, 0), 右上角编号为(99, 99)。棋盘上有N个Queen，最开始第i个Queen的位置为(Xi, Yi)。现在有两个玩家依次来操作，每一次一个玩家可以选择其中一个Queen，将它跳到(Xi – k, Yi)或(Xi, Yi - k)或(Xi – k, Yi - k), 其中k > 0。注意在游戏的过程中，一个格子里面可能出现多个Queen。如果谁先将任意一个Queen移动到(0, 0), 谁就获胜。问先手必胜还是后手必胜? Input

注意本题是多组数据。 第一行有一个数T, 表示数据组数。 接下来有T组数据，每组数据的第一行一个正整数N表示Queen的个数。接下来N行每行两个数表示第i个Queen的初始位置Xi, Yi(0 <= Xi <= 99, 0 <= Yi <= 99)。 Output

对于每一组数据，你需要输出是先手必胜还是后手必胜。 如果是先手必胜，输出“o“, 如果是后手必胜，输出”T_T”。 Sample Input

2 2 3 4 3 5 3 3 2 4 2 3 1 Sample Output

o T_T 数据范围 T <= 10, N <= 1000

http://www.lydsy.com/JudgeOnline/problem.php?id=1457 参考以下题解写的... http://blog.163.com/benz_/blog/static/186842030201172411290582/

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
#include<bits/stdc++.h>
using namespace std;
int sg[110][110]={};
int p[11000]={};
void init()
{
	for(int i=1;i<=99;i++)
	{
		for(int j=1;j<=99;j++)
		{
			if(i!=j)
			{
				memset(p,0,sizeof(p));
				for(int k=1;k<min(i,j);k++)
				{
					p[sg[i-k][j-k]]=1;
				}
				for(int k=1;k<i;k++)
				{
					if(i-k!=j) p[sg[i-k][j]]=1;
				}
				for(int k=1;k<j;k++)
				{
					if(i!=j-k) p[sg[i][j-k]]=1;
				}
				for(int k=0;k<=10000;k++)
				{
					if(p[k]==0)
					{
						sg[i][j]=k;
						break;
					}
				}
			}
		}
	}
}
void work()
{
	int n,s,x,y;
	int flag;
	s=flag=0;
    for (scanf("%d",&n);n--;)
    {
        scanf("%d%d",&x,&y);
        if (x==0||y==0||x==y) flag=1;
        else s^=sg[x][y];
    }
    if (flag||s) puts("^o^");
    else puts("T_T"); 
}
int main()
{
	init();
	int T;
	scanf("%d",&T);
	while(T--) work();
	return 0;
}