codeforces 201 div.1

本文从WordPress迁移而来, 查看全部WordPress迁移文章

A.题意:一开始序列有n个不同的数字,每人每次可以选两个数字,作差求绝对值,这个绝对值一定不存在于当前序列中,然后将这个绝对值添加到序列中,直到某一个人,无法找到合法的绝对值插入序列,那么这个人输了,求出胜利的人是谁

  1. 显然的一个事实就是,一开始序列中最大值为Max,那么无论怎么选,后来产生的绝对值都比这个Max小
  2. 很天真的一个想法就是,感觉最后1-Max这些数一定都能产生,也就是还需要插入Max - n个数字,那就可以知道最后是谁插入,它就是胜者,写代码,wa
  3. 很快想到一个数据,3,6,发现这个数据,从一开始,就没办法插入数字(|3-6|=3,无法插入),也就是A一开始就输了,接着又想到了一个特殊的数据,2,4,6,8,发现这个序列,从一开始就没办法插入数字,A一开始就输了。很容易联想到是等差数列,然后接着发现另一个数据9,11,13,15,也是个等差数列,但是最后是可以构造完1-15所有的数字的,为什么都是等差数列,差都是2,但是结果相差这么大呢?于是再思考
  4. 观察2,4,6,8这种等差数列,发现,d=2,而最小的元素(或最大元素也行)是2,即2 = 1 d,是d的倍数,自然4=2 d,6=3 d,8=4d,很容易发现,对于一个等差数列,如果差是d,并且每个元素都是d的倍数,那么这个等差数列到最后,就会“终止生成”,无法继续扩展,例如 6,9,12,15,很容易发现,这个序列扩展到3,6,9,12,15后就停止了。刚才的序列9,11,13,15,d=2,但是序列的元素并不是d的倍数,所以存在继续扩展的能力
  5. 现在我们能明确一个结论就是,若一个序列为等差序列,差为d,最大元素Max = m*d,那么这个序列最后的元素个数就是m,分别为d,2d,3d,4d…..md
  6. 对于给定的序列P,如果最后停止扩展了,得到序列Q,那说明Q序列,一定是一个等差序列,差为d,并且Q中每个元素都是d的倍数,也就是说,P中原有的这些元素,都是d的倍数,那么d就是P中每个元素的公约数,求出d,问题都解决了
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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 110

int gcd(int a,int b){
return b == 0 ? a : gcd(b,a%b);
}

int main(){
int n,a[N],Max;
while(scanf("%d",&n)!=EOF){
Max = -1;
for(int i = 0; i < n; i++){
scanf("%d",&a[i]);
Max = max(Max,a[i]);
}
int GCD = a[0];
for(int i = 1; i < n; i++)
GCD = gcd(GCD,a[i]);
int m = Max / GCD;
if((m-n)&1) puts("Alice");
else puts("Bob");
}
return 0;
}