首先恭喜 jly!!! Orz，然后怎么还没人写题解？我来对着标程口胡一下 = =。

• https://codeforces.com/blog/entry/128559
• https://github.com/SnapDragon64/ACMFinalsSolutions/tree/master/finals2023

Problem Y. Compression

相邻的相同元素都先压缩掉，然后因为只有..010101… 所以连续删除末尾偶数个字符，直到长度 <= 3 即可。

Problem P. Turning Red

第一反应解模线性方程，但是有一个灯至多只关联两个按钮这个额外条件，因而知道一个按钮的状态，就能立刻推出另一个，于是就变成签到题了。

我们将灯和按钮视作二分图，对于每个连通块，我们只需要枚举其中任意一个按钮的状态，其它按钮的状态就都能确定，在 dfs 的过程中看有没有矛盾即可，代码也很像二分图判定。

Problem W. Riddle of the Sphinx

脑经急转弯，先问 a,b,c,a+b+c，如果不自洽那么要么是前面 a,b,c 错，那么 a+b+c 错。此时我们再问 a+2b+3c，如果和 a,b,c 仍然不自洽那么说明其中有一个是假的，但此时我们可以通过后两问的线性组合，得到不依赖其中一个元素且百分百正确的询问，从而寻找出哪一个询问为假。

Problem Q. Doing the Container Shuffle

非常有趣的概率题，第一反应当然是利用期望的线性性质，每个轮次独立讨论，感觉像是某种逆序对的板子。

但是有个麻烦的点是这个移动的过程会有一些后效性，破坏之后的状态。。。
但是发现分类讨论之后，这个过程居然产生的影响也是局部的！直接取 min(cur, last) 进行每个轮次的询问即可 Orz。

Problem V. Three Kinds of Dice

看起来又是概率题，但实际是几何题。

首先考虑第三枚骰子只有一面的情况，我们枚举它的取值，就可以快速求出对另外两个骰子的胜率。然后 x、y 轴分别是对另外两个骰子的胜率，我们发现这些取值在平面上形成一些离散的点，而任意多面的情况，就是这些离散的点在平面上的线性组合所构成的区域，然后 lrj 曾经告诉我们，这个东西其实是一个凸包。最后只要在这个凸包上做两条射线即可。

Problem T. Carl’s Vacation

三分套三分。

Problem X. Quartets

看起来很像是并查集（食物链）什么的，但是好像是网络流。。反正我还没整明白囧。

Problem R. Zoo Management

说给你一个图，每个结点有一个标号，你唯一可以调整标号的方法，是沿着环旋转。
问是否能从初始状态旋转成目标状态。

总感觉在哪见过= =

首先桥边无法联络，所以先求 bcc，每个双联通分支独立讨论，用抽象代数的知识建模：
– 环，那么操作构成循环群，是最简单的情况，等价于判定字符串循环同构。。可以 https://oi-wiki.org/string/minimal-string/ （也可以后缀自动机）
– 仙人掌，那么构成对称群，直接返回 yes。
– 其它情况，那么构成交错群，求一下逆序对。

后面两种情况真的一点也不显然，问就是总感觉在哪见过。。。= =
https://en.wikipedia.org/wiki/Jordan%27s_theorem_%28symmetric_group%29

Problem S. Bridging the Gap

非常帅的一个题，过桥问题想必大家都见过，《大航海时代 IV》里还是哪一个遗迹的谜题我忘了，然后小时候看的一本吴文虎的图论小册子开篇也是这个谜题。这个题是原版问题的威力加强版，变成 n 个人，桥上最多能过 c 人，每个人给一个通过时间，看似修改不多，但难度一下子就上来了囧。

我对着 std 和题解视频（which is wrong）大眼瞪小眼想了好几天都没想通，最后还是羞耻的跑去看了论文，看到一半终于悟了。
首先 std 开幕雷击。。那个神似背包的（就是背包，还是完全背包） 的 cc 我就看不懂。。
这是因为我们对过河的结构缺乏 insight 导致的。。。论文大部分都在研究这个结构，并不断简化。。。

首先有一种最直觉的贪心。。就是最快的人反复过河去带其他人。。。
很遗憾，样例它就错了。。。我们发现样例里有最慢的两个人一起过河的情况。。这样次慢的那个人就可以避免成为瓶颈被统计。。。

但是我们还是先找找这个贪心有哪些地方是做的对了！！

首先。。回来的队伍一定是单独一个人。。。多回去没意义。（状态直接减半有没有！）
其次。。最快的那个人确实是最有成为火炬手的潜力的。。
所以我们先对所有人按速度从慢到快排序，总是先想办法把当前最慢的一批人送过河。。

…

经过一番挣扎。。我们发现实际上过河的队伍只有三种情况。。。
第一种。。当前 C 个最慢的人。。这 C 个人永远不会回来。。所以除非它们是最后一批，否则需要之前至少有一个先锋队成员在右岸。。（定义一下先锋队，就是过了河还会回来的同志，一定是速度最快的那一波人）
第二种，当前 C-i 个最慢的人，和 i 个最快的人，这 i 个先锋队成员里除了 1 个人要立刻返回之外，剩下 i-1 个成员之后可以当作资源再利用。。。而我们上面的贪心，实际恰好对应了每轮次都自产自销的情况。。
最后一种。。。当前最快的 i 个人。。。这种情况纯粹为了产生更多的先锋队。。

所以 dp[i][j] 就是，已经运完了前 i 人（从慢到快），且还倒欠 j 个先锋队的情况。。。。
这种通过电表倒转，引入未来状态的 dp 技巧。。我们也不是没见过。。对吧！（但是这个题里有正有负）（https://www.spoj.com/problems/ZUMA/

再回顾一下上面的三种情况。。。
1. 纯贫下中农队伍（透支 1 个先锋队）
2. i 个先锋队成员带领 C-i 个贫下中农组成的混合队伍，（积攒 i-1 个先锋队）
3. 纯 i 个先锋队成员组成的先锋队伍（积攒 i 个先锋队）

然后最后这个代码里的完全背包现在也很好丽洁了吧！就是对应上面分析的最后一种情况，因为这种情况对顺序不敏感，我们单独拎出来处理，极大的降低思考复杂度，然后 1 和 2 实际可以合并成一种状态转移来枚举，代码里的：
– mnc 就是最多倒欠几个先锋队可以 clear。（保证了复杂度是 O(n2)）
– mxc 就是最多当前可攒多少个先锋队。（再多就溢出后面没必要了，算是个小优化）