2016-C05-team2
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||User||Problem||Result||Memory||Time||Length||Submit Time||
||TaZoF||I||WA|| || ||3972||2016-08-05 14:08:47||
||TaZoF||L||WA|| || ||1729||2016-08-05 14:05:44||
||TaZoF||I||TLE|| || ||3943||2016-08-05 14:02:31||
||TaZoF||I||TLE|| || ||3906||2016-08-05 14:00:36||
||TaZoF||I||TLE|| || ||3439||2016-08-05 13:53:18||
||TaZoF||I||TLE|| || ||3416||2016-08-05 13:50:40||
||TaZoF||B||AC||0||2689||1216||2016-08-05 12:20:36||
||TaZoF||L||WA|| || ||1687||2016-08-05 12:05:20||
||TaZoF||H||AC||0||0||4726||2016-08-05 11:33:52||
||TaZoF||F||AC||0||482||1641||2016-08-05 11:00:56||
||TaZoF||K||AC||0||1662||1038||2016-08-05 10:50:26||
||TaZoF||A||AC||0||3||1501||2016-08-05 09:47:30||
||TaZoF||D||AC||0||36||645||2016-08-05 09:43:40||
||TaZoF||A||WA|| || ||1450||2016-08-05 09:33:26||
== 流水账 ==
=== TsReaper ===
今天学长们发挥平稳。开场后学长们似乎都没有看到简单题，我就先上机写小模拟A题，获得全场第一WA。Starve学长看到D题可能比较简单，思考了一下'''D1y33'''。我调了调A发现读入没有初始化，修改后'''A2y37'''。之后一段时间我们分头看题，抉择之后感觉F和K可能比较可做。F题我们很快想到了做法，我上机写了一段时间后发现不能通过样例，就让Starve学长先写K。我与hzf学长讨论后发现了程序中的错误，在'''K1y100'''后'''F1y110'''。
Starve学长开始写计算几何H，我与hzf学长继续看题，选择思考L。因为之前做过一个在无限地图上的bfs，我想了一个L的做法，自我感觉十分科学~~完全不顾hzf学长的怀疑~~。'''H1y143'''后我上机写L并没有答对。在我写L的过程中两位学长讨论出了B的做法，Starve学长上机'''B1y190'''，我在吃午饭的时候也想了一个反例，感觉跳错了坑。
最后一个多小时我们在剩下的题目中选择了I，我想到了I的做法，不过复杂度似乎有点紧...因为是几何题就把写题的锅甩给了Starve学长，然而最后还是TLE了。练习结束后看看题解貌似的确是这样做的，可能是迷之卡常。
=== hzf ===
今天还是从最后4题开始看起，看了一遍感觉都没什么思路，由于几何题I的题意特别简洁，就先和starve学长说了，starve学长也和我说了D的dp做法，好像是很简单，就让starve学长去写了，果然1A，之后我们开始讨论K和F，K题starve学长提到了2sat，我也尝试构造了一下，不成功...F题tsr学长给出了计算每个初值的贡献的思路，starve学长提供了处理常数c的方法，非常科学，但是tsr学长的公式里写错了一个符号...我以为是他笔误没提醒他...导致他样例过不了...惨！我的锅...下次一定要发现错误就提醒队友啊...在tsr学长写F的过程中starve学长和我说了一种有点迷的K题做法，我听的有点迷糊..starve学长很快就上去写了...竟然过啦！强！
看了看榜，发现H题过的人很多，我读了题，发现的确很可做，和starve学长说了一下，starve学长就开始写啦。之后tsr学长开了L，并给出了一种有点迷的解法，我构了许多反例，tsr学长修改了许多次做法..最后一种做法我构不出反例...但是也证明不了...我虽然有点虚，但是感觉即使我能构出来，可能那时候tsr学长也已经写完了，所以不构了...开始和starve学长讨论B，starve学长给出了一种暴力的做法...复杂度一分析甚是可行..学长上机很快1a，然而tsr学长最后自己找出了返利..L没能通过...
最后的1小时左右我们选择开I，利用I坐标范围小的性质，得出了复杂度比较科学的做法，赛后证明确实是正解，但是总是蜜汁tle到比赛结束....
== 总结 ==
=== TsReaper ===
* 这几天猜了很多奇怪的结论都不正确...要和队友多讨论...
* 一般字符串的题读入是不需要清空的，但是今天的A略有特殊。
=== 3z ===
* 手速还是有待提高啊，写代码码模板太慢了
* 在测试样例数据的要注意没有输错样例
=== hzf ===
* 看到队友公式推错了要及时提醒那！还好今天没有贡献wa
== 题解 ==
ADH思维比较简单，略过...
=== E - Export Estimate ===
把询问从大到小排序，边也从大到小加入。对于一张有N个点的加入M条边后的原始图，输出图的点数就是N-(度数为2的点数)+(只由度数为2的点构成的环的数量)（因为一个环不可能全部被缩完，肯定会留下一个点）。同理，输出图的边数是M-(度数为2的点数)+(只由度数为2的点构成的环的数量)。
维护度数为2的点数很容易，问题就是怎么维护“只由度数为2的点构成的环的数量”。这个可以用并查集来维护，记一个isCir表示某个连通块是否可能成为“只由度数为2的点构成的环”。合并时细节很多，具体可以看一下补题代码。
== 补题 ==
=== TsReaper ===
B, ~~E~~, G, I, J, L
=== hzf ===
~~E~~, ~~F~~| User | Problem | Result | Memory | Time | Length | Submit Time |
| TaZoF | I | WA | 3972 | 2016-08-05 14:08:47 | ||
| TaZoF | L | WA | 1729 | 2016-08-05 14:05:44 | ||
| TaZoF | I | TLE | 3943 | 2016-08-05 14:02:31 | ||
| TaZoF | I | TLE | 3906 | 2016-08-05 14:00:36 | ||
| TaZoF | I | TLE | 3439 | 2016-08-05 13:53:18 | ||
| TaZoF | I | TLE | 3416 | 2016-08-05 13:50:40 | ||
| TaZoF | B | AC | 0 | 2689 | 1216 | 2016-08-05 12:20:36 |
| TaZoF | L | WA | 1687 | 2016-08-05 12:05:20 | ||
| TaZoF | H | AC | 0 | 0 | 4726 | 2016-08-05 11:33:52 |
| TaZoF | F | AC | 0 | 482 | 1641 | 2016-08-05 11:00:56 |
| TaZoF | K | AC | 0 | 1662 | 1038 | 2016-08-05 10:50:26 |
| TaZoF | A | AC | 0 | 3 | 1501 | 2016-08-05 09:47:30 |
| TaZoF | D | AC | 0 | 36 | 645 | 2016-08-05 09:43:40 |
| TaZoF | A | WA | 1450 | 2016-08-05 09:33:26 |
流水账
TsReaper
今天学长们发挥平稳。开场后学长们似乎都没有看到简单题，我就先上机写小模拟A题，获得全场第一WA。Starve学长看到D题可能比较简单，思考了一下D1y33。我调了调A发现读入没有初始化，修改后A2y37。之后一段时间我们分头看题，抉择之后感觉F和K可能比较可做。F题我们很快想到了做法，我上机写了一段时间后发现不能通过样例，就让Starve学长先写K。我与hzf学长讨论后发现了程序中的错误，在K1y100后F1y110。
Starve学长开始写计算几何H，我与hzf学长继续看题，选择思考L。因为之前做过一个在无限地图上的bfs，我想了一个L的做法，自我感觉十分科学完全不顾hzf学长的怀疑。H1y143后我上机写L并没有答对。在我写L的过程中两位学长讨论出了B的做法，Starve学长上机B1y190，我在吃午饭的时候也想了一个反例，感觉跳错了坑。
最后一个多小时我们在剩下的题目中选择了I，我想到了I的做法，不过复杂度似乎有点紧...因为是几何题就把写题的锅甩给了Starve学长，然而最后还是TLE了。练习结束后看看题解貌似的确是这样做的，可能是迷之卡常。
hzf
今天还是从最后4题开始看起，看了一遍感觉都没什么思路，由于几何题I的题意特别简洁，就先和starve学长说了，starve学长也和我说了D的dp做法，好像是很简单，就让starve学长去写了，果然1A，之后我们开始讨论K和F，K题starve学长提到了2sat，我也尝试构造了一下，不成功...F题tsr学长给出了计算每个初值的贡献的思路，starve学长提供了处理常数c的方法，非常科学，但是tsr学长的公式里写错了一个符号...我以为是他笔误没提醒他...导致他样例过不了...惨！我的锅...下次一定要发现错误就提醒队友啊...在tsr学长写F的过程中starve学长和我说了一种有点迷的K题做法，我听的有点迷糊..starve学长很快就上去写了...竟然过啦！强！
看了看榜，发现H题过的人很多，我读了题，发现的确很可做，和starve学长说了一下，starve学长就开始写啦。之后tsr学长开了L，并给出了一种有点迷的解法，我构了许多反例，tsr学长修改了许多次做法..最后一种做法我构不出反例...但是也证明不了...我虽然有点虚，但是感觉即使我能构出来，可能那时候tsr学长也已经写完了，所以不构了...开始和starve学长讨论B，starve学长给出了一种暴力的做法...复杂度一分析甚是可行..学长上机很快1a，然而tsr学长最后自己找出了返利..L没能通过...
最后的1小时左右我们选择开I，利用I坐标范围小的性质，得出了复杂度比较科学的做法，赛后证明确实是正解，但是总是蜜汁tle到比赛结束....
总结
TsReaper
- 这几天猜了很多奇怪的结论都不正确...要和队友多讨论...
- 一般字符串的题读入是不需要清空的，但是今天的A略有特殊。
3z
- 手速还是有待提高啊，写代码码模板太慢了
- 在测试样例数据的要注意没有输错样例
hzf
- 看到队友公式推错了要及时提醒那！还好今天没有贡献wa
题解
ADH思维比较简单，略过...
E - Export Estimate
把询问从大到小排序，边也从大到小加入。对于一张有N个点的加入M条边后的原始图，输出图的点数就是N-(度数为2的点数)+(只由度数为2的点构成的环的数量)（因为一个环不可能全部被缩完，肯定会留下一个点）。同理，输出图的边数是M-(度数为2的点数)+(只由度数为2的点构成的环的数量)。
维护度数为2的点数很容易，问题就是怎么维护“只由度数为2的点构成的环的数量”。这个可以用并查集来维护，记一个isCir表示某个连通块是否可能成为“只由度数为2的点构成的环”。合并时细节很多，具体可以看一下补题代码。
补题
TsReaper
B, E, G, I, J, L
hzf
E, F
附加文件
- E.cpp by TsReaper
- 2016-C05-team2.zip by TsReaper
- I.c by TsReaper