我意识到了我做 DP 的严重问题。我非常习惯于说去推结论和性质，结果迟迟没有开始试图设计状态。对 DP 理解的非常的不深刻。在推性质的时候应该主动像 DP 上靠。而不是先推再说。要主动地设计状态，尝试几种经典的状态设计。然后试图找出关系。或者是先找出子结构之间的联系。 DP 的本质就是子结构。要主动洞察这个题目有哪些子结构，以及他们之间的良好性质，而不是仅靠“发现”。 我觉得我设计暴力 DP 这件事比 DP 优化更困难。因为我并没有养成这种良好的思维习惯。 开始正题。 这个题目首先就是我们 feel 一下这个题目。 一个 native 的想法是考虑从小到大以 popcnt 为层推进。然后呢你其实可以把他看成一个金字塔。然后你想一下，比如说你当前先把单个元素染个色。然后对于横跨的，怎么办？实际上对于这些横跨的不能随便染色，反例：RBBR 13 24 R 14 23 B 然后就炸了。 然后呢我就摆了，也许是畏惧吧。 你其实可以推进一步，你思考为什么会炸。 因为 R 和 B 的并都是 S。 然后显然 R 和 B 的并不能都不是 S。 然后如果 S 是 R 那一定是 R 的并是 S。反过来同理。 实际上现在你可以直接开始试图设计状态了。 比如你很经典地你设 $f_{S,0/1}$ 为 $S$ 内染色，然后颜色为 $0/1$。然后这个时候你想怎么转移。 你发现你好转移啊，你找这个并不是当前颜色的并。然后你发现其实这个并一定得是对应的 $f$ 然后你直接转移即可。 优化用脚优化。你直接一个一个加即可，套路。

观察 1: 这个区间其实跟左端点的关系不大，跟右端点关系更大。 于是我们可以想到从左到右考虑，于是乎我们发现了一个 $O(n^2)$ 的做法。 我们设我们当前决策了是否要激活 $[1,i]$ 且激活了 $i$ 的最大代价为 $f_i$。 然后转移就是枚举 $j < i$，然后减去多于代价，加上新的。 我们考虑优化他。 首先新的贡献是跟 $j$ 无关的。 然后剩下的呢，我们考虑我们往右扫。维护右端点在 $i$ 右边的区间。然后你把他们的左端点放在线段树里，你每删除一个线段，就在对应的区间内将线段树减一。然后相当于要区间 $y_i$ 加，区间 $x_iy_i$ 最小值。然后你发现这是 KTT 板子。 做完了。

自己想出来了。 他这个 $p_1$ 和 $p_n$ 的限制本质上是因为一个排列和其颠倒过来的是不可区分的，因此我们只要最后判一下即可，之前完全不需要考虑这个条件。 首先他既然说 randomness 那我们就 random。 然后我们看到 $\mod 3$ 我们应该要向同余类的方向想。 然后我们如何获得同余类？这个是好做的，对于每个点，随机取一个点，query 一下，选到同余类的点的概率为 $\cfrac{1}{3}$，因此我们期望 $3n$ 次获得同余类。 然而我们并不知道同余类哪个是 $0,1,2$ 然而其实我们只要知道循环的方向即可。然后我们发现循环的方向都不需要知道，因为循环方向变了就是排列翻转了，我们随便指定一个方向。 然后我们发现我们已经可以比较大小了，如果 $x,y$ 不在一个同余类里，则可以比较但同余类内部无法比较。 我们相当于要做这个排序。而排序本质上是用子结构堆起来。（不管是什么排序） 然而我们发现如果在当前子结构中有两个相同同余类的点对其他所有的结果都相同我们根本没法区分。 但其实我们根本不用区分，我们把这些东西打包起来，要用的时候拿我们当前的值对这些东西依次问一遍。 然后我们感觉一下我们发现这个期望并不会增加多少的询问次数。因为一个很大的连续同同余类的段的出现概率指数下降。 然后我们其中一个想法是使用插入排序，每次二分大概位置，然后暴力扫描，使用平衡树即可，但实现难度有点高。 另一个想法是，我们使用归并排序。我们每次在归并的时候，如果遇到大包就把他们两两问一遍，这个明显容易的多。

