先讲一下Georgia and Bob:
题意:
给你一排球的位置(全部在x轴上操作),你要把他们都移动到0位置,每次至少走一步且不能超过他前面(下标小)的那个球,谁不能操作谁就输了
题解:
当n为偶数的时候,假设当每个球都相互挨着没有间隙,那么两两一组,一组中前面那个走到哪,后面那个跟上就可以了,先手必输
如果球与球之间有间隙,那么俩俩球之间的距离可以当作尼姆博弈中取石子游戏中一堆石子的石子数,用尼姆博弈判断一下就可以了
可以说先手赢不赢光和两球之间的距离有关,如果俩俩球之间的的距离都是0的话,那么谁胜利就已经知道了
当n为奇数的时候,可以先把第一个球走到终点(那么第一个球到终点的距离可以算成尼姆博弈的一堆石子),假设后面的球还是两两挨着,那么只需要用尼姆博弈判断一下第一个球怎么走就可以了
如果后面的球有间隔,那么可以把球与球之间的距离一起异或就可以了
代码:
1 #include<cstdio>
2
3 #include<iostream>
4
5 #include<algorithm>
6
7 #include<cstring>
8
9 using namespace std;
10
11 int a[1010],b[1010];
12
13 int main()
14
15 {
16
17 int t;
18
19 scanf("%d",&t);
20
21 while(t--)
22
23 {
24
25 int n;
26
27 b[0]=0;
28
29 scanf("%d",&n);
30
31 for(int i=1; i<=n; i++)
32
33 scanf("%d",&a[i]);
34
35 sort(a+1,a+n+1);
36
37 for(int i=1; i<=n; i++)
38
39 b[i]=a[i]-a[i-1]-1;
40
41 int s=0;
42
43 for(int i=n; i>0; i-=2)
44
45 s^=b[i];
46
47 if(s==0)
48
49 puts("Bob will win");
50
51 else
52
53 puts("Georgia will win");
54
55 }
56
57 return 0;
58
59 }
Climbing the Hill题意:
给你n个球的位置(x坐标),每一个球可以往前(下标减小的位置)移动,但是不能超过他前面那个球的位置,除了0这个位置之外其他位置只能有一个球,看谁能把红球移到0位置,Alice先走,Bob后走,谁把红球移动到0位置,就输出那个人的名字(第k个球就是红球)
题解:
当k==1的时候先手必胜
当n为偶数,k!=1的时候,那么根据上一道题我们只需要对所有球两两分组,对每一组球的间距异或一下,如果是0,那么Bob赢,反之亦然
你可能要问了,上一道题目所有球都要到达0这个位置,这一道题红球到了就结束了,这没有区别吗?
其实是没有区别的,因为一旦每一组球的间距都变成0的话,那么一组之间的移动不改变谁获胜
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 using namespace std;
6 const int maxn=1005;
7 int v[maxn];
8 int main()
9 {
10 int n,k;
11 while(~scanf("%d%d",&n,&k))
12 {
13 for(int i=1;i<=n;++i)
14 {
15 scanf("%d",&v[i]);
16 }
17 if(k==1)
18 printf("Alice\n");
19 else
20 {
21 if(n%2==0)
22 {
23 int flag=0;
24 for(int i=2;i<=n;i+=2)
25 {
26 flag^=(v[i]-v[i-1]-1);
27 }
28 if(flag==0)
29 printf("Bob\n");
30 else printf("Alice\n");
31 }
32 else if(n%2)
33 {
34 int flag=v[1];
35 if(k==2) flag-=1;
36 for(int i=3;i<=n;i+=2)
37 {
38 flag^=(v[i]-v[i-1]-1);
39 }
40 if(flag==0)
41 printf("Bob\n");
42 else printf("Alice\n");
43 }
44 }
45 }
46 return 0;
47 }