CF博弈论题选㗅

Querainy · 2020-11-22 17:07:43 · 个人记录

呃，因为某场cf的时候和某场csp的时候不会猜结论炸开了，所以来找点题练习一下。

选题的方式是，加上filter，直接从上往下开（

大部分是㗅一下然后看题解。

filter: tags=games

按Rating升序。

959A : 智障题。

1398B : 这种贪心选取不会给对手带来好处的，可以直接贪心选。

832A : ?难道是Div.4 A题

1270A : 超长题面，智障做法

1373B : 智障结论 : 01串中只要有0又有1，那么一定有01相邻。

1419A : 既然两个人的操作互不影响，只要看谁决定最后剩下那个是什么就好了，如果在这个人能操作的数里面有留到最后会让她赢的数，那么她确实就赢了。

以下为Rating 1000及以上。

616B : ?这也配1000?

1365A : 因为每次操作只对一行一列而对其它地方没有影响，所以能放就放就好了，答案为空行和空列数的\min的奇偶性。

1382B : 这题还不错。观察样例发现，先手有一个棒到不行的策略 : 每次取到只剩一个，这样后手必须取那一个，就可以保持先手；最后一次直接取完。

但是发现当遇到1的时候这个做法好像不太行了。考虑上面的做法核心是给对手1，那么先手可以直接把这个1给对手，也即上一次直接取走全部的。当然如果这个1是最后一堆还是要留给自己。

现在想了想发现有两个问题 : 开头有连续的1，和最后有连续的1。

对于开头，每个1一定会使先手后手交换一次。

对于结尾，先手还是有必胜策略 : 假设有2k+1堆1，先手后手轮流取，取到最后一堆是先手的；如果有2k堆，在这个连续的1段之前，先手可以把第一个1扔给后手，这样最后一个还是先手的。

所以只要看开头连续1数量的奇偶性即可。这题感觉不止1100。

841B : 智障题。考虑如果先手能全取走那么就会全取走。如果不能全取走，也就是说总和是偶数，那就随便取点什么，取完之后总和会变成奇数，后手一定不能全取走。后手再随便取点什么(或者直接不能取了)，总和还是奇数，这回先手一定全取走。所以如果先手第一步能取，那么先手一定获胜。

755B : 如果你玩过什么类似于飞花令的游戏，你应该想过，最优策略是先说都知道的，再说只有自己知道的。模拟即可。

705B : 这东西也挺智障，考虑每个东西a一定会被操作a-1次然后变成一堆1，所以判断\sum (a_i-1)的奇偶性即可。

1102C : 如果砸的比修的厉害，那么显然可以全砸了；否则一次砸不坏的显然不可能砸坏了，一次能砸坏的，只要修一次也变成砸不坏的了，所以两个人轮流砸/修，答案是一开始一次能砸坏的数量的一半上取整。

1155B : 最后十位没有用，因为删最后十一位中的任何一个，都等价于删第十一个。所以问题变成最后能不能留下8，看前面那些位8多还是别的多就好了。

914B : 考虑这个过程，发现如果最大的有1个，拿了它就赢了；如果有奇数个先手拿了也能赢。如果有偶数个，那么先开始拿最大的人肯定会输，所以考虑先拿次大能不能让对手先拿最大，也就是次大如果是奇数个，先拿次大就能赢。否则再去找第三大，以此类推，如果没有奇数个的，那么先手必败，否则取最大的有奇数个的那个一定可以赢。

630R : 这题实在是非常经典(，然而太过经典所以只有1200)。考虑先手如果放在棋盘正中间，接下来每一步都放跟后手对称的，那么一定是后手先完蛋。如果n是偶数，那么棋盘没有正中间了，后手就可以放跟先手对称的，所以后手必胜。

276B : 这题的获胜条件可以说成，逼着对手把它删成最多一个字母出现奇数次，并且其它字母出现偶数次。下面说的奇数偶数指的是出现奇数/偶数次的字母。那么我们先统计出奇数的数量k。如果k是0,1，那么先手已经赢了；如果是2，那么先手必败，因为她要么把一个偶数变成奇数，这样后手会把它变回来，有限轮之后删到没有偶数的时候先手就不得不删奇数了；要么把一个奇数变成偶数，这样后手就赢了。以此类推，如果k是0或奇数则先手胜，否则后手胜。

