10/10
【UER #10】随机薅羊毛 - 题目 - Universal Online Judge (uoj.ac)
【概率期望】
神他妈，要是往计数想就寄麻了。概率期望不仅可以计数，枚举，当然可以用解方程系列方法做，不要忘了。
令 表示第一次选了 的次数期望：
其中 ，把方程加起来，可以容易解得所有答案。
CF1392G Omkar and Pies - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
【DP】【TO】
mmp，又被转换教育了。
这题的重点不是交换操作本身，因为它没什么性质，所以我们最要关心的是如何把区间拍成前缀或后缀。
选择一段区间 ，得到的答案相当于将 做 的操作， 做 的操作，再来比对它们的相同元素个数。
然后还有一重消弱就是我们只要知道了它们相同的 的个数，就可以知道相同位置总个数，稍微容斥一下即可。
因为串长很小，所以我们枚举最终它们的公共 的集合，统计一下包含他的 的最小编号，和 的最大编号即可。
CF1389G Directing Edges - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
【最优化】【双连通】【DP】【TO】
CF1383F Special Edges - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
【网络流】
太离谱了。FF算法居然可以比 Dinic 还优。
【计数】【DFS树】【随机化】
拆平方贡献。
首先由结论，方案数可以直接求，， 是连通块数量，因为任意选好树边之后选非树边的方案是唯一的。
然后拆平方贡献，若当前删掉了 条边 ，贡献为 。
的系数就是方案数。
考虑组合意义，枚举每一条边，统计钦定删除的情况下的方案数，关注 变化即可。
就是钦定两条边必须删除，只有删两条树边的情况不平凡，由于删两条树边导致 当且仅当覆盖它们的非树边几何相同，于是我们给每一个非树边上一个 long long 的随机权值，比较集合可转为比较异或和。
CF1383C String Transformation 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
【构造】【最优化】【TO】
首先需要转换，建出图 ，我们的目标转换为，按照时间顺序向新图 中加有向边，要求原图中每一对 在 中都存在一条时间递增的路径。
那么我们可以有一个最简单的构造，把每个点都串在一起变成一条链，除了从 到 的位置以外，都要有一条重边。这样是 。
然后考虑优化，考虑并不是每一个点对都要互相可达，那么我们可以找出 中的一个最大 DAG （点集），把最大 DAG 中的点按照拓扑序排到链的最前端去，那么最前面的这一段链就不需要安排重边了。由于 DAG 中的到达关系只需要满足按拓扑序顺序的点对即可，合法性依旧，最优性没毛病。
求解最大 DAG 只有 dp。
那么 ， 为 的弱联通块数量。
AT4505 [AGC029F] Construction of a tree - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
【网络流】【构造】【HALL】【TO】
先判断，再构造。
先观察出可以构造的充要条件，发现 HALL 定理的条件是这个充要条件的必要条件，于是可以建出二分图跑匹配，在跑完的匹配上搜索构造。
CF1436F Sum Over Subsets - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
【计数】【莫反】
拆平方套路+莫反。
【构造】
没有转换成一个更清晰的目标，实在是太不应该了。
目标可转换为要选择一个连通块集合，他们的大小之和为 ，这样里面的红点和外面的蓝点就可以构成合法独立集。
抽屉原理，一定可以构造得出来。
【TO】【组合】
/jie 论。。。
最后肯定只剩下 ，考察一下结论，发现合法当且仅当 ，其实画一些子结构可能可以观察出来。
充分性的话，删去若干元素后，一定可以变成一个下降子序列接上上升子序列。
枚举 插入元素组合计数。经典的拆开后吸收。
标签：洛谷,cn,luogu,计算机科学,构造,list2,com,杂题 From： https://www.cnblogs.com/chenyinjin/p/16626631.html