2019-Sp036-lyk
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(1.png,700px)]]
[[Image(2.png,700px)]]
[http://acm.zju.edu.cn/pia/trac/wiki/2019-team2 返回Runespoor]
[https://codeforces.com/gym/101667 contest]
== 流水账 ==
== 总结 ==
'''zqq: ''' 前期我们比较落后。主要是因为我睡过了迟到了10分钟，把我们的节奏搞得很乱。
今天题目简单，但是我们的策略还是有挺大问题的。
我刚来就看到lyk在写B，结果他1小时40分钟才过。这么大的题还是稍微冷静一下比较好？有些时候一定要会了就马上写。
今天A题本来是非常简单的，但是我们开始做这道题就太晚了，A是一道前期题啊！然后就是我的锅了，一开始DP的状态推得仍然不够清楚，输出调试才发现错。后来DP两维下标弄反了，一直出现诡异的错误。调了半个多小时
还有H题，本来是一个非常简单的FFT,一开始想错了一个地方，最后调了很久。感觉自己贡献了今天所有罚时。
'''题要想清楚再上去写。不要每次等到WA了或者错了才来找自己算法的错误！'''
我们今天J题的开得太早了，这道题一看就不简单。对于这种图论很难的题目，我们的姿势还差挺多！
''' lyk: ''' B题是个傻逼暴搜，但是我暴搜逻辑上有些问题，一直过不了样例。因为题特殊，没法上机调试，而且机位很紧张，中间一直放着。
== 题解 ==
* J ： 这道题有三种做法，但是一种我都不知道为什么。大多数人都用了结论：对任意点，取其相邻点集为S ( S = x | N(x)) , 然后找到邻边包含在S中的所有点T。充要条件是：|S| - min(n / 2,|T|) >= n / 2
而我们只想到 (N(x) - |x|) >= n / 2 对任意点集成立。但是应该把点集的限制转化成单点才有办法做。我们有一段时间还以为这是NP问题，对匹配的姿势真的需要提高。
这题也可以网络流。对每个点拆点成(i1,i2) , 连边：（i1,i2,1）,(a2,b1,1) , (b2,a1,1) (a,b是原图中的边） 然后枚举(i,j) 以i2为S，j1为T，跑最小割。答案必须>= n / 2。参见https://codeforces.com/gym/101667/submission/44020777
也有随机化做法。参加https://codeforces.com/gym/101667/submission/36279559
== 补题 ==
* J: []
流水账
总结
zqq: 前期我们比较落后。主要是因为我睡过了迟到了10分钟，把我们的节奏搞得很乱。
今天题目简单，但是我们的策略还是有挺大问题的。
我刚来就看到lyk在写B，结果他1小时40分钟才过。这么大的题还是稍微冷静一下比较好？有些时候一定要会了就马上写。
今天A题本来是非常简单的，但是我们开始做这道题就太晚了，A是一道前期题啊！然后就是我的锅了，一开始DP的状态推得仍然不够清楚，输出调试才发现错。后来DP两维下标弄反了，一直出现诡异的错误。调了半个多小时
还有H题，本来是一个非常简单的FFT,一开始想错了一个地方，最后调了很久。感觉自己贡献了今天所有罚时。
题要想清楚再上去写。不要每次等到WA了或者错了才来找自己算法的错误！
我们今天J题的开得太早了，这道题一看就不简单。对于这种图论很难的题目，我们的姿势还差挺多！
lyk: B题是个傻逼暴搜，但是我暴搜逻辑上有些问题，一直过不了样例。因为题特殊，没法上机调试，而且机位很紧张，中间一直放着。
题解
- J ： 这道题有三种做法，但是一种我都不知道为什么。大多数人都用了结论：对任意点，取其相邻点集为S ( S = x | N(x)) , 然后找到邻边包含在S中的所有点T。充要条件是：|S| - min(n / 2,|T|) >= n / 2
而我们只想到 (N(x) - |x|) >= n / 2 对任意点集成立。但是应该把点集的限制转化成单点才有办法做。我们有一段时间还以为这是NP问题，对匹配的姿势真的需要提高。
这题也可以网络流。对每个点拆点成(i1,i2) , 连边：（i1,i2,1）,(a2,b1,1) , (b2,a1,1) (a,b是原图中的边） 然后枚举(i,j) 以i2为S，j1为T，跑最小割。答案必须>= n / 2。参见https://codeforces.com/gym/101667/submission/44020777
也有随机化做法。参加https://codeforces.com/gym/101667/submission/36279559
补题
- J: []