570B : 第一眼还真没想到是取m+1或m-1最优。

1220C : 题面你谷没有?题意 : 给一个字符串，现在有一个游戏，从一个区间[l,r]开始，每次扩展到一个比当前区间字典序小的区间，不能扩展就输了。对每个初始区间[i,i]求游戏的结果。

智障题。先手如果能扩展，直接一步扩展到不能扩展，那后手就没了。所以就是对每个字符看有没有字典序比它小并且包含它的。可以直接每个字符搞一个前缀和，看前面有没有比它小的字符。

257B : A肯定希望放跟上一个相同的，B希望不同的，那么我们只要枚举是先放红的还是蓝的，然后大力模拟即可。也可以更简单一点 : 考虑既然B放的是跟上一个不同的，一共可以放\min次不同的，那么B的分就是\min，然后每两个相邻的要么相同要么不同，也就是要么A得分要么B得分，所以A的分就是\max -1。

下面是1400及以上的题。

1370C : 对于奇数，直接除自己，先手必胜。对于2的幂，这东西没法除，只能-1变成奇数，所以先手必败，但2-1=1是一个特例。对于只含一个因子2的偶数，如果只有一个奇数因子，那就减了变成奇数会输，除了变成2也会输，所以先手必败。如果不止一个奇数因子，那就除到只剩一个，所以先手必胜。对于因子2幂次大于1的，除最大的奇数因子让它变成2的幂，所以先手必胜。

546C : 这个小模拟被扔进games我能理解，但是1400是?

934A : 原来CF也有爆力题，但是这games是?并且那个最后一篇题解写的还是不错的。

150A : 智障题，分解质因数，一口气除到只剩一个。

1425A : 我不会做，官方题解说，如果是4的倍数且>8就先-1，这样对手也只能-1，先手再/2，对手还是只能-1，这比两个人都/2优。如果是8或者是是2而不是4的倍数就/2，如果是奇数只能-1。这是一道好题，但是为什么只有1400呢?

120E : 跟上面的630R完全相同。

859C : 考虑dp，发现如果设dp[i][0/1]表示前i个，该先手/后手拿，先手能搞到的最大值，那么转移不太好办，因为当前做决策的同志不能决定她的对手怎么选择。再想一下，发现怎么选择取决于后面可以得到多少，所以倒着dp即可。

293A : 其实就是让1比对方多。贪心地，先选两个都是1的，再选只有一个1的，再选两个都是0的，模拟即可。

74B :

题意 :

S和C在一列火车上，火车有n节车厢。现在S要抓C。每个时刻，火车可能会停或不停。

如果火车不停，S可以选择移动到下一节车厢或上一节车厢。如果火车停了，S可以下车，然后移动到任意一节车厢。

不管火车停不停，C总是从起点向某个方向开始移动，每刻走一节车厢，直到走到车头或车尾，然后调头继续走，一直这样走下去(也就是，不停从一头走到另一头)。

规定同一时刻内，如果不停车，S先移动，C后移动；如果停车，S先下车，C再移动，S再上车。如果S和C在同一节车厢了，那么C就抓住了S。

求S能不能安全地在最后一站下车，如果不能，求出S最晚在第几刻被抓住。

输入格式 : 第一行三个数，表示火车的长度、S和C的初始位置；第二行表示C的初始方向；第三行表示火车在每一刻停不停车。

Solution : 考虑只有C把S按在一头S才完蛋，所以每次停车的时候走到C调头之前不会被C按死的那一边就好了。模拟即可。

以下是1600及以上的题。

1363C : 能删x当然就直接删了。考虑如果一开始不能删x，说明x度至少为2，然后如果删到只剩三个点且x度为2了肯定先手必败，又是每次删一个，所以此时答案就是点数量的奇偶性。

346A : 一眼题，根据裴蜀定理，最后一定可以拼出所有最小和最大之间的可以表示为k\gcd的东西。看有哪些要出现的数没有出现即可，这个数量的奇偶性就是答案。

197A : 这个结论出现三次了......先手能放那就放中间，肯定能赢。

