[[模拟]] [[概率期望]] [[DAG 链剖分]] [[最大权闭合子图]] [[KMP 自动机]]

前情提要

Link

今天没考好啊，但是要注意身体，早睡早起。

题解

T1

一个简单的模拟，由于太害怕失误了，导致花费了将近一个小时。

以后还是要心态好一点。

遇到模拟不要紧张。

错不错全看人品。

T2

想到了一个组合数的做法，但是没有想出的。当时感觉是很像 Catalan 数，但是忘记 Catalan 数怎么推的了，这道题就没有推出来（失望）。但是现在记住了！

T3

本来都想得挺好，但是当我把前面都处理好了（求出每个军队的贡献），然后准备算整体的时候不会了（）。我当时是想把强连通分量给缩点的，成为一个 DAG，又不费了。只好打了个指数级的暴力，前面的努力白费了（）。

最后看到别人暴力，发现还有没有相互关系的点。血亏。

后来发现这就是最大权闭合子图，啊，还是做题做少了。就是网络流的思路啊。

这里为什么是最小割感觉大家都讲得不是很清楚，我讲讲我的理解：

相当于先把正的权值点选了，但由于出边肯定最终结果会选择一些（可能没有）负权点，再删除一些（可能没有）正权点，最后形成一个闭合子图。

那么，照着标准做法连边以后，要减去的权值刚好就是正权点的和再加上负权点的和。由于建图时负权的点的边变为正的了，相当于就是这两种边连向源汇点的和，要最小，最后还要使得剩下的没有多余的出边。所以这就刚好满足最小割的定义，割掉的正权边是删掉的，割掉的负权边是增加的，剩下的没删掉的不会指向删掉的，不连通刚刚好。所以是最小割。

还有一个细节。前面求军队贡献的时候不能带，可以按位置分配到桶中排个序就可以递增来选择了。

妙极了。

T4

不会，据说是有 DAG 链剖分。

网上还找到了题解：

link1

link2

用到了 KMP 自动机，学习学习。

后记

还是要多做题啊 (￣▽￣)*