#include<iostream> #include<cmath> using namespace std; int main(){ int n,b=-10000000,c=0,x=0; cin>>n; int a[n]; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ c+=a[i]; b=max(a[i],b); } for(int i=1;i<=n;i++){ if(a[i]==b){ x++; } } cout<<c-(x*b); return 0; }

upd：暴力推平的复杂度分数写反了。 调了 10h 的 FHQ-Treap 调疯了，然后直接加入邪修（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 替罪羊树是一个比较暴力的平衡树。 首先我们复习一下普通二叉树是怎么加入元素的： * 如果已经遍历到不存在的节点了，就新开一个节点。 * 如果当前节点的值恰好是要修改的值，就修改。 * 否则如果要修改的值小于当前节点的值，就往左子树搜。 * 否则往右子树搜。 * 然后 push_up 合并左右子树及当前节点的信息。 这样子会有什么问题呢？ 注意到出题人可能会构造数据，让你建出一个十分不平衡的二叉树，然后就炸了。显然单次查询最坏可以卡到 O(n)O(n)O(n)。 那不平衡怎么办呢？把它弄平衡呗。 我们可以在修改的时候判断当前节点，如果发现这个节点不太平衡了，就直接暴力把这个子树重构成一个最平衡的完全二叉树。 判断一个节点不平衡的方法有很多种，我这里用的是比较子树节点个数。 定义 sizeu\text{size}_usizeu 为节点 uuu 的子树节点数量，如果 sizesonu≥α×sizeu\text{size}_{\text{son}_u}\ge \alpha\times \text{size}_usizesonu ≥α×sizeu ，那么就将他看做不平衡，其中 α\alphaα 是一个 (0.5,1)(0.5,1)(0.5,1) 的数。 这么做为什么是对的呢？ 首先考虑查询复杂度。 由于某儿子的 size\text{size}size 大于等于父亲的 size\text{size}size 的 α\alphaα 倍就会被重构，所以在每次操作后一定满足两个子树的 size\text{size}size 小于父亲的 size×α\text{size}\times \alphasize×α。而查询就是递归到 size≤1\text{size}\le 1size≤1 的点，所以时间复杂度是 O(log⁡1αn)O(\log_{\frac{1}{\alpha}} n)O(logα1 n) 的。 然后看看暴力重构复杂度。 假设一个节点的子树当前处于完全平衡状态（sizesonu=0.5sizeu\text{size}_{\text{son}_u}=0.5\text{size}_usizesonu =0.5sizeu ），则解方程可得至少增加 2α−11−αsizeu\frac{2\alpha-1}{1-\alpha}\text{size}_u1−α2α−1 sizeu 个节点才能使得它被 O(sizeu)O(\text{size}_u)O(sizeu ) 重构，然后又处于平衡状态。均摊时间复杂度为 O(1−α2α−1)O(\frac{1-\alpha}{2\alpha-1})O(2α−11−α )。 所以只要 α\alphaα 不设得太离谱这个复杂度就是 O(log⁡n)O(\log n)O(logn) 的。 直接贴代码。

动态规划 动态规划(DP)类问题主要求解的步骤： 1.划分阶段 斐波那契数列的为一项作为一个阶段 2.确定状态 第i项的值用数组第i位表示：a[i] 3.确定决策并写出状态转移方程式 每一项得值都是前两项的和：a[i]=a[i-1]+a[i-2]

不一定要做出来，偏分就行（除不想偷懒的人)

https://www.acgo.cn/application/1680181715063709696

happy,happy，我看看还有那些人没放寒假呢

此帖内容仅代表自己的想法，有误请勿喷 最近我正在尝试获得ACGO中勋章墙里的编程能力勋章，但是呢发现了一点问题： 大家可以看到，在编程能力勋章里面的【字符】勋章显示，需要通过10道【字符】相关知识的官方题目 我在题库里面选择了【字符】相关知识点和【官方】这两个筛选条件，出来的题目只有5道 也就是说，只靠把官方题目的5道全做完也不可能得到这个勋章，这个勋章也就完全没有意义了...... 希望以后ACGO能在勋章这一方面做一些改善，下面是我的建议： 1.增加更多相关知识点的勋章，激励大家学习相关知识点 2.目前“通过10道官方题目”略微有点局限性，希望ACGO不用对着官方题目死磕，可以增加一些历年真题 希望ACGO能作出调整，谢谢！