非常欢迎跟我在评论区随机说话。 萨特有一句话 存在先于本质。我不想认同，因为我觉得存在主义根植虚无主义，是对他的一种“扬弃”。但我不理解为什么一定要有本质呢。一切事物可以只是存在，不需要有本质和意义，那我大可以想做什么就做什么，不受意义和本质的束缚。但你可能要问了，那我的这种思考是不是我的本质的一部分呢。当然是啊，他也许确实是对的。但我既然可以做我任何想的事，那我自然也可以不认同“真理”咯。而且再者我他只是不需要有本质和意义，如果你硬要加，也是可以的，你乐意就好了。我大可以在我想要认同他的时候认同他，你觉得我做的这种是选择是本质那他可以是，但不一定是，我不喜欢他是本质，于是在我这里他就不是。别人当然也可以不认同我啊，这种事情家常便饭。 起点是 意义焦虑，我突然反应过来不是所有东西都要有意义。例如天上的流星，他并不是为你而流，你却声称他对你有意义。这很荒诞。因此我说，事物不需要有意义，当然比如你给别人送的钻戒他可以有意义，但不是一定的，当他从工厂里生产出来的时候他是没有意义的。当他被放进墓中，墓的主人被人所遗忘之后，他又变得没有意义。就算他戴在一对夫妻的手指上，他对你可能也是没有意义的。那他有没有意义完全取决于你，你认同他们的爱情，他就有意义，你不想管他们，他就没有意义。进而拓展到真理，人们信真理是因为对他的信仰式崇拜，没有理由，因为任何体系无法自证。那我如果说，我不想管真理是什么，那你当然也可以认为真理没有意义，你不必认同他，但当你想研究问题的时候，你可以认同真理。 我是非常奇怪的。我在思考自身问题和思考宏大的社会问题的时候变得思维异常快速和敏锐，给我的感觉像完全不一样的一个人格，他 act as a watcher，换句话来说他做的是元认知工作。但大部分平常情况下都做不到这样的思维状态。 我不是讨厌情绪的，反而我非常喜欢他。但情绪会像狗狗一样咬人，这个时候我们要把他关起来。这听起来似乎是奇怪的，因为情绪，情感和理性已经深深根植于集体无意识和言语之中。但我们不是消灭他，而是让理性和他互相制约。从旁观的角度让他自然消失。怎么关？用理性结构把他拆散，解构。一枚核弹是威力巨大的，但核材料，外壳，引爆装置的威力远不如他。情绪的作用来源于他的整体。就好像人是有思想的，但头部，四肢，躯干是没有思想的。这是表面上的解构。而进一步的解构是离他远远的，看清楚他。要自我制造疏离感。通过陌生化，旁观化，来消除他带来的作用。通常的办法是调用另一个人格。情绪不是一个真实物体，当他的作用消失了，那他本体就消失了。 但这只是把狗狗关起来，还要想办法安抚他，不然开了笼子他又会跑出来。通过代理发泄或者直接发泄的方式可以让他不再压抑到心底，而是让他自然消散，变成经验。常见的代理发泄：rock，breakcore。直接发泄：随机说话。但你要这样想：我们既然花了这么大的代价把他关起来，总得让他长长记性。于是我们可以重新去思考，这个事情是为什么发生的，这时你用的是 watcher 的话通常会得出一个看起来很像废话的结论，但完美规避了对自我价值的否定。因为往往我们否定自己只是因为过度解读。 我最喜欢的就是想做什么做什么，这同时给了我消极自由和积极自由（也许听起来很奇怪）。这是完全符合我对主体性的追求的。我当然是没有完全主体性的（由于无意识人类也不可能做到），但这构成了一个主体性++的循环。但我一直追求的都是 truly 愉悦。你判断一个愉悦是否 true 需要你开 watcher。比如我明显觉得我刷知乎是完全不 true 的。因为我看到的 99.9% 是激烈的观点输出与立场站边，我觉得我看到了新思想。实则都是一个个张嘴闭嘴价值判断。而剩下的 0.1% 呢？也许有营养但完全不足以补足我的损耗。这种情况下我是被渴望的多巴胺所掌控了的。而 truly 的愉悦像是我在写这些东西。我觉得我得到了一种向外输出的快感，尽管可能全是问题和漏洞。但有漏洞，矛盾和问题那我就更开心了，这展开了新的思考方向。而且有趣的是 truly 愉悦与在真实中有助于生活的更好的活动是高度重合的，有可能是人类和其社会的进化演变出的无意识吧。 我之前似乎是喜欢去刻意追求归属感和认同感的。但我逐渐意识到这比较唐。归属感的来源是在于你在一个集体中给你带来的愉悦。但这个愉悦有两种，一种是“属于集体”本身的愉悦。另一种是与具体的人的联结的愉悦。“属于集体”这种愉悦的来源是你期望获得与具体的人的联结。这在确实有具体的人时是一大动力。但现在的网络社会到处都是标签，每个标签都在引诱你：贴上这个标签并加入这个群体。而我们真的就被这所吸引，贴上了这个标签，并假想自己身后有一个庞大的群体在为你撑腰。这与所谓的“想象的共同体”有异曲同工之妙。但往往你的身后这个真正的群体并不存在。他们只是一个个主动给自己贴上了标签的人。这个时候你与他们产生联结，只是因为你们都想获得一个联结，而不是基于人对人的直接联结。这种联结往往提供不了更多的情绪价值。而反而你为了维护自己越来越多的标签与人设中丧失了自己的主体性，而且你一直在渴望，却从未得到，这是彻底的 false 愉悦。这也是为什么我说：“we want, we ask, we build then we act as it, until realizing it’s not true.” 先写这么多。 更。 说到理性压制情绪，便要谈到情绪压制理性，正如我开头所说的，我并不是纯粹的理性主义者。我曾经是，但我逐渐意识到了其根本上的问题，一来逻辑或者说理性本质上考查的是数学结构或者说逻辑结构，他是基于关系的，他预设几个公理然后推导，这相当于是命题与公理的关系，而不是命题的内在属性。而放到生活的选择之中就出现极大的问题，不存在一个所谓的先验的绝对目的，我们生活之中会根据所见调整目的便是最好的证明，而因此所谓的公理则无从谈起。逻辑在认知和论断上显得苍白无力。二来正如我所说，情绪，情感等他是作为整体存在的，他们可以拆开，但拆开后的加和不再是其本身，而逻辑追求第一性原理，天然地想要去把他拆开。我不得不承认我与尼采的思想不谋而合，在我知道尼采之前，我就有过关于一整个我称之为“狂”和“强唤醒度低指向性”情绪的思维架构，我同样指向了直接泼洒情绪的艺术作为载体的模式。这在现在看来其实就是所谓的关于酒神和生命力的讨论。至于尼采的具体思想我在此不赘述。说到这里我承认我是向往艺术的。从我“开智”以来我好像一直在寻求表达，一种能直接传递的情绪浪潮。无论以什么形式，我总感觉在表达的时候有一种深层次的快感，尽管在外人看起来无比笨拙。 更。 是你醉了，还是我醉了？ 我真的很喜欢写意识流的东西，这给我一种不加磨损的直接表达。 我最早喜欢音乐是当时误打误撞听到了凛冽时雨，然后我觉得戳上 xp 了。我真的很喜欢这支乐队，我听过他们所有的专辑，他们真的很意识流。虽然我其实一直都有听电音，但当时听的都很糖，都是些烂大街的东西。然后又因为一些奇怪的原因接触到了 breakcore，因为这个原因我突然发现了新大陆。 我一直怀疑人是否拥有真切意义上的主观能动性。比如一个决策，你如果什么都不知道，那你的决策就是在瞎蒙，如果知道些什么，那说明就是你知道的这些驱使你去做的这个决定，而不是你。就算你选了一个决策，那大概率还是因为你本身就有选这个决策的倾向，而不是你真的决定了。 因此我突然意识到整个理性主义社会的追责和因果链都是同一个逻辑：个人以上，是可讨论的，个人以下，是你自己的问题。他断在了个人这个点上。比如一个人杀了人，法律不会追究最终让他有杀人倾向的那个人而是直接处决杀手。换句话来说，他把所有的责任都抛给了某个明确的个体，这似乎是不利于体系发展的，但他运作了几千年。 我的一个解释是：即使是今天意识仍然是未解之谜，对于每个人来讲，他人的意识是黑盒，他害怕试图拆开黑盒。再者拆开黑盒的成本过高，以至于无法承担。因此就使用了这种方法。另一方面是人总是得有一个发泄对象的，如果你说一个杀人事件的原因是社会的某个问题，那被害者的家属会怎么看？但我认为随着技术的进步，黑盒逐渐会变得透明，而整个人类逻辑将会被改写。 也许我说的这些都是一些半吊子的话，半瓶水叮当响。 我确实是对其有一定兴趣，但并没有系统性地学习过或者严谨地思考过，我也许只是在胡思乱想。 这也许像一个中二少年装逼日志，那就让他是吧，不然可能过些年也没什么好留念的了。 再者我的语文水平烂的不能再烂了。我写的作文，满地都是雷点，很意识流，而且没有任何文学性的表达（事实上我已经很久很久很久没有读过文学性的书籍了）。虽然有人说我写的有特殊的质感但我更倾向于这种东西并没有什么用处。 不过我确实是着迷于这整个世界是如何运转的。因此我涉猎相对广泛，但也极度皮毛。 也许我有生之年并做不到这一点。但我还是这么期盼着。 人类的文明，人类的社会是一个极其复杂的机器。但这给了渴望的灵魂以无尽的素材。 但这里也藏着最深的悖论，我们拿着人类发明的语言去试图解释他，必然会遇见一定不可调和的矛盾。 而艺术，尤其是音乐，这也给了我一种解构的欲望。 ...

