2020-team06/C1002
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
- 在此记录一些尚无法被归档入正式组队训练中的l1ll5参加的训练
[2020/11/12] [https://codeforces.com/gym/101623 2017-2018 Northwestern European Regional Contest (NWERC 2017)]
[2020/11/13] [找不到打的哪场了，留坑]
[2020/12/01] [https://codeforces.com/gym/102860 2020-2021 Saint-Petersburg Open High School Programming Contest (SpbKOSHP 20)]
[2020/12/26] [https://codeforces.com/gym/100520 Winter Petrozavodsk Camp, Andrew Stankevich Contest 45 (ASC 45)]
[2021/01/04] [http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010312 XVI Open Cup named after E.V. Pankratiev. GP of Japan]
2021 Petrozavodsk and Shanghai ICPC Training Camp Day 4 problem I solution :
题意：
给一个n个点的完全图，边有颜色。将其扩展到(m+1)阶完全图，并且m染色，判断是否可行并输出方案。
题解：
Lemma 1：考虑最终所有 m(m+1)/2 条边，按照颜色分组，仅当每组都有(m+1)/2条边且m为偶数时有解
Proof：考虑边数最多的一组，令其有 x 条边，则其覆盖了 2x 个点，min(x) = (m+1)/2 ，当m为偶数时，2x=m，否则组内有重复点。
现在考虑n个点的情况，同样考虑最终的m组，将每组的(m+1)/2条边分为三类：
2-set：两个端点均已经在目前的图中出现
1-set：仅有一个端点在目前的图中出现（某点x的目前所有边中没有这个颜色，则在最终的图中必然有这种颜色的一条边）
0-set：以上两种情况之外的边，即完全没有出现。
Lemma 2：对于给出的情况，若没有某一组的1-set边数加2-set边数超过(m+1)/2，则有解。否则无解。
Proof：无解显然，为了证明有解，只需证明一个满足如上性质的图一定可以加一个点。（归纳，加一个点的影响是将边从1-set变成2-set（加某个颜色的边）或者从0-set变成1-set（不加某个颜色的边），不影响组内边数）
考虑用网络流解决该问题：对于每种颜色，将其和对应的1-set（n个点）或0-set（1个点）连边。其中0-set到T连一条m-n，其余都是1
显然源点总共发出m的流量，汇点最多收到m的流量。
不妨令每个颜色的点发出去的所有流量均相等，此时发现该网络满流。（不会证）
则最大流为满流，任取一整数最大流则对应一个方案。依次扩展到m+1个点即可。
感觉非常的玄妙。
因为l1ll5博客炸了，平时补的一些题就放在这里了。
CF 717 E
长度为n的排列，swap k次，能得到的不同排列数。
一个思路是考虑这个的逆过程，对所有swap j次能得到一个1-n的排列的排列计数，只需要考虑最后一个元素是否为错排即可
dp i j = dp i - 1, j + (i - 1) dp i - 1, j - 1
ans_i = dp[i][k] + dp[i - 2][k] + ... 这里考虑到浪费操作数就是交换相同对
但是复杂度是与n有关的，不妨考虑枚举做了k次swap，影响到了i个元素，答案乘一个C(n,i)即可
显然有重复，怎么避免呢，考虑只要枚举的i个元素都是错排即可不重不漏，容斥这个过程即可。- 在此记录一些尚无法被归档入正式组队训练中的l1ll5参加的训练
[2020/11/12] 2017-2018 Northwestern European Regional Contest (NWERC 2017)
[2020/11/13] [找不到打的哪场了，留坑]
[2020/12/01] 2020-2021 Saint-Petersburg Open High School Programming Contest (SpbKOSHP 20)
[2020/12/26] Winter Petrozavodsk Camp, Andrew Stankevich Contest 45 (ASC 45)
[2021/01/04] XVI Open Cup named after E.V. Pankratiev. GP of Japan
2021 Petrozavodsk and Shanghai ICPC Training Camp Day 4 problem I solution :
题意：
给一个n个点的完全图，边有颜色。将其扩展到(m+1)阶完全图，并且m染色，判断是否可行并输出方案。
题解：
Lemma 1：考虑最终所有 m(m+1)/2 条边，按照颜色分组，仅当每组都有(m+1)/2条边且m为偶数时有解
Proof：考虑边数最多的一组，令其有 x 条边，则其覆盖了 2x 个点，min(x) = (m+1)/2 ，当m为偶数时，2x=m，否则组内有重复点。
现在考虑n个点的情况，同样考虑最终的m组，将每组的(m+1)/2条边分为三类：
2-set：两个端点均已经在目前的图中出现
1-set：仅有一个端点在目前的图中出现（某点x的目前所有边中没有这个颜色，则在最终的图中必然有这种颜色的一条边）
0-set：以上两种情况之外的边，即完全没有出现。
Lemma 2：对于给出的情况，若没有某一组的1-set边数加2-set边数超过(m+1)/2，则有解。否则无解。
Proof：无解显然，为了证明有解，只需证明一个满足如上性质的图一定可以加一个点。（归纳，加一个点的影响是将边从1-set变成2-set（加某个颜色的边）或者从0-set变成1-set（不加某个颜色的边），不影响组内边数）
考虑用网络流解决该问题：对于每种颜色，将其和对应的1-set（n个点）或0-set（1个点）连边。其中0-set到T连一条m-n，其余都是1
显然源点总共发出m的流量，汇点最多收到m的流量。
不妨令每个颜色的点发出去的所有流量均相等，此时发现该网络满流。（不会证）
则最大流为满流，任取一整数最大流则对应一个方案。依次扩展到m+1个点即可。
感觉非常的玄妙。
因为l1ll5博客炸了，平时补的一些题就放在这里了。
CF 717 E
长度为n的排列，swap k次，能得到的不同排列数。
一个思路是考虑这个的逆过程，对所有swap j次能得到一个1-n的排列的排列计数，只需要考虑最后一个元素是否为错排即可
dp i j = dp i - 1, j + (i - 1) dp i - 1, j - 1
ans_i = dp[i][k] + dp[i - 2][k] + ... 这里考虑到浪费操作数就是交换相同对
但是复杂度是与n有关的，不妨考虑枚举做了k次swap，影响到了i个元素，答案乘一个C(n,i)即可
显然有重复，怎么避免呢，考虑只要枚举的i个元素都是错排即可不重不漏，容斥这个过程即可。