招人，各位如果想加入，可以在1月30日之前申请加如，团队链接如下 https://www.acgo.cn/team/1898604825192366080 ---神仙突击队， tips: 前5人有官位！！！ 小彩蛋

只花了1.9MB

如果你在学习树穴的过程中遇到令你崩溃的计算题可以发到评论区！然后作者会放在下面的列举里！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1.当你在做简便计算时遇到例如56+4356 + 4356+43这种凑不了整十整百的数时@风之叹 2.当你遇到这种小数乘小数的题目：0.115×0.33370.115 × 0.33370.115×0.3337一乘就5分钟的无法变成整数的计算题@风之叹 3.计算时算出除数为000的数，而且前面还列了一大堆式子，结果发现第一步就错了@风之叹 4.做分数乘法或除法的题目时做到类似514÷710\FRAC{5}{14}÷\FRAC{7}{10}145 ÷107 的题目，本以为化成乘法就可以开开心心地约分，可是刚写下去：514×107\FRAC{5}{14}×\FRAC{10}{7}145 ×710 就EMO了@风之叹 5.算了半天4.137Π4.137\PI4.137Π加6.125Π6.125\PI6.125Π，算完得一个小数已经崩溃了，题目让我再乘7，算完了发现他让保留Π\PIΠ @༺ཌༀ我要上南开ༀད༻ 6.736+637\FRAC{7}{36}+\FRAC{6}{37}367 +376 @༺ཌༀ我要上南开ༀད༻ 7.考试算出6.3756.3756.375个人一组@༺ཌༀ我要上南开ༀད༻ 8.21221^2212+22222^2222@༺ཌༀ我要上南开ༀད༻ 9.题目让Π=3.14159\PI = 3.14159Π=3.14159@风之叹 10.让算81Π81\PI81Π，转化成9Π×99\PI×99Π×9，算完了又除以999验算，的确是9Π9\PI9Π，发下来卷子发现9Π9\PI9Π背错了 @༺ཌༀ我要上南开ༀད༻ 11.让用(40.125Π+9.75Π)×93(40.125\PI+9.75\PI)×93(40.125Π+9.75Π)×93，算完思想崩溃了，检查时发现Π\PIΠ取333@凤凰_星火燎原—月落 12.[(35.125Π+3.7Π)×306×5360]÷3.795[(35.125Π + 3.7Π) × 306 × 5³⁶⁰] ÷ 3.795[(35.125Π+3.7Π)×306×5360]÷3.795@至少比你帅（佐助，水门本人） 13.文具店进了一批铅笔，第一天卖出了总数的13\FRAC{1}{3}31 多 666 支，第二天卖出了剩下的 12\FRAC{1}{2}21 少 333 支，第三天卖出了剩下的 23\FRAC{2}{3}32 后，还剩下的数量比第一天卖出后剩下的 14\FRAC{1}{4}41 多 222 支。请问这批铅笔原来有多少支?这道题可以列方程，设这批铅笔原来有X支，按每天卖出的规则逐步推导剩余数量：19X=14(23X−6)+2\FRAC{1}{9}X = \FRAC{1}{4}(\FRAC{2}{3}X - 6) + 291 X=41 (32 X−6)+2，结果X=−9X = -9X=−9,白解一个方程。@柒梅久久 14.有这样的一个完美长方形，求周长: @TN HACKER 15.对于 A1A2AA3A4‾\OVERLINE{A_1A_2AA_3A_4}A1 A2 AA3 A4 ，解方程： a1≠a4,a2≠a3,a2=a1+2,a4=2a3,a2a3a4‾+a1a3a4‾+a1a2a4‾+a1a2a3‾∣39,1≤a1,2,3,4≤9a_1 \neq a_4,a_2 \neq a_3,a_2=a_1+2,a_4=2a_3,\overline{a_2a_3a_4}+\overline{a_1a_3a_4}+\overline{a_1a_2a_4}+\overline{a_1a_2a_3} | 39,1 \le a_{1,2,3,4} \le 9 a1 =a4 ,a2 =a3 ,a2 =a1 +2,a4 =2a3 ,a2 a3 a4 +a1 a3 a4 +a1 a2 a4 +a1 a2 a3 ∣39,1≤a1,2,3,4 ≤9 解法： 设 A=A1,B=A3A=A_1,B=A_3A=A1 ,B=A3 ,枚举 A,B 的 81 种可能，可以证明答案为 A=4,B=4A=4,B=4A=4,B=4,因此答案为 464846484648@不会C++的NOAH 16.已知有个容器足够高，先到入水再倒入油，然后再放入一个长4厘米，宽8厘米，高15厘米，铁块，然后油和水升高了3厘米，问：原来的水油有多高，原本是能答对的，结果忘记还会有溢出的情况@AC是最好的 17.[(2÷12345302.378)MOD2.78]+⌊0.91÷534⌋[(2 ÷ 12345^302.378) MOD 2.78] + ⌊0.91 ÷ 534⌋[(2÷12345302.378)MOD2.78]+⌊0.91÷534⌋@至少比你帅（佐助，水门本人） 18.找规律：2,9,28,65,126,2172,9,28,65,126,2172,9,28,65,126,217，规律为：N3+1N^3+1N3+1@咕咕咕 19.上课的时候列二元一次方程组，算租了多少辆车，算了1小时，算出来租了-3辆车@抑相>...< 20.算几何图形时算半天，批完一发下来，最后的得数算错了，算出来一个班408个人@ENTJ 21.算出师父做了一小时16000个零件，徒弟做了42000@凤凰_星火燎原—月落 22.没看见约，以为能除尽，算到小数点后十几位@ZDZL_HACKER_小逍遥 23.解一个方程题时，都算对了，结果被判全错问老师为什么老师说"这题让你求YYY，谁让你求辅助计算的XXX的？! "单元模拟考的题目，水灵灵五分全扣光了@我是辞E，听取红色WA声一片 24.谁能懂，考试的时候算出，小明身高22.89ML2^{2.89}ML22.89ML的无力感@鬼嘲深渊——嘲灾 25.天天站在第9.15道跑道上@ENTJ 26.一辆汽车一小时行驶47100KM@ENTJ 27.当你算完一个复杂的多项式相加的时候，猛地一看发现选项里没有这个选项@‮༺དༀ༒∞░∞༒ༀཌ༻ 28.1÷1+(1÷(1+1÷(1+1÷7)))1÷ 1+(1÷(1+1÷(1+1÷7)))1÷1+(1÷(1+1÷(1+1÷7)))@朱朗枫 29.一个带绝对值的式子 ∣6T−32∣+6T|6T-32| + 6T∣6T−32∣+6T 算成了 −32-32−32@KALI 30.方程算着算着把XXX算没了@ZDZL_HACKER_小逍遥 31.把6(2X+4)=14X−46(2X+4)=14X-46(2X+4)=14X−4算到12X−8=14X+412X-8=14X+412X−8=14X+4@橙子同学 32.答案算出来无限循环小数@ZDZL_HACKER_小逍遥 33.用方程算了101010分钟，得出小明37.537.537.5岁，他爸414141@橙子同学 34.因式分解：A2+2ABA^2+2ABA2+2AB 解：原式=A2+2AB+X2−X2=(A−X)2−X2解：原式=A^2+2AB+X^2-X^2=(A-X)^2-X^2解：原式=A2+2AB+X2−X2=(A−X)2−X2@暴力出奇迹，结果TLE 35.当你把16−2X16-2X16−2X写成∣2X−16∣|2X-16|∣2X−16∣然后丢了一分从120到了119@BIANHL 36.(3X−6)÷(X−2)=4(3X-6)÷(X-2)=4(3X−6)÷(X−2)=4,XXX应该=2=2=2，但除数不能为000，所以X≠2X≠2X=2@朱朗枫 37. @MC真好玩 38.算一道Π取3.1415926的填空题，算了一大堆，最后题目要求填大于或小于或等于，我本来要写大于的，可下笔后写成了“大小”，还有一道题要写静止或运动，写成了“静动”@鬼嘲深渊——嘲灾 39.A2+2ABA^2+2ABA2+2AB 解：原式=A(A+2B)原式=A(A+2B)原式=A(A+2B)@俞梓宸 JAYDEN 40.用方程算出了甲地离乙地有−93-93−93千米@LIIIIIIIII 41.算出3.33333......3.33333......3.33333......人一组@凤凰_星火燎原—月落 42.ABCDE*5=EDCBA@神_ℒℴѴℯ骏-時間打敗諾言༻꧂ 43.用代数式算了半天阴影部分的面积,死磕半天没算出来,最后发现下面定义了一个字母MMM@CH/陈---必回关 44.有一次考试36.04Π36.04Π36.04Π我真蒙了，结果算完要保留ΠΠΠ@俞梓宸 JAYDEN 45.算出2X=X2X=X2X=X@阿道夫—奶龙 46.拼尽全力算出X=X,Y=YX=X,Y=YX=X,Y=Y@BFS神力庇佑 47.求半圆+长方形的面积和周长 一切正常数据：圆半径6.756.756.75，长方形长6.75∗26.75*26.75∗2，宽1.575……1.575……1.575……六位小数@意大利面拌72号混凝土 48.直线Y=−2X+10Y=-2X+10Y=−2X+10与XXX轴，YYY轴分别交于点A,BA,BA,B把▲AOB▲AOB▲AOB沿ABABAB翻折，使点OOO落在点CCC处，求点CCC的坐标@LOVEKLEE1314 49.10241024=?1024^{1024}=?10241024=?@TN HACKER 50.因式分解：Y(Y+1)+(X2+1)+X(2Y2+2Y+1)Y(Y+1)+(X^2+1)+X(2Y^2+2Y+1)Y(Y+1)+(X2+1)+X(2Y2+2Y+1)最后发现:没分完！@༺ཌༀ༒RDS༒ༀད༻（HG） 51.10%的NACL溶液，在体积不变的情况下，浓度变大，则液体质量____（增大或减小）正解:增大;我的答案:减大@入 52.算出45875*957382-68654，这还是正确答案，年级考试的时候压轴题@WANDERER 53.简便运算121299991212^{9999}12129999，我直接晕了@疯癫的二 54.10道选择题中有8道 算半天发现答案选项里没有@CAT 55.几何这一块 1.添了一条辅助线，于是按照辅助线的条件 写了一堆答辩还证不出来最后答案没添辅助线 2.瞎眼识相似 3.想当然直角三角形，夏季⑧勾 4.翻折动点旋转3幻神，添线宝宝有福了@‮REWOLF LAUNUNU 56.做压轴题好不容易做出X=−3X=-3X=−3，却发现题目说XXX为正整数@人行道上不是很宽吗-互关 57.180+820，本以为很简单，结果发下来时发现写了个100@135****1664 58.一道算伯伯养了多少只鸡的题老师出错了，问AI问了半天问不出，自己算出是个小数@CCHU 59.题目说父女一共99岁，算出女儿49岁，父亲50岁@鬼嘲深渊——嘲灾 60.算出结果汽车时速200KM/H,以为错了去改,没想到200就是正确答案@CH/陈---必回关 61.题目问甲乙两地相距多少千米，我做出来-20千米@俞梓宸 JAYDEN ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 欢迎发到评论区！！！ 😭[链接描述] 作者的一辈子 求进团！！！

