2017-Sp218-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，很快发现F是树上打架，cjb上了个树链剖分，yzc上去写线段树，'''F1y42'''。之后跟榜过了'''A1y46'''，cjb发现H是李超线段树，上了个板子后，让sub先写I，cjb和yzc研究离散化细节。之后跟榜开了E，sub '''I1y127'''。cjb和yzc确认E做法之后上机写E，数组开小了一发'''E2y158'''。cjb上机抄hopcroft，sub跟进'''J1y191'''。终于让yzc上机写H了，很顺利'''H1y211'''。之后cjb上机仙人掌，后来发现dp细节不太对，sub努力搞G无果，rk6。MIT 8，MSU 8，Atcoder Team 8，东大 7，KAIST 7。
== 总结 ==
=== chenjb ===
李超线段树很好很强大！今天dirt非常低，感觉不错，希望继续保持。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：都是偶数同时除2，一奇一偶则奇*2，两个奇则把小的加到大的身上。

 * B：

 * C：

 * D：

 * E：费用流模型很明显，由于最后午饭和晚饭一定各增广n的流，考虑手动模拟增广，每次增广一次午饭，一次晚饭就行了。模拟方式就是午饭，晚饭各用两个set取出增量最小的即可。

 * F：树链剖分，然后数字打架取答案。存在答案肯定能打架胜出，最后用主席树check下数字出现次数是否符合即可。

 * G：

 * H：离线询问之后在dfs过程中维护根到当前点的李超线段树，记录修改的节点，返回时暴力恢复即可。

 * I：考虑在序列自动机上，求必经点树，发现是每个数组下标维护一个vector，vector支持push_back，和后缀lca，类似单调队列，倒过来再做一遍即可。

 * J：所有边权视为n-1跑hopcroft，最后留个老师，然后从这个老师往回广搜即可。注意判无解。

流水账

出门各自看题，很快发现F是树上打架，cjb上了个树链剖分，yzc上去写线段树，F1y42。之后跟榜过了A1y46，cjb发现H是李超线段树，上了个板子后，让sub先写I，cjb和yzc研究离散化细节。之后跟榜开了E，sub I1y127。cjb和yzc确认E做法之后上机写E，数组开小了一发E2y158。cjb上机抄hopcroft，sub跟进J1y191。终于让yzc上机写H了，很顺利H1y211。之后cjb上机仙人掌，后来发现dp细节不太对，sub努力搞G无果，rk6。MIT 8，MSU 8，Atcoder Team 8，东大 7，KAIST 7。

总结

chenjb

李超线段树很好很强大！今天dirt非常低，感觉不错，希望继续保持。

oipotato

subconscious

题解

  • A：都是偶数同时除2，一奇一偶则奇*2，两个奇则把小的加到大的身上。
  • B：
  • C：
  • D：
  • E：费用流模型很明显，由于最后午饭和晚饭一定各增广n的流，考虑手动模拟增广，每次增广一次午饭，一次晚饭就行了。模拟方式就是午饭，晚饭各用两个set取出增量最小的即可。
  • F：树链剖分，然后数字打架取答案。存在答案肯定能打架胜出，最后用主席树check下数字出现次数是否符合即可。
  • G：
  • H：离线询问之后在dfs过程中维护根到当前点的李超线段树，记录修改的节点，返回时暴力恢复即可。
  • I：考虑在序列自动机上，求必经点树，发现是每个数组下标维护一个vector，vector支持push_back，和后缀lca，类似单调队列，倒过来再做一遍即可。
  • J：所有边权视为n-1跑hopcroft，最后留个老师，然后从这个老师往回广搜即可。注意判无解。
附加文件