首页 > 其他分享 >CF1658E Gojou and Matrix Game

CF1658E Gojou and Matrix Game

时间:2024-11-02 22:08:24浏览次数:2  
标签:CF1658E Matrix 必败 max Game Gojou 全局 范围

题意

题解

设f[i,j]表示(i,j)先手必胜/必败

则全局max一定必败,因为先手走出去后手走回来,重复无限次后必输

然后全局max外(距离>k)的必胜,因为可以走到全局max

之后可以发现,下一个必败的是全局max范围内的次max,因为次max不能①走出全局max范围 ②走到全局max ③走到一个比自己小的数(后手往回走,先手输)

然后次max会进一步缩小范围,变成全局max+次max两重限制,并且可以发现下一个必败的就是里面的次次max


观察整体流程,发现上面的操作完全等价于从大到小枚举数,若在范围内就选,然后缩小范围并设为必败;在范围外不动

(次max就是除全局max和全局max范围外的max,即按顺序枚举下来的第二个

直接做,\(O(n^2)\)

标签:CF1658E,Matrix,必败,max,Game,Gojou,全局,范围
From: https://www.cnblogs.com/gmh77/p/18522578

相关文章

  • L. A Game On Tree
    应该坚持问题导向你的思维疏漏之处在于,忽略了“乙烯型”的情况本题其实并不是真正的数学期望型题目,因为可以通过除上\((\frac{n(n-1)}{2})^2\)将问题转化为统计所有公共路径长度的平方和考虑拆贡献。设公共边为e1,e2,...,ek,\((|e1|+|e2|+...+|ek|)^2\)分类讨论。|ei|产生的......
  • SS241031C. 博弈(game)
    SS241031C.博弈(game)题意博弈的规则是,有\(3\)个数字\(x,y,z\),每次可以选择其中两个数字\(x,y\),改成\(x',y'\),满足和不变差严格变小,即\(x+y=x'+y',|x-y|>|x'-y'|\)。无法操作的失败。给你\(n\)个数字,问有多少种选\(3\)个数字的方案使得先手必胜。solution首先可以设......
  • 0xgame 2024
    做不过来了,就跟着做了一点第一周####ez_sstifromflaskimportFlask,request,render_template,render_template_stringimportosapp=Flask(__name__)flag=os.getenv("flag")os.unsetenv("flag")@app.route('/')defindex():returnopen......
  • Shooter Game User Interface Starter
    射击游戏用户界面工具包这个工具包为射击游戏开发者提供了一套完整的UnityUI布局屏幕和预制件,旨在加速游戏界面的开发过程。以下是工具包的核心特性:屏幕布局:包含9个完整的UnityUI布局屏幕,覆盖装备、选项、游戏模式、大厅、社交、装备详情、登录、设置等多个游戏界面。......
  • 0xGame2024-week3-crypto
    CryptoLLL-IfromCrypto.Util.numberimportbytes_to_longfromnumpyimporteye,matrixfromrandomimportrandintfromsecretimportflagassertlen(flag)%4==0Length=len(flag)//4Noise=[[randint(1,pow(2,90))foriinrange(4)]forjinra......
  • Pygame游戏手柄(Xbox)输入测试工具
    文章目录前言Xbox手柄测试程序说明使用说明完整代码前言在python做机器人控制时,需要加入xbox操控功能,为了直观显示手柄摇杆与变量之间的对应关系,实时调试手柄输入,开发了python手柄测试程序(本文基于xbox)。Xbox手柄测试程序说明测试程序使用pygame库创建了一......
  • 题解:P11143 「SFMOI Round I」Strange Cake Game
    题目思路考虑贪心算法。根据题意,我们可以猜出结论,在最优状态下,小W将一直向下移动,小M一定向右移动。又因为小W是先手,所以当这块巧克力的横坐标小于等于纵坐标,即\(x\ley\)时,这块巧克力才可能归小W所有。另外,本题还有某些神秘做法可得\(20-25\)分。要特别注意的是......
  • 题解:Tokitsukaze, CSL and Stone Game
    ProblemLinkTokitsukaze,CSLandStoneGame题外话对于某些人说降绿甚至降黄,本人是很不同意的,毕竟多一道水蓝有什么不好题意翻译得很简洁,不再赘述。Solution不难发现有以下几种情况:只有两堆不等的,肯定选少的那堆,因为这样不易使得两堆相等。若两堆相等,一定破坏相等......
  • 题解:CF1994B Fun Game
    涉及知识点:异或,字符串处理。解题思路‌异或是一种二进制运算,用于比较两个数字的差异。当两个输入不同时,异或运算的结果为1;当两个输入相同时,结果为0。现在就可以切掉本题了。设两个字符串分别为$a$,$b$。如果$a$和$b$完全相同,输出Yes。如果$a$中没有$1$且$b$......