T2221.数组偏移 入门 通过率：34.21% 加入题单 题目描述 你有一个数组 � a，里面有 � n个元素。 现在需要将数组向前偏移 � M个位置，我们定义偏移 � M为： � 0 > � � A 0 =>A M ， � 1 > � � + 1 A 1 =>A M+1 ，...， � � − 2 > � ( � − 2 + � ) % � A N−2 =>A (N−2+M)%N ， � � − 1 > � ( � − 1 + � ) % � a n−1 =>a (n−1+m)%n ，即每个数向前偏移 � m个位置。 比如原数组 � a为 [ 1 1、 2 2、 3 3、 4 4、 5 5]，向前偏移3个位置后，数组变为 [ 3 3、 4 4、 5 5、 1 1、 2 2]。 请设计一个函数完成这个功能。 输入格式 第一行包含 � n 和 � m，分别表示数组长度和偏移量。 第二行包含 � n个整数，表示数组的各个元素。

建议你用WA

现团队已经达到35人，感谢大家支持

///////屏前攻C++励志长句/////// 荧屏灼灼映书案，十指翻飞敲键盘。 晨起研题思算法，暮来敲码解疑难。 一行语法需斟酌，数度调试始心安。 循环嵌套寻规律，条件分支辨细端。 变量定义严规范，函数调用合矩端。 深钻递归破迷局，细推迭代顺流程。 屏前凝思千般绪，笔下铺陈万缕牵。 遇题初懵频凝眉，得法方知路坦宽。 排查bug寻根由，验证结果守准线。 眸光专注屏中字，心力全倾码上缘。 键盘轻响凝思绪，屏幕微光伴静研。 基础夯实方致远，难题攻克更知艰。 数组排列循章法，指针穿梭探本源。 结构体中藏奥义，类方法里觅真诠。 编译初红心微紧，调试全绿意欣然。 朝磨思路清千障，暮炼技能破万关。 千行代码凝心力，百次推敲见精研。 纵使难题拦前路，终凭执着越重山。 身寄屏前追星梦，心随代码赴新篇。 难题炼得思如炬，代码磨来技渐圆。 敲尽繁文终有获，研通妙法更无前。 案头纸笔助思萦，屏间逻辑铺锦笺。 左思边界防疏漏，右想场景避偏颜。 简单题里磨功底，复杂题中炼胆肝。 代码行行皆有序，思路条条总相连。 初遇报错不慌乱，再遇疑难敢攻坚。 千番试错终无憾，一番跑通尽欢颜。 晨钟伴我研题旨，夜漏随吾敲码言。 算法精研明路径，语法细究避坑沿。 栈中数据藏玄妙，队列元素守序沿。 屏前久坐浑不觉，码上深耕自乐然。 一句注释明其意，几行代码解其难。 思通百法寻捷径，练熟千题破险滩。 逻辑铺陈无滞碍，代码书写有规圆。 堆区管理知深浅，栈区运用晓方圆。 循环遍数精推算，分支条件细详勘。 函数封装求简洁，代码复用贵精专。 调试步步寻疏漏，验证层层把好关。 初心不改研编程，志趣相投乐此间。 屏间光影随思动，指下键盘伴念弹。 千题炼就真本领，百码磨出硬功夫。 遇繁不躁心常静，遇简不怠志恒坚。 语法精熟无滞涩，算法通透少疑难。 定义变量循规范，调用函数合纲端。 递归层层寻脉络，迭代步步顺峰峦。 排查错误寻根蒂，修正代码复坤乾。 屏前研思忘朝暮，案上敲码历暑寒。 初心只为探真知，矢志不渝向峰巅。 代码千行凝匠心，算法百炼出精研。 今朝磨剑勤耕耘，明日扬鞭勇向前。 报错频仍不气馁，成功将至更谦谦。 逻辑思维凭锤炼，编程技艺靠精钻。 数组操作循章法，指针运用悟真诠。 结构体里藏经纬，类对象中蕴坤乾。 编译通过心欢悦，用例全过意舒然。 朝朝研题磨思路，暮暮敲码练指尖。 千番调试终无错，一番运行尽畅然。 身随代码游学海，心伴算法攀书山。 难题面前不低头，挫折途中勇向前。 敲码百遍知真味，研题千回悟本源。 基础扎牢行致远，技能炼硬步登巅。 屏前凝思寻妙法，指下敲键出佳篇。 编程路上多求索，算法途中苦钻研。 千行代码皆心血，百道难题尽锦笺。 纵使前路多风雨，初心不改向晴川。 今生无悔c++，来世还学c++(抄哪的好难猜) 求赞！！！！！！！！！！！！！！！！！！ c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 c++nb666 我不会告诉你是抄豆包的 点一点有惊喜 1（别被首页迷惑了） 2（别被首页迷惑了+1） 3 4（别被首页迷惑了+2） 5（别被首页迷惑了+3） 6（别被首页迷惑了+4） 7（别被首页迷惑了+5） 8 9（别被首页迷惑了+6） 10 11别被首页迷惑了+7） 12（别被首页迷惑了+8） 别忘了点赞

