GAME （HDU）（博弈论）

Alice and Bob are playing a game. They take turns and Alice moves first. There is a set of positive integers. In one's turn, he or she can choose a number (suppose xx) in the set, and choose a positive integer kk (kk does not need to be in the set), and replace xx with x-(10^k-1)x−(10k−1). For example, you can make a number xx in the set become x-9x−9 or x-99x−99 or x-999x−999 or x-999\cdotsx−999⋯. After that the set must still be a set of positive integers. That is to say:


* The number must still be positive: x-(10^k-1) > 0x−(10k−1)>0.
* A set can not have duplicate elements: x-(10^k-1)x−(10k−1) can not be equal to any other numbers in the set.

They take turns and Alice moves first. The one who can't move loses the game. Now the question is that who will win the game if they play optimally.

题意：a和b在玩游戏，给你一组正整数，每次可以减9，99，999...，但是要满足两个条件：1.减完之后必须是正整数，2.没有重复的元素

a先移动，不能动的人输，每个人最优，求谁赢

思路：-99，999等等都是9的倍数，最小减的数是9，那么我们就算最多能减多少次9，而且应该先对原数组排序之后再算每个数最多能减多少个9是最优解，

那么我们就先对数组排序再对原数组求最多能减几次9

还有一个问题是不能有重复的数，那我们先算能减的最多的数，然后我们再减去重复的操作数

那么我们对每个数来说，%9余数是0的我们最终的数应该是9 18 27...也就是1*9 2*9 3*9，那么多算的不数就是1 2 3...假设个数为n那么重复的操作数就是n*(n+1)/2

%9！=0的时候：假如余数是op，那我们就变到op+9*0 ,op+9*1,op+9*2...，那么操作数就是 0 1 2 ...,假设有n个余数是op的数，那么重复的操作次数就是n*(n-1)/2

然后用总操作数减去重复的操作数就是最后的操作数了，是单数的话A赢，双数的话是B赢
 

/*
 .----------------.  .----------------.  .----------------.  .----------------. 
| .--------------. || .--------------. || .--------------. || .--------------. |
| |  ________    | || |  _________   | || | ____    ____ | || |     ____     | |
| | |_   ___ `.  | || | |_   ___  |  | || ||_   \  /   _|| || |   .'    `.   | |
| |   | |   `. \ | || |   | |_  \_|  | || |  |   \/   |  | || |  /  .--.  \  | |
| |   | |    | | | || |   |  _|  _   | || |  | |\  /| |  | || |  | |    | |  | |
| |  _| |___.' / | || |  _| |___/ |  | || | _| |_\/_| |_ | || |  \  `--'  /  | |
| | |________.'  | || | |_________|  | || ||_____||_____|| || |   `.____.'   | |
| |              | || |              | || |              | || |              | |
| '--------------' || '--------------' || '--------------' || '--------------' |
 '----------------'  '----------------'  '----------------'  '----------------'
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define int long long
#define lowbit(x) x&(-x)
#define PI 3.1415926535
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int gcd(int a,int b){
	return b>0 ? gcd(b,a%b):a;
}
/*
int dx[8]={-2,-2,-1,1,2,2,-1,1};
int dy[8]={-1,1,2,2,1,-1,-2,-2};
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int dx[8]={-1,1,0,0,-1,-1,1,1};
int dy[8]={0,0,-1,1,-1,1,-1,1};
*/
//int e[N],ne[N],h[N],idx,w[N];
/*void add(int a,int b,int c){
	e[idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx++;
}
*/
const int N=2e5+10;
int n;
int a[N],b[N],c[N],book[N];
 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie() ,cout.tie() ;
	while(cin>>n){
		for(int i=0;i<=9;i++){
			book[i]=0;
		}
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		sort(a+1,a+1+n);
		int ans=0;
		for(int i=1;i<=n;i++){
			b[i]=a[i]/9;
			c[i]=a[i]%9;
			ans+=b[i];
			book[c[i]]++;
		}
		for(int i=0;i<=8;i++){
			int k;
			if(i==0){
				k=book[i]*(book[i]+1)/2;
			}else k=book[i]*(book[i]-1)/2;
			ans-=k;
		}
		if(ans&1){
			cout<<"A"<
		}else cout<<"B"<
	}
}