2019-Sp055-lyk
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(1.png,700px)]]
[[Image(2.png,700px)]]
[wiki:2019-team2 返回Runespoor]
[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001531 contest]
== 流水账 ==
== 总结 ==
'''zqq: ''' '''双打'''
这套题很有趣。感觉可以学到很多东西。
K题没有做出来很遗憾。'''打表的姿势不足，打表要耐心，好好确认是否用了正确的方式，打表很多时候是做出一道题的关键！'''
然后I题的模板有很大问题，用起来很不熟练，没有自己整理过。其实400行的板子需要抄的也就200行左右。虽然我们双打粘了板，其实这样不好。
前面暴力部分以为很简单，结果太慌了调了很久，不够冷静。
其他题都很简单，感觉我们过得偏慢。
'''Heltion:''' nmd怎么想到的从自由群也能出计数题.
=== 题解 ===
http://clatisus.com/Petrozavodsk%20Winter-2019.%20300iq%20Contest%201#k.-knowledge
* A ： 感觉是一道经典匹配问题的变形。'''普通网络流是做不了既有只得、又有斜的的情况'''但是我们发现只有'+','*'的格子才会作为中心，然后可以把这两个格子拆成两个点(x1,x2),连边(x1,x2) , 如果是* ， 连(x1,上下）,(x2，左右）。如果是'+' ， 两个都连上下左右。然后跑一般图最大匹配。如果拆出的两个点都被匹配，则合法。正确性：如果可以通过替换多一个合法解，则一定存在增广路，和最大匹配矛盾
* D ： hall定理。发现可以按pi从大到小贪心，判定是看所有覆盖当前区间的区间是否都还有容量。因为区间的左右端点同时递增，一个区间[l,r]覆盖的区间个数等于右端点小于等于r - 左端点小于等于l，线段树维护S(r) - w(r) >= S(l - 1) - w(l - 1) , 每次区间减一。
* I ： 题意等价于联通块大小 <= 6 ， 然后发现每个联通块的染色数是度数 = 点数 + 1的多项式。先暴力dp再插值计算出多项式，然后分治fft，然后多点求值。模板非常混乱再加上暴力没有想清楚，调了很久，很不应该！
* K ： 打表发现只有12个等价类（'''这个打表要把长度开大一点，然后耐心的等待，否则无法得到12个，它可能先加到比较长然后在缩短'''）。然后发现加一个'a','b'是等价类之间的转化。发现加一个其实是可以看做大小为4的置换，这12个等价类可以表示成大小为12的置换群（其实是4的所有偶排列）。然后矩乘
=== 补题 ===
* A :
* E :
* G :
* H :
* J :
* K : zqq
流水账
总结
zqq: 双打
这套题很有趣。感觉可以学到很多东西。
K题没有做出来很遗憾。打表的姿势不足，打表要耐心，好好确认是否用了正确的方式，打表很多时候是做出一道题的关键！
然后I题的模板有很大问题，用起来很不熟练，没有自己整理过。其实400行的板子需要抄的也就200行左右。虽然我们双打粘了板，其实这样不好。
前面暴力部分以为很简单，结果太慌了调了很久，不够冷静。
其他题都很简单，感觉我们过得偏慢。
Heltion: nmd怎么想到的从自由群也能出计数题.
题解
http://clatisus.com/Petrozavodsk%20Winter-2019.%20300iq%20Contest%201#k.-knowledge
- A ： 感觉是一道经典匹配问题的变形。普通网络流是做不了既有只得、又有斜的的情况但是我们发现只有'+','*'的格子才会作为中心，然后可以把这两个格子拆成两个点(x1,x2),连边(x1,x2) , 如果是* ， 连(x1,上下）,(x2，左右）。如果是'+' ， 两个都连上下左右。然后跑一般图最大匹配。如果拆出的两个点都被匹配，则合法。正确性：如果可以通过替换多一个合法解，则一定存在增广路，和最大匹配矛盾
- D ： hall定理。发现可以按pi从大到小贪心，判定是看所有覆盖当前区间的区间是否都还有容量。因为区间的左右端点同时递增，一个区间[l,r]覆盖的区间个数等于右端点小于等于r - 左端点小于等于l，线段树维护S(r) - w(r) >= S(l - 1) - w(l - 1) , 每次区间减一。
- I ： 题意等价于联通块大小 <= 6 ， 然后发现每个联通块的染色数是度数 = 点数 + 1的多项式。先暴力dp再插值计算出多项式，然后分治fft，然后多点求值。模板非常混乱再加上暴力没有想清楚，调了很久，很不应该！
- K ： 打表发现只有12个等价类（这个打表要把长度开大一点，然后耐心的等待，否则无法得到12个，它可能先加到比较长然后在缩短）。然后发现加一个'a','b'是等价类之间的转化。发现加一个其实是可以看做大小为4的置换，这12个等价类可以表示成大小为12的置换群（其实是4的所有偶排列）。然后矩乘
补题
- A :
- E :
- G :
- H :
- J :
- K : zqq