本题出题人在我旁边，是ACGO存在BUG，正在火速修复

#include<iostream> using namespace std; int main(){ int a,s=0; cin>>a; for(int i=0;i<=a;i++){ s+=(i+1)*i/2;} cout<<s; return 0; }

CF 原题能过，这过不了。 https://codeforces.com/contest/2008/submission/359658553

NIM 游戏总集 * Nim和：所有元素的异或和 NIM * 基础形式：nnn 堆物品，每堆 aia_iai 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取，取走最后一个物品的人获胜 * 结论：当且仅当Nim和为0时，先手必败，反则先手必胜 * 证明： * 发现最终局面是没有任何石子，先手必败，满足性质Nim和为0，所有Nim和为0的局面一定只能转移到Nim和不为0的局面（我们为了行文方便，称之为性质1），所有Nim和不为0的局面只能转移到Nim和为0的局面（我们称之为性质2）。 * 性质1的证明：考虑反证法，如果可以找到一堆石子，然后移除部分石子让异或和不变，那意味着我们取出的这个数量在二进制下的每一位都是0，相当于我们没有取石子，所以实现不了，故性质1成立。 * 性质2的证明：这里可能比较难理解，我们干脆直接给出玩家该如何具体操作来证明这个性质吧，玩家先找到石子最多的一堆，然后发现这一堆的石子数一定大于其它石子堆的异或和，因为这一堆石子数量最多，所以总的异或和二进制里的最高位一定由这一堆石子数来提供，相当于说明了这一堆的石子数一定大于其它石子堆的异或和，又由于两个相同数的异或和为零，我们只需要把这一堆石子也取到其它石子堆的异或和的数量，总的异或和就为0了。 * 题目： * P2197 【模板】Nim 游戏 * 模板，略 * P1247 取火柴游戏 * 找每个元素让Nim和变为0需要操作的最小数即可 * P7589 黑白棋（2021 CoE-II B） * 显然我们把每条线上的两点间的距离看作一堆石子，很像Nim游戏 * 考虑加石子的操作，因为有限，所以后手加石子的时候先手直接取走对应数量的石子就行了，这时候局面未变 * 综上，直接走Nim游戏就行了 * P5675 [GZOI2017] 取石子游戏 * 根据Nim游戏的结论我们有以下结论 * <1>所有石子堆的Nim和为0，先手必输 * <2>如果指定的那一堆没法通过取石子让Nim和变为0，先手必输 * 对于<2>很困难，我们正难则反，考虑什么情况能让<2>被打破 * 假设第i堆石子取走k个厚Nim和为0，其余堆的异或和为b，则 (ai−k)⊕b=0(a_i-k)\oplus b=0(ai −k)⊕b=0 * 这个式子等价于 ai−k=ba_i-k=bai −k=b，即 ai−b>0a_i-b>0ai −b>0 * 那么对于满足<2>的我们枚举i后求出其它堆的异或和大于等于 aia_iai 的方案数即可 阶梯NIM * 基础形式：有 nnn 堆石子，每堆石子的数量为 x1,x2,…,xnx_1,x_2,\dots,x_nx1 ,x2 ,…,xn ，A与B轮流操作，每次可以选第 kkk 堆中的任意多个石子放到第 k−1k-1k−1 堆中，第1堆中的石子可以放到第0堆中，最后无法操作的人为输。问 A先手是否有必胜策略。 * 结论：先手必败当且仅当奇数堆中的石子数异或和为0 * 证明： * 显然先手如果不能让奇数堆的Nim和变为0的唯一方案就是所有石子都在0点上，此时已输 * 如果移动石子让奇数堆的Nim和变为0则有两种情况 * <1>操纵的是奇数堆 * 后手一定能移动某一个奇数堆的若干石子往下一个堆使得奇数堆的Nim和变回0 * <2>操纵的是偶数堆 * 后手把这些操作的石子全部往下移一个堆就能让奇数堆的Nim和变回0 * 另一方面，如果最开始奇数堆的Nim和不为0，那么先手一定能一步让这些奇数堆的Nim和变为0，但此时先后手已经交换了，故必胜 * 题目： * P3480 [POI 2009] KAM-Pebbles * 显然任何时刻的差分数组非负，移动石子可以看作差分数组上的移动，变为差分数组上的倒着的阶梯Nim了 * P2575 高手过招 * 发现有若干子游戏互不相关，直接拆开，最后用SG定理合起来 * 现在把棋子的连续段缩成一堆石子，空位就算0石子堆，变味了阶梯Nim，注意这个阶梯Nim依旧是倒着的 ANTI NIM * 基础形式：nnn 堆物品，每堆 aia_iai 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取，取走最后一个物品的人失败 * 结论： * <1>所有堆的石子数均为1且为偶数堆，先手必胜 * <2>至少有一堆石子个数大于1且Nim和不为0，先手必胜 * <3>否则先手必输 * 证明： * <1>的正确性显然 * 当只有一堆石子数大于1，显然此时Nim和不为0 * 如果堆数为奇数，则把多的那一堆取到剩一个，显然后手必输，先手必胜。 * 如果堆数为偶数，则直接取走多的那一堆，显然后手必输，先手必胜。 * 当有两堆及以上的石子数大于1时 * 当Nim和为0时，显然会转移到Nim和非0的情况，如果石子数大于1的堆的数量变为了1，那么显然先手必输，否则会变为下面的情况。 * 当Nim和不为0时，显然可以转移到Nim和为0的情况，也就是上面那种情况，显然先手必胜，后手必输。 * 题目： * P4279 [SHOI2008] 小约翰的游戏 * 模板，略 K-NIM * 基础形式：有 nnn 堆石子，其中第 iii 堆有 aia_iai 颗，每次可以取走1至k堆石子中任意颗石子，不能操作者输 * 结论（记数字 xxx 在二进制下的第 iii 位表示为 (x)i(x)_i(x)i ）： * 若 ∀s,(∑i=1n(ai)s)mod  (k+1)=0\forall s,(\sum\limits_{i=1}^n(a_i)_s)\mod (k+1)=0∀s,(i=1∑n (ai )s )mod(k+1)=0，则先手必败，反之先手必胜。 * 证明： * 终止状态为必败状态（P态） * 所有石子堆为0，满足 * 所有P态只能转移到N态 * 因为最多操作k堆石子，但是要让mod(k+1)依旧是0需要至少k+1次操作。故P状态转移到的状态不是P态，即N态。 * 所有N态可以转化到P态 * 显然只需要按位拿就行了 * 显然性质成立 * 题目： * P2490 [SDOI2011] 黑白棋 * 显然最终局面是这些棋子黑白棋子交错的堆在一起 * 我们把相邻两个棋子（左白右黑）间的距离看作一堆石子，问题就成了d-Nim游戏的必胜局面方案数了 * 考虑前i个二进制都为0且用掉了j个位置的方案数，这里实际记录的是非法的，最后要用 (kn)(_k^n)(kn ) 减一下 * dpi+1,j+t×(d+1)×2i←dpi,j×(k2t×(d+1))dp_{i+1,j+t \times (d+1) \times 2^i} \leftarrow dp_{i,j} \times \binom{\frac{k}{2}}{t \times (d+1)}dpi+1,j+t×(d+1)×2i ←dpi,j ×(t×(d+1)2k ) * 答案就是 (kn)−∑i=1n−kdpmaxl+1,i(n−i−k2k2)(_k^n)-\sum_{i=1}^{n-k} dp_{maxl+1,i} \binom{n-i-\frac{k}{2}}{\frac{k}{2}}(kn )−∑i=1n−k dpmaxl+1,i (2k n−i−2k ) FIBONACCI NIM * 基础形式： * * 结论： * <1>如果n为斐波那契数，则先手要全取走 * <2>如果正整数 n 不为斐波那契数，则将其用齐肯多夫表示法表示后，最小的那一堆个数即为答案 * 证明 * <1>不妨设 n=Fbii=Fbii−1+Fbii−2n=Fbi_i=Fbi_{i-1}+Fbi_{i-2}n=Fbii =Fbii−1 +Fbii−2 * 如果先手不取 FbiiFbi_iFbii ，那么有一下两种情况 * 取了一个大于 Fbii−2Fbi_{i-2}Fbii−2 的数 * 显然 Fbii<3Fbii−2Fbi_i<3Fbi_{i-2}Fbii <3Fbii−2 * 所以后手能一步制胜 * 取了一个小于 Fbii−2Fbi_{i-2}Fbii−2 的数 * 显然这个数要是斐波那契数，原因见结论<2>的证明 * 显然后手可以一步把这个数保持成一个斐波那契数 * 我们考虑极端的末尾情况，n=2（显然n=1全取走，意义不大） * 先手不取2的话只能取1，后手取1赢 * 所以我们可以归纳的证明出结论<1> * <2>根据齐肯多夫定理，我们可以把n表示为 f1+f2+⋯+fkf_1+f_2+\dots+f_kf1 +f2 +⋯+fk 满足 ∀i，fi为斐波那契数。f1<f2<⋯<fk\forall i，f_i为斐波那契数。f_1<f_2<\dots<f_k∀i，fi 为斐波那契数。f1 <f2 <⋯<fk * 先手先取 f1f_1f1 ，显然后手没法一步取走 f2f_2f2 ，因为f2>2f1f_2>2f_1f2 >2f1 一定存在 * 我们假设先手足够聪明，那么先手一定可以通过拉扯来作为取走属于 f2f_2f2 的最后一个元素 * 同理我们对于每一个 fif_ifi 最后的一个元素都是先手取走的，所以最后是先手赢 * 现在的问题是为什么这个值是最小的 * 如果存在更小值，那么这个值一定小于 f12−1\dfrac{f_1}{2}-12f1 −1，不然后手就能用上面的规律获胜了。更进一步，按上述规律一定能找到一个更小的斐波那契数，但是并没如，所以这个数最小。 * 例题： * P6487 [COCI 2010/2011 #4] HRPA * 模板，略。 * P6791 [SNOI2020] 取石子 * 可以让 nnn 减小1，因为显然多取一个不会犯规，这样Anti Nim就解决了 * 然后现在就是再求有多少数按贪心的构造下最小的斐波那契数小于了k，由于不会有两项相邻的斐波那契数加入构造，直接dp就行，细节间代码吧，dp写多了觉得应该都不算细节 * 课后作业 * 如果P态（或N态）满足了一个性质q，并且所有满足性质q的局面只能转移到不满足性质q的局面，但所有不满足性质q的局面都可以转移到满足性质q的局面，那就可以通过看初始局面是否满足q性质来判断先手是否必胜 * 这个也可以用于证明 * 试着用这个去证明一下上面的所有Nim游戏吧

谁能告诉我哪错了？ 另一个：