493D : 很多这样的问题都可以考虑对称地走。对于奇数的情况，后手一直跟着走的话，容易发现先手必败。对于偶数的情况，先手先走到(1,2)，此时因为对称，后手想走到第一行，必须得踩着先手的脸过去，而这显然是不可能的(总慢一步)，所以就变成奇数的情况了，因此先手必胜。

1451D : 官方题解说的是，考虑设z为满足(kz,kz)在圆内的最大整数，那么 :

如果(kz,k(z+1))不在圆内，先手可以把后手按在y=x上(每次跟先手走相反的)，这样后手走到(kz,kz)就没法走了。这种情况下先手必胜。

否则，不管先手怎么走，后手可以把她按在y=x+k(或y=x-k，以下略)上。最后先手走到(kz,k(z+1))时，先手往右走到(k(z+1),k(z+1))肯定出圆；往上走到(kz,k(z+2))，套琴生不等式，出的比(k(z+1),k(z+1))还要离谱。这种情况后手必胜。

1194D : 直接打表找规律。

1215D : 考虑先手的最优策略肯定是往更大的一边放9来拉大差距，而后手为了减小差距也得放9。接下来只剩一边有?了，假设两人还分别能操作k次，有?的那一边减去没有?的那一边差为d，那么如果9k>d，先手全放9就赢了；如果9k<d，先手全放0就赢了；只有当9k=d，后手能保持每一轮两人放的和为k，此时后手赢。

980C : 又一个假games，既然是字典序所以直接按位贪心即可，可以简单地记录一个区间来判断一个数还能往右覆盖多少。这里暴力的复杂度似乎也可以接受。

917B : 大力dp，设dp[u][v][c][0/1]表示现在A在u，B在v，之前走过的字符最大是c，现在该A/B走，谁会赢。转移显然。

533C :

题意 : 有一个坐标系，A每次可以从(x,y)走到(x-1,y)或(x,y-1)，B每次可以走到(x-1,y),(x,y-1)或(x-1,y-1)，两个人不能位于同一个点。A先手，问谁先走到(0,0)。

考虑如果A可以走到B左下方，B就不能走(x-1,y-1)了，此时A必胜，否则看两个人到(0,0)最少要多少步即可。

1396B : 贪心地，我们希望每次拿最大的那一堆，这样更有可能多活一会，交上去发现过了。感性理解大概是，考虑如果一堆非常大以至于超过了一半，那么先手先拿它肯定能赢。所以如果有个人拿完了出现了这样一堆非常大的，他就输了，所以他不能这么做。贪心地，每次拿最大的就可以避免这种情况。

1190B : 考虑如果一开始有相同，那么先手必须操作相同的，否则他就开门红。如果操作完了还有相同，他就开门红。考虑没有相同的情况，容易想到最后的情况一定是类似于0,1,2,...这样的，计算需要拿石子的奇偶性即可。

3C : 这是一道小模拟，因为是上古场所以评到了1800。

148D : 经典概率dp。

794D : 考虑先手显然只会用到最小的一部分，后手只会用到最大的一部分，先手肯定想把小的往前放，后手也希望把大的往前放。有一个特例 : 先手手里最小的比后手手里最大的还要大，那么先手就会往后放，让后手把他手里最大的放到最前面。模拟即可。

55C : 考虑如果走到角上就赢了，而走到边上之前如果对手可以封锁四个角，那就输了，所以能赢当且仅当有棋子四步就能走到边上。

下面是棒到不行的1900及以上的题。

1404B : 感觉自己会一点猜结论了（考虑如果b>2a，那么B可以一步跨过A，所以B只要走到直径的一端并且直径边数至少是2a+1她就赢了(可以反复横跳)，但是也有可能还没轮到她A就一步干掉她了。否则A必胜，策略是走到直径中点。

455B : 这个k显然可以根据奇偶性干掉，然后看到前缀考虑trie，我们在trie上dp，设f[u]=0/1表示u这个点先手的输赢，那么转移非常显然。

好了上面是错误做法，既然要进行很多轮，那么如果只进行一次的话，这个游戏先手必胜，两个人肯定都希望最后一轮自己是先手，反之亦然，所以我们在trie上分别dp出想赢和想输的情况，然后分类讨论即可。这确实是一道容易降智的题。