牛牛题。 先讲我自己想到的部分。 首先最大流肯定不好做，做最小割。 然后显然有最小割树。 但现在问题出在如何求最小割上。 一个很大的问题是，你求最小割至少都要考虑所有的即一定是 $\Omega(n)$。 然而如果这样时间复杂度就已经爆了。 我一直的思路都是用数据结构扫描线啊啥的维护发现很难做。（也许可以做？我好像看到有人用 DS，有可能是把不同的步骤在 DS 上合在一起吧。） 然后题解做了个很厉害的事情，他说：平面图我们要想到对偶图。 好的我们考虑他的对偶图。 我们考虑我们求一次最小割，是在做什么事情。 我们发现在对偶图上就是把 $s$ 和 $t$ 伸两条射线出去，然后做对偶图，就是上下两个无限平面的最短路。 如果只是想到这里，我们只是得到了一个 $\Omega(n\log n)$ 的算法，但其实无论如何，这已经优于我们的朴素 DS 了（而且我们的朴素 DS 很难写）。 我们想一下我们的根本诉求是什么，我们的根本诉求是，把这个最小割树转化为其他东西，而不是直接求最小割（因为这样一定会爆）。 但若是我们继续想。我们递归之后做的是什么呢，我们做的其实是把左右分成两半，然后对于左边，就把右边整个缩为一个点，右边同理。 我们首先就是想到，我们无论怎么分，实际上最多只有 $n$ 个无限平面，我们干脆提前分好，然后我们发现我们变成了是选两个无限平面使得最短路最短。 实际上这就是在树上找最近的两个叶子。 我们试图继续用这种找两个的方式选，然后我们想到我们既然不要这两个点，那我们把这俩合起来。我们看其他最小的两个叶子。 Creatively，我们发现我们在做 kruskal。 然后我们不想做 kruskal。 面对 MST 最好用的就是 boruvka。 然后我们使用 boruvka。 我们如何找树上每个叶子最近的不同块的叶子呢。 我们可以使用 DP，从下到上做一遍，从上到下做一遍，记录最小次小即可。 然后我们就建出来了合并无限平面的树。 但我们要得是最小割树。 于是我们再对偶回去即可。 就这个题最本质的 idea 是，你可以“发现你在做一个经典问题然后换一种解法”。比如把 kruskal 换成 boruvka。 这仍然是灵活迁用，更本质的来说，这是把方法之间建立活的联想连接，而不是感觉连接。这对发散性思维有很高的要求。、 然后其他一些重要的是平面图用对偶图。 还有就是提前处理的思想，把无限平面分成 $n$ 个也可能是一个卡点。 还有呢，就是一个贯彻思想的做法。比如你第一下找的是最近叶子，那你肯定也希望接下来也是最近叶子。 透过现象看本质。

