首页 > 其他分享 >J - Simple Game (博弈论外壳下的模运算考察题目)

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

时间:2023-05-01 20:13:18浏览次数:54  
标签:移走 运算 Simple 博弈论 Alice int Game abs Bob

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

相关文章

  • 【配置】Simple Memory - 博客园 cnblogs 个性化博客配置
    前言地址:https://www.cnblogs.com/FReQuenter5156/setblog如题,使用的是SimpleMemory主题。Github连接:https://github.com/BNDong/Cnblogs-Theme-SimpleMemory。想个性化自己的博客只需要改代码就行了。不难改,注释很充分(也就是换一些url啥的。反正我是这么改的。搭建教......
  • cpp: Simple Factory Pattern
     //Monster.h:此文件包含"Monster"类。AbstractFactoryPatternC++14//2023年4月29日涂聚文GeovinDuVisualStudio2022edit.#pragmaonce#ifndefMONSTER_H#defineMONSTER_H#include<iostream>usingnamespacestd;namespaceDuAbstr......
  • MybatisPlus高级特性之SimpleQuery工具类
    1、是很么?SimpleQuery可以对selectList查询后的结果使用Stream流进行操作,使其可以返回指定的结果,简洁了api的调用2、怎么玩?案例演示(1)list操作/***list(LambdaQueryWrapper<E>wrapper,SFunction<E,A>sFunction,Consumer<E>...peeks)*参数说明:*p......
  • 主题Cnblogs-Theme-SimpleMemory-2023-04-30
    前言好久没来看CnBlog,准备更换一下主题,就记录下原主题,并感谢作者提供的这么好看的主题。主题文档地址:Cnblogs-Theme-SimpleMemory主题预览主题设置主题配置代码侧边栏公告HTML<scripttype="text/javascript">window.cnblogsConfig={cnzz:"1280245......
  • SimpleDateFormat和DateTimeFormatter
    SimpleDateFormat和DateTimeFormatter都是进行日期时间格式化的工具类,后者是为jdk1.8以后的日期对象服务的,它没有线程安全的问题;而前者,是存在多线程下的安全隐患的。作用将日期格式化成日期/时间字符串从给定字符串的开始解析文本以生成日期SimpleDateFormat是针对java.util.date和......
  • Tool-CMake-A Simple CMake Example
    Tool-CMake-ASimpleCMakeExamplehttps://cmake.org/examples/Therearethreedirectoriesinvolved.Thetopleveldirectoryhastwosubdirectoriescalled./Demoand./Hello.Inthedirectory./Hello,alibraryisbuilt.Inthedirectory./Demo,anexecuta......
  • AtCoder Regular Contest 116 F Deque Game
    洛谷传送门AtCoder传送门很强的博弈+性质题。下文令A为Takahashi,B为Aoki。发现单独考虑一个序列\(a_1,a_2,...,a_n\):若\(n\bmod2=0\):若A为先手,答案为\(\max(a_{\frac{n}{2}},a_{\frac{n}{2}+1})\);若B为先手,答案为\(\min(a_{\frac{n}{2}},a_{\frac......
  • 博弈论入门
    博弈论有向图游戏Nim游戏Nim游戏的定义是,给定\(n\)堆石子,两个玩家去交替的拿石头,每次只能拿某一堆的石头,如果此时有一个玩家无法进行这个游戏了,则游戏结束。为了解决这个问题,比较直接的会先想到一个类似于\(DP\)的思路,考虑当前每个状态,去将其划分为两个状态,这里我们定义为\(P:......
  • Game Engine Architecture(游戏引擎架构)
    推荐序1最初拿到《GameEngineArchitecture》一书的英文版,是编辑侠少邮寄给我的打印版。他建议我接下翻译此书的合同。当时我正在杭州带领一个团队开发3D游戏引擎,我和我的同事都对这本书的内容颇有兴趣,两大本打印的英文书立刻在同事间传开。可惜那段时间个人精力顾及不来,把近千页......
  • NC50454 A Simple Problem with Integers
    题目链接题目题目描述给定数列\(a[1],a[2],\dots,a[n]\),你需要依次进行q个操作,操作有两类:1lrx:给定l,r,x,对于所有\(i\in[l,r]\),将a[i]加上x(换言之,将\(a[l],a[l+1],\dots,a[r]\)分别加上x);2lr:给定l,r,求\(\sum_{i=l}^ra[i]\)的值(换言之,求\(a[l]+a[l+1]+\dots+a......