1383B : 好题，我不会。按位贪心，考虑如果这一位有偶数个1，那么不管怎么拿，两个人拿的1个数要么都是奇数，要么都是偶数，所以没有关系。如果有奇数个1，那么先手能赢当且仅当拿到其中奇数个1。

然后我们考虑后手模仿先手什么时候能赢。如果两个人轮流只拿1，拿到最后先手拿了偶数个1(也就是1的个数是4k+3)，那么后手只要模仿先手就可以赢，但是这要求先手拿0的时候后手也要拿0，所以这种情况下有偶数个0时后手必胜，否则先手拿个0就必胜。

然后我们考虑1的个数是4k+1的情况，那么只拿1的话，后手会拿偶数个1，所以我们让先手先拿个1，然后模仿后手。同理，0有偶数个时模仿才有效。

135C : 输出只可能是\{00,01,10,11\}的子集，所以我们只要判断每一种输出有没有可能就好了。

考虑先手一定取1而后手一定取0。拿到最后如果剩下了11，说明1比0多至少一个；00说明0比1多至少两个(奇数，先手)。如果是01或10，说明两种数量相同或0比1多一个，此时因为先手不能拿0，后手不能拿1，所以拿成01当且仅当最后一个是1，其余都是10。

279E : 似乎不是博弈论而是纯构造?考虑对于末尾的一堆1，可以用一个2^k-2^0搞出来；对于中间的一堆1，也可以用一个(2^{k_1}-2^0)-(2^{k_2}-2^0)=2^{k_1}-2^{k_2}搞出来，这是两次操作；然后我们得到，可以用两次操作把一段取反，也可以用一次操作把一位取反，把每一段搞出来贪心选即可。然后你交上去发现过了(也许吧，反正是㗅)，然后去官方题解搬证明，然后发现没有官方题解¿

717D : 先考虑Nim先手必胜当且仅当各堆\operatorname{xor}和非0，所以问题变成n个数\operatorname{xor}和非0的概率。尝试dp，设dp(i,j)表示前i个\operatorname{xor}和为j的概率，然后有

倍增优化即可，发复杂度O(x^2\log n)，可以用FWT再优化做到O(x\log x\log n)。(看到题解只有一篇矩阵快速幂我还去写了代码)

69D : 没太看懂题，据说是记搜?

388C : 简单dp，先对每一堆求出前缀和，然后设dp(i,j)表示前i堆，先手拿了j张的最大和就做完了。

好了以上是错误想法。考虑如果你想拿某一堆的一半(当然，下取整)，那么你肯定能拿到。然后如果你觉得A这一堆的一半太小了，你希望放弃这一堆的一些，去更棒的B堆拿超过一半，那么这时候你的对手就不愿意了，她当然可以保证在B堆拿到一半，所以你的想法是不可行的。所以每一堆都是上下分别被两个人拿走。

但是如果一堆数量是奇数，这时候还剩一个，所以我们把数量是奇数的堆里面中间那个拿出来排序，然后两个人轮流选即可。

1147C : 妙啊，考虑如果有任何一堆空了但是游戏还没结束，那么接下来那个人大力取就可以赢。

如果有超过一半的1，那么先手肯定会取到至少一个1，所以她没了。

如果1不超过一半，先手可以取一些使得1超过一半，此时先手必胜——但是有一个小问题，如果根本没有1，先手取完了只剩一半1，她也没啦。

考虑没有1有2的情况，如果2超过一半，那么先手必须要取一些2，但她肯定不能把2取到1(转化成1不超过一半)，所以她只能取到0，所以她就输啦。如果2不超过一半，那就把2取到超过一半，所以她就赢啦。

所以归纳一下，我们得到，如果最小值超过一半，那么先手必败，否则先手必胜。

786A : 这个是移到1就赢，所以每个位置拆两个状态分别表示该先手/后手走，从1开始bfs/dfs即可。

896B : 实在是太妙了，请自行看题解。

15C : 好像很妙?考虑Nim先手能赢当且仅当\operatorname{xor}不为0，所以我们的任务变成了求一串东西的\operatorname{xor}，然后你可以打个表找规律，然后你就切了（

实际上，你发现每个偶数和它下一个奇数的\operatorname{xor}一定是1，所以拆成两个前缀然后判一下最后一个是奇数还是偶数就好了。