如果前面的是怪物题，那这个是克苏鲁题，不可名状，只能感性理解。 什么逆天东西啊喂！ 首先我们得先看懂题，注意 Torus 指的不是球，他实际上你硬要画出来是一个…甜甜圈。 但我们还是在矩形纸上考虑问题吧，不然太难描述了。 我们可以把他假想成，一个无限延伸的平面，上下左右都复制当前纸，这样直观一点。 好的，我们想象一下，一个环可以长什么样。 他首先不能在纸上是一个圆对吧这样切了就爆了。 他能是怎么样的？他肯定至少要能穿过边界对吧，然后呢他这个要求联通，等价于说你要按照这个环切了之后呢，存在一个连通块，满足他进行在 $x$ 和 $y$ 上都进行类似 mod 的操作重叠在一起后覆盖了整个矩形。 或者本质一点，他应该是，所有的连通块，全等？？？ 我感觉是这样的。 然后我们发现他实际上画在这个无限平面上呢，是类似一堆这个同一个方向的线，类似平行，但是可能扭来扭去。 显然我们可以在无限平面上任意平移这个我们考虑的矩形。 然后显然我们根据拓扑原理，你是直的是弯的的是根本不重要的，你只要交点结构一样即可。 你交点的这个位置是不重要的，重要的是你交点在整个图形中的层次与地位。 然后你发现就非常多的画环的方式都是等价的，比如一个横线是一个等价类，一个竖线是一个等价类，一个对角线也是一个等价类。他们的特点都是可以通过连续地平移矩阵，或者连续地扰动这个路径得到同一个地方。 然后我们有一个非常重要的感性理解，就是其实像比如说无论是横的啊，竖的啊，对角线的啊，还是缠两圈的对角线啊，甚至自己跟自己交错的神秘斜线。他们本质相同。我们都可以通过旋转和缩放我们所观测的这个矩形来发现，比如一个对角线，你给他转一下再缩放一下，对角线就变为竖线了。因此我们可以选择最简单的横线和竖线思考问题。 然后我们可以开始思考问题了。是的现在才开始思考问题。 我们注意到，如果等价类 $\ge 3$ 个，那他们必定共点。 不然因为你不能边相交，三个拓扑上方向不同的一定会围出我们不想要的环。 然后我们发现这等价于仙人掌上所有环共点。 我们试图构造，发现这是好构造的，你就钦定一个中心点，然后向外辐射即可。 只要满足这个条件就是 Yes。 显然剩下的树你随便挂在一边即可。 如果等价类 $=2$ 个，那他们要么共点，要么其中一个等价类只有一个环，且与其他所有的环相交。 理由同理，如果共点的话我们在第一个情况就算过了，不用管。 如果是一个等价类只有一个环，且与其他所有的环相交，这相当于一个川中间画了一横。 然后这个东西你发现你可以看成是，仙人掌上的所有其他环都挂在一个特定的环上。 这个也是好判的，你记 $i$ 在 $c_i$ 个环里，你只要看 $\sum c_i = sz+cnt-1$ 即可。 然后如果只有一个等价类，我们发现他一定得是一堆竖线，然后一个横线段（不是横直线）贯穿。 这等价于所有的环都挂在一条链上，你建出圆方树进行简单的树形 DP 即可。 然后我们终于理解完了这个题目。但也只是理解，至于证明？ 我们伟大的信息学，不需要证明。

