2017-Sp105-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，有人猛得过A，然后claris突然过L，三脸懵逼，yzc强行上A，'''A1y32'''。cjb想出了K做法却决定摸一会儿，sub试图上机写J，结果爆炸，cjb和yzc讨论出了L，cjb上机抄dominator tree板子，yzc补上，'''L1y81'''。cjb秒了G，让yzc上机写主代码，cjb上机写spfa，'''G1y120'''。yzc和sub讨论了C，cjb上机写K，之后交替上机，C获得wa，K获得tle，之后'''C3y176'''，cjb改成单哈之后wa了，查出小bug，'''K3y181'''。三人讨论想出了J的正确分治，yzc上机获得wa，sub上机写D，'''D1y230'''。之后终于找到J的错误，'''J3y235'''。cjb发现E是个old题，和yzc一起上机，tle后撸了个hopcroft过了，'''E3y285'''，sub上机rush F，wa了一发未能通过。
== 总结 ==
=== chenjb ===
说好的final不训练，结果还是偷偷训练了...Hopcroft怎么这么快啊，匈牙利真的有存在的必要？有些时候卡一些疑似数学题的时候，要考虑换下大方向，比如dp。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：Two-pointer即可。

 * B：cjb

 * C：按深度由浅到深取出lca。

 * D：f[i]等于min(max(f[j],time[i])+max(h[j+1]..h[i]))，根据max分类讨论两种转移，均可O(n)维护。

 * E：除a，每个点均恰有一条入边，同理除b，每个点恰有一条出边，则把边点放左边，新建2n-2个点代表选择，用hopcroft跑匹配即可。

 * F：sub

 * G：二分之后差分约束。

 * H：yzc

 * I：cjb

 * J：分治，每次从mid往左右扩展，然后计算包含mid的询问，则只需O(20)转移，分治下去即可。

 * K：不同询问长度只有sqrt(n)种，按长度暴力哈希，维护dp值。

 * L：最短路图，把边变点，跑dominator tree，统计子树大小即可。
== 补题 ==

流水账

开场各自看题，有人猛得过A，然后claris突然过L，三脸懵逼，yzc强行上A，A1y32。cjb想出了K做法却决定摸一会儿，sub试图上机写J，结果爆炸，cjb和yzc讨论出了L，cjb上机抄dominator tree板子，yzc补上，L1y81。cjb秒了G，让yzc上机写主代码，cjb上机写spfa，G1y120。yzc和sub讨论了C，cjb上机写K，之后交替上机，C获得wa，K获得tle，之后C3y176，cjb改成单哈之后wa了，查出小bug，K3y181。三人讨论想出了J的正确分治，yzc上机获得wa，sub上机写D，D1y230。之后终于找到J的错误，J3y235。cjb发现E是个old题，和yzc一起上机，tle后撸了个hopcroft过了，E3y285，sub上机rush F，wa了一发未能通过。

总结

chenjb

说好的final不训练，结果还是偷偷训练了...Hopcroft怎么这么快啊，匈牙利真的有存在的必要？有些时候卡一些疑似数学题的时候，要考虑换下大方向，比如dp。

oipotato

subconscious

题解

  • A：Two-pointer即可。
  • B：cjb
  • C：按深度由浅到深取出lca。
  • D：f[i]等于min(max(f[j],time[i])+max(h[j+1]..h[i]))，根据max分类讨论两种转移，均可O(n)维护。
  • E：除a，每个点均恰有一条入边，同理除b，每个点恰有一条出边，则把边点放左边，新建2n-2个点代表选择，用hopcroft跑匹配即可。
  • F：sub
  • G：二分之后差分约束。
  • H：yzc
  • I：cjb
  • J：分治，每次从mid往左右扩展，然后计算包含mid的询问，则只需O(20)转移，分治下去即可。
  • K：不同询问长度只有sqrt(n)种，按长度暴力哈希，维护dp值。
  • L：最短路图，把边变点，跑dominator tree，统计子树大小即可。

补题

附加文件