原题链接:https://vjudge.net/contest/555710#problem/J
手工翻译:
Alice和Bob在玩一个游戏有这样一个数列a1,a2,a3,a4……an长度为n,他们轮流移走一个整数当数列中没有可移走的整数时游戏结束,Alice移走的数的和是S1,Bob移走的数的和是S2如果abs(s1-s2)为奇数,Alice赢,否则Bob赢接下来给出n(1e6)个数ai(1e9).谁赢输出谁的名字。
分析:
一个博弈论题目,但实际上考察的是我们关于取模运算的理解
首先,明确取模运算符合的运算律
模运算满足结合律、交换律、分配率,具体如下:
A. 结合律
((a+b)%p+c)%p=(a+(b+c)%p)%p
((ab)%p * c)%p= (a * (bc)%p)%p
B. 交换律
(a+b)%p=(b+a)%p
(ab)%p=(ba)%p
C. 分配率
(a+b)%p=(a%p+b%p)%p
((a+b)%pc)%p = ( (ac)%p + (b*c)%p )%p
具体到这个题目我进行如下推理
abs(s1-s2)%2==1 ->ALice win
==0 ->Bob win
abs(s1-s2)%2=abs(s1%2-s2%2)%2=abs((ai%2+……+aj%2)%2-(ak%2+……+aq%2)%2)%2=(a1%2+a2%2+a3%2+...+an%2)%2
(绝对值在运算中自行去除)
因此可得下列简单代码
CODE:
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e6 + 10;
int n, a[N], sum = 0;
int main () {
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for (int i = 1; i <= n; i ++)
{
if (a[i] % 2 == 1)
sum ++;
}
if(sum%2==1)cout<<"Alice"<<endl;
else cout<<"Bob"<<endl;
return 0;
}
标签:移走,运算,Simple,博弈论,Alice,int,Game,abs,Bob
From: https://www.cnblogs.com/OhLonesomeMe/p/17366912.html