非常非常厉害厉害的题目，总算是自己做出来了个厉害题。 首先显然正难则反。 嗯。我们一个想法呢，是说，我们可以按点分类，分成 A 点：连接 1 2 的点，B 点：1 3, C 点：2 3, X 点：1 2 3, O 点：无。 然后呢，我们想一下啊，我们发现我们只要把 ABC 中不同的两个点，连起来，然后就一定是一条合法路径。 当然这个有 corner case，就是如果是个三元环，那就爆了。 为什么呢？因为两点都连有不同的两种颜色，所以满足。 所以似乎这个如果有 ABC 点的话，那只能有这一种，换句话来说只能有两种颜色。 好的，然后 X 点同理，你发现，这个如果有 X 点似乎其他必须得是 O 点。 然后你写完发现样例过不了。 为啥呢，因为 corner case。 然后你很容易发现，我们如果是 X 点的情况，因为 corner case，我们如果两个不同颜色的边连到了同一个点双里，那就爆了，因为会形成一条路。 然后另一种情况就是，你根本没有 X 点，你可能是有一堆奇奇怪怪的三元环（如样例 1），他因为俩点接到同一个点上了，所以爆了。 然后你怎么着一下，然后就把这个情况全部判掉，然后就过了。

怪物题目。 我一直在想正着做，然后就爆了。 我们考虑反着做。 首先你解放一条边，显然这条边一定得是红蓝边重合。 然后你解放倒数第二条边，然后你发现他一定得是红蓝边分别连接了两个相同的这个解放块。 然后你发现你相当于是合并解放块的过程。 然后你干脆啊，直接就给他启发式合并，把整个块变成一个点，然后他就相当于要求红蓝边是重边。 显然因为两个是树，所以呢你根本不用区分哪个是红边哪个是蓝边，直接找重边即可，因为树不可能有重边。

