J - Simple Game (博弈论外壳下的模运算考察题目)

发布时间 2023-05-01 20:04:58作者: liuwansi

原题链接: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;
}