首页 > 其他分享 >Sept.25 Triangle Game

Sept.25 Triangle Game

时间:2022-10-03 11:11:44浏览次数:76  
标签:ch Triangle 必败 Game 必胜 Sept.25 操作 oplus mod

portkey

考场上因为读不懂题(再加上菜)就弃了
所以先给一点翻译
non-degenerate 不-除掉|生成的 不退化的
non-degenerate triangle 不退化三角形,就是存在的三角形,满足三边\(a+b\geq c\)

然后题目就涉及到奇奇怪怪的博弈论知识了
不会
但最简单的证明还是看得懂
大佬说目前我的水平想不出来那就不必想出来吧,自己写一遍证明还是很有收获的

一个必胜态一定能够经过一次操作到达必败态,而一个必败态无论怎样操作都只能到达必胜态。
——来自博弈论知识

结论:先手胜当且仅当(a-1)^(b-1)^(c-1)!=0
证明如下

不妨设\(a\le b\le c\)
第一,一个必败态(即(a-1)^(b-1)^(c-1)==0)无论怎样操作都只能到达必胜态

  1. 若\(a=1\),则(b-1)^(c-1)==0,易知 \(b=c\),显然必败(已经可以停止证明了,因为先手都无法操作)
    先手将\(b\)减少,后手将\(c\)减少到相同值即胜利
  2. 若\(a\neq 1\),则有\(1<a<b<c\),如果将\(a\)减小为\(x\),则一定有(x-1)^(b-1)^(c-1)!=0,为必胜态
    对\(b\)与\(c\)操作也是这个结果

第二,一个必胜态一定能够经过一次操作到达必败态
x=(a-1)^(b-1)^(c-1),将 \(a-1\) 变为 (a-1)^x,则 \(a\) 变为 (a-1)^x+1,那么此时(a-1)^(b-1)^(c-1)==0,为必败态(对\(b,c\)同理,当然一次只能操作一个数)
那么就需要知道是否能使(a-1)^x+1<a
找到\(x\)的最高位,这个 \(1\) 在 \(a-1,b-1,c-1\) 的对应位上一定出现了奇数次,选择这个位上为 \(1\) 的数进行操作就可以使得这个数减小,因此是可以使(a-1)^x+1<a的(\(a\)取\(a,b,c\))

证毕

多打几个括号啊

标签:ch,Triangle,必败,Game,必胜,Sept.25,操作,oplus,mod
From: https://www.cnblogs.com/antimony-51/p/16750171.html

相关文章

  • 2018-2019 ACM-ICPC, Asia Seoul Regional Contest(CF GYM 101987) Problem K. TV Sho
    ProblemSolution设\(p_{i,R/B}\)为第\(i\)号节点染成R或B所代表的点。考虑2-SAT,对于每一个猜的操作,其中任意一个与猜的答案颜色不同,则其他两个必须相同。我们暴力进行......
  • POJ 2348 Euclid's Game(博弈论 辗转相减)
    POJ2348Euclid'sGame(博弈论辗转相减)题目:​ 给出两个数,A,B轮流操作。每次操作可以将大的数减去小的数的整数倍,若操作后出现0,执行这次操作的人胜。思路:​ 根据样例(25......
  • P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles
    这是一道动态规划的经典入门题,重点在于递规过程中存储计算结果,避免重复计算.当然直接简单粗暴使用递归也可以拿到部分分数.只是样例太大的话就过不了了.题目描述观......
  • Educational Codeforces Round 136 C. Card Game
    题意:有1-n的一个排列,其中n是偶数,A和B两个人拿这副牌玩游戏,两个人绝顶聪明。A拿一半牌,B拿一半牌。规则很简单,A先手出牌,如果B有比他大的牌,那出一张比他大的牌,这一轮结束,下一......
  • Game on Tree 3
    ProblemStatementThereisarootedtreewith$N$vertices,Vertex$1$beingtheroot.Foreach$i=1,2,\ldots,N-1$,the$i$-thedgeconnectsVertex$u_i$......
  • ABC 244 C - Yamanote Line Game (交互题)
    https://atcoder.jp/contests/abc244/tasks/abc244_c题目大意:有两个人,分别叫做AB。给定一个数字,A先手,每个人可以从[1,2*n+1]这个范围内说出一个数字,说不出的人就输;我......
  • gamemaker学习记录001
    截屏功能:截屏函数:screen_save获取时间戳:date_get_second_of_year(date_current_datetime())完整的截屏:if(keyboard_check(ord("Q"))){screen_save(string(date_......
  • pygame各个模块概述
    在pygame中,有很多模块,每个模块对应着不同的功能,如果我们知道这些模块是做什么的,那么,对我们的游戏开发会起到关键性的作用。我们就说说pygame中的各个模块吧!!! #pyga......
  • 【2021ICPC上海站】H-Life is a Game(kruskal重构树)
    题意你本身有一个权值。每个点有一个权值,到达一个点可以获得这个权值;每条边也有一个权值,只有你自己当前权值大于等于边权才可以走这条边。q次询问,每次给出初始点和初始......
  • 「postOI」Colouring Game
    题意有\(n\)个格子排成一行,一开始每个格子上涂了蓝色或红色。Alice和Bob用这些格子做游戏。Alice先手,两人轮流操作:Alice操作时,选择两个相邻的格子,其中至少要有......