广义串并联好题。 首先我们看到 $m \le n + 13$ 这个就是广义串并联。 其次，对于这种东西，我们可以把点双搞出来，这个简单路径的限制如果是难点可以用点双解决。 首先肯定不可能出点双再进来。 你考虑我们发现如果 $1$ 和 $n$ 不在一个点双以内，那我们直接就连一条 $1,n,L$ 的路径显然不会更改答案。 所以我们直接考虑它点双。 好的然后我们既然用的是这个广义串并联，我们就要考虑 $K_4$。 然后你发现，如果有这个 $K_4$ 就一定存在 $>L$ 的路径。 然后我们知道他是广义串并联，然后我们缩图即可。 而且注意到 $1$ 和 $n$ 是可以不缩的，如果不缩导致不行说明也是不行的（类似 $K_4$ 的分析） 重边显然是要 check 边长短。 二度点显然把两个长度加起来即可。 这个告诉我们的就是说这个 VCC 非常的好用在简单路径中。 以及这个广义串并联看到部分分就要想到。 或者更本质的来说，你如果是要搞类似这种就是一排排过去，长得跟毛细血管一样的，那就是可以试试广义串并联。

唐唐题。 考虑直接开导！ 我们很容易发现我们画在图像上，我们一定是优先节省这个费用最大的东西。 然后我们把每次增广的这个流过去的流量与每流一次的代价啥的都算出来。 然后直接贪心即可。