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;
}