2016-C03-team2
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||User||Problem||Result||Memory||Time||Length||Submit Time||
||TaZoF||C||CE|| || ||1742||2016-08-03 14:09:06||
||TaZoF||C||MLE|| || ||1772||2016-08-03 14:07:45||
||TaZoF||C||RE|| || ||1771||2016-08-03 14:07:12||
||TaZoF||C||TLE|| || ||1278||2016-08-03 14:02:29||
||TaZoF||F||AC||0||15||984||2016-08-03 13:48:34||
||TaZoF||C||TLE|| || ||901||2016-08-03 13:47:12||
||TaZoF||H||AC||11552||156||2245||2016-08-03 13:28:37||
||TaZoF||H||WA|| || ||2151||2016-08-03 13:13:32||
||TaZoF||D||AC||4||15||1203||2016-08-03 12:00:36||
||TaZoF||A||AC||4||15||1275||2016-08-03 11:51:16||
||TaZoF||A||WA|| || ||1154||2016-08-03 11:47:43||
||TaZoF||F||WA|| || ||992||2016-08-03 11:40:58||
||TaZoF||F||WA|| || ||480||2016-08-03 11:23:43||
||TaZoF||A||WA|| || ||1062||2016-08-03 11:12:45||
||TaZoF||A||WA|| || ||1062||2016-08-03 11:09:00||
||TaZoF||D||WA|| || ||1040||2016-08-03 10:46:57||
||TaZoF||D||WA|| || ||1040||2016-08-03 10:45:15||
||TaZoF||D||WA|| || ||1125||2016-08-03 10:39:54||
||TaZoF||D||WA|| || ||1117||2016-08-03 10:34:41||
||TaZoF||D||WA|| || ||1061||2016-08-03 10:29:09||
||TaZoF||D||WA|| || ||915||2016-08-03 10:17:58||
||TaZoF||D||WA|| || ||791||2016-08-03 10:09:00||
||TaZoF||I||AC||0||202||307||2016-08-03 09:42:34||
== 流水账 ==
=== TsReaper ===
今天题目难度比较大，没有简单题。我们队并没有练习过难度比较高的比赛，可能因此比赛节奏并不是很好。
练习开始后根据现场回放我们开始想I题，一段时间后我想到了一个二进制的做法，'''I1y32'''。hzf学长也想到了D的做法，但调了几次都没有答对。我们看到题目中提到了“自然数”，但并不知道欧洲人的自然数是从0开始还是从1开始（练习结束后发现D题的自然数和G题的自然数不一样~~感觉欧洲人有毒~~）。我们商量了一下觉得可能是从1开始的，但是hzf学长改了改还是没有答对。学长决定再考虑一下，我就上机写模拟题A，然而也没有答对。同时卡两题比较郁闷，我debug的时候hzf学长猜了F的结论，但是还没有答对，我们队的罚时就比较爆炸。debug一段时间后我觉得自己的A并没有写错，可能是题目里有特殊数据，不能用随机化的方式判断，要构造几个特殊情况。两种方法一起判断后'''A4y161'''（练习结束后据说其他队的学长一把就答对了，感觉自己脸太黑...）。之后又帮hzf学长debug F,发现学长的程序不能通过极限数据，INF开小了。修改后'''D8y170'''。
Starve学长根据现场回放觉得H应该很可做，上机写了一段时间，并用一些特殊数据调了一下'''H2y258'''。剩下的题目应该只有F可做了，因为我们没有带数学手册，就向fengsuiyan学长借了一本，结果fengsuiyan学长正好翻到结论那一页- -确认了猜测的结论正确后，hzf学长发现可能是因为没开long long，改了改'''F3y278'''。最后一点时间Starve学长乱搞C。
=== 3z ===
学长说的好！
== 总结 ==
=== TsReaper ===
* 比较困难的比赛我们队可能不是很有节奏。
* 记得开long long，INF要开大。
=== 3z ===
* 前期节奏太差，三开了一段时间，虽然最后都做出了，但是这样太冒险了
* 思路不清晰，或者样例没手算的情况下不要写代码，很容易崩掉
* 对于一些思考的技巧还是没有把握好，比如B题，发现修改次数多的话，就应该往适当增加查询的复杂度来降低修改的复杂度方向想，当时却只想了常数优化。。
=== hzf ===
* 注意开long long...
* 要正确估计极限数据的范围
* 交题不能太莽了...
== 题解 ==
=== B - Tree of Almost Clean Money ===
因为修改的次数太多了，用普通的DFS序+树状数组的套路会TLE.
我们可以用分块让复杂度更偏袒修改。同样记录树的DFS序，进入新节点和从节点出来都要记。设bgn[x]表示新进入第x个节点的DFS序，end[x]表示从第x个节点出来的DFS序。如果给x的权值加上v，可以把bgn[x]位置加上v，再把end[x]位置扣去v。容易发现，bgn[x]的前缀和就是从根到x的权值之和。这样我们分块维护，O(1)修改，O(sqrt(n))查询即可。
=== E - Taxies ===
因为C(15,1)+C(15,2)+C(15,3)+C(15,4)约为2000不会太大，我们完全可以先用spfa求出公司和15个人的家两两间的最短距离，再枚举每一种坐车情况和下车顺序，用一个2^15^的状压dp（表示当前已经把哪些人送回家，枚举下一辆车的坐车情况进行转移）就能解决了。
其实程序并不会很难写，如果今天节奏比较好的话，这题应该还能再答对。
=== I - Olympic Parade ===
因为空间限制太小，不能一次性读入所有数然后排序（其实可以刚好卡过，但是题目本意应该不是这样）。
考虑把所有数弄成二进制，如果所有数二进制第i位1的个数不能被K整除，说明答案的二进制第i位是1.
== 补题 ==
=== TsReaper ===
~~B~~, C, ~~E~~| User | Problem | Result | Memory | Time | Length | Submit Time |
| TaZoF | C | CE | 1742 | 2016-08-03 14:09:06 | ||
| TaZoF | C | MLE | 1772 | 2016-08-03 14:07:45 | ||
| TaZoF | C | RE | 1771 | 2016-08-03 14:07:12 | ||
| TaZoF | C | TLE | 1278 | 2016-08-03 14:02:29 | ||
| TaZoF | F | AC | 0 | 15 | 984 | 2016-08-03 13:48:34 |
| TaZoF | C | TLE | 901 | 2016-08-03 13:47:12 | ||
| TaZoF | H | AC | 11552 | 156 | 2245 | 2016-08-03 13:28:37 |
| TaZoF | H | WA | 2151 | 2016-08-03 13:13:32 | ||
| TaZoF | D | AC | 4 | 15 | 1203 | 2016-08-03 12:00:36 |
| TaZoF | A | AC | 4 | 15 | 1275 | 2016-08-03 11:51:16 |
| TaZoF | A | WA | 1154 | 2016-08-03 11:47:43 | ||
| TaZoF | F | WA | 992 | 2016-08-03 11:40:58 | ||
| TaZoF | F | WA | 480 | 2016-08-03 11:23:43 | ||
| TaZoF | A | WA | 1062 | 2016-08-03 11:12:45 | ||
| TaZoF | A | WA | 1062 | 2016-08-03 11:09:00 | ||
| TaZoF | D | WA | 1040 | 2016-08-03 10:46:57 | ||
| TaZoF | D | WA | 1040 | 2016-08-03 10:45:15 | ||
| TaZoF | D | WA | 1125 | 2016-08-03 10:39:54 | ||
| TaZoF | D | WA | 1117 | 2016-08-03 10:34:41 | ||
| TaZoF | D | WA | 1061 | 2016-08-03 10:29:09 | ||
| TaZoF | D | WA | 915 | 2016-08-03 10:17:58 | ||
| TaZoF | D | WA | 791 | 2016-08-03 10:09:00 | ||
| TaZoF | I | AC | 0 | 202 | 307 | 2016-08-03 09:42:34 |
流水账
TsReaper
今天题目难度比较大，没有简单题。我们队并没有练习过难度比较高的比赛，可能因此比赛节奏并不是很好。
练习开始后根据现场回放我们开始想I题，一段时间后我想到了一个二进制的做法，I1y32。hzf学长也想到了D的做法，但调了几次都没有答对。我们看到题目中提到了“自然数”，但并不知道欧洲人的自然数是从0开始还是从1开始（练习结束后发现D题的自然数和G题的自然数不一样感觉欧洲人有毒）。我们商量了一下觉得可能是从1开始的，但是hzf学长改了改还是没有答对。学长决定再考虑一下，我就上机写模拟题A，然而也没有答对。同时卡两题比较郁闷，我debug的时候hzf学长猜了F的结论，但是还没有答对，我们队的罚时就比较爆炸。debug一段时间后我觉得自己的A并没有写错，可能是题目里有特殊数据，不能用随机化的方式判断，要构造几个特殊情况。两种方法一起判断后A4y161（练习结束后据说其他队的学长一把就答对了，感觉自己脸太黑...）。之后又帮hzf学长debug F,发现学长的程序不能通过极限数据，INF开小了。修改后D8y170。
Starve学长根据现场回放觉得H应该很可做，上机写了一段时间，并用一些特殊数据调了一下H2y258。剩下的题目应该只有F可做了，因为我们没有带数学手册，就向fengsuiyan学长借了一本，结果fengsuiyan学长正好翻到结论那一页- -确认了猜测的结论正确后，hzf学长发现可能是因为没开long long，改了改F3y278。最后一点时间Starve学长乱搞C。
3z
学长说的好！
总结
TsReaper
- 比较困难的比赛我们队可能不是很有节奏。
- 记得开long long，INF要开大。
3z
- 前期节奏太差，三开了一段时间，虽然最后都做出了，但是这样太冒险了
- 思路不清晰，或者样例没手算的情况下不要写代码，很容易崩掉
- 对于一些思考的技巧还是没有把握好，比如B题，发现修改次数多的话，就应该往适当增加查询的复杂度来降低修改的复杂度方向想，当时却只想了常数优化。。
hzf
- 注意开long long...
- 要正确估计极限数据的范围
- 交题不能太莽了...
题解
B - Tree of Almost Clean Money
因为修改的次数太多了，用普通的DFS序+树状数组的套路会TLE.
我们可以用分块让复杂度更偏袒修改。同样记录树的DFS序，进入新节点和从节点出来都要记。设bgn[x]表示新进入第x个节点的DFS序，end[x]表示从第x个节点出来的DFS序。如果给x的权值加上v，可以把bgn[x]位置加上v，再把end[x]位置扣去v。容易发现，bgn[x]的前缀和就是从根到x的权值之和。这样我们分块维护，O(1)修改，O(sqrt(n))查询即可。
E - Taxies
因为C(15,1)+C(15,2)+C(15,3)+C(15,4)约为2000不会太大，我们完全可以先用spfa求出公司和15个人的家两两间的最短距离，再枚举每一种坐车情况和下车顺序，用一个215的状压dp（表示当前已经把哪些人送回家，枚举下一辆车的坐车情况进行转移）就能解决了。
其实程序并不会很难写，如果今天节奏比较好的话，这题应该还能再答对。
I - Olympic Parade
因为空间限制太小，不能一次性读入所有数然后排序（其实可以刚好卡过，但是题目本意应该不是这样）。
考虑把所有数弄成二进制，如果所有数二进制第i位1的个数不能被K整除，说明答案的二进制第i位是1.
补题
TsReaper
B, C, E
附加文件
- 2016-C03-team2.zip by TsReaper
- B.c by TsReaper
- E.cpp by TsReaper