The 2021 ICPC Asia East Continent Final Contest (EC-Final 2021) 题解

· · 题解

Link

A. DFS Order

注意到一个点只有在其所有父节点被搜索后才会被搜索，故设点 p 的深度为 dep_p(dep_1=1)，子树大小为 siz_p，则点 p 最早和最晚被搜索到的时间分别是 dep_p,n-siz_p+1。

E. Prof. Pang and Poker

神金分讨题。记不小于 Pang 手中的牌的牌为大牌，否则为小牌。首先只有在 Bob 打出了一张小牌或 Alice 出了小牌且 Bob 跳过时 Pang 才可以出牌。依次考虑如下情况：

  1. Alice 手上只有一张牌。此时 Alice 必须将其打出，则 Pang 不会赢。
  2. Alice 手上没有小牌。此时若 Bob 选择一直跳过出牌则显然最后 Alice 会把牌出光。则 Pang 不会赢。
  3. Alice 手上最大的小牌比 Bob 手上所有的牌要大。若 Alice 将它打出，则此时 Bob 无法接牌，则 Pang 必赢。
  4. 若 Bob 手上只有一张牌，因为已经特判了情况 3，则此时 Alice 手上的小牌都不大于这张牌。则若 Alice 打出小牌时 Bob 打出这张牌即可获胜。故此时 Pang 不会赢。
  5. 如果 Bob 手上有两张小牌，则 Alice 之后一直选择跳过，则 Bob 在某个时刻必定打出一张小牌且手上还有另外的小牌。则 Pang 必赢。
  6. 若 Bob 手上没有小牌，则 Bob 能出牌就出牌。显然在 Alice 出小牌时 Bob 必定可以出牌。此时 Pang 无法出牌，则 Pang 不会赢。注意，在特判了情况 4、5、6后，Bob 手上只会有一张小牌且必定有大牌，下文省略这个事实。
  7. 若 Alice 手上只有一张小牌，则当 Alice 出大牌时 Bob 不管，否则出一张大牌。此时全场只有 Bob 有且仅有一张小牌，故 Bob 可以将其留到最后出，则 Pang 必定无法出牌，故其不会赢。
  8. 若 Alice 手上最大的牌不大于 Bob 最大的牌，则当 Alice 出大牌时 Bob 不管，否则出一张大牌。所不同的是，Bob 会把最大的牌和唯一一张小牌保留到最后出。若 Bob 只剩下了这两张牌，则打出最大的牌，此时 Alice 和 Pang 无法出牌，故 Bob 可以打出最后一张牌获得胜利。则 Pang 不会赢。
  9. 若 Alice 手上只有不超过三张牌，则因为特判了情况 2、7，故 Alice 此时手上必定有至少两张小牌，又因为特判了情况 8，且 Bob 手上最大的牌必然是大牌，故 Alice 手上必定有两张小牌和一张大牌（这也意味着 Alice 手上只有两张牌的情况被讨论过了）。若 Alice 一开始出的是小牌，则 Bob 任意出一张大牌，若 Alice 不接牌则一直出大牌，最后打出仅有的一张小牌获胜。若 Alice 在这中间接牌了，则放弃出牌。此时由于 Alice 打出的必然是大牌，故 Pang 无法接牌。则 Alice 只能打出手上最后一张小牌获胜。否则若 Alice 一开始出的是大牌，则仍然任意出一张大牌，由于此时 Alice 手上只有小牌，故其无法接牌。则一直出大牌，最后打出仅有的一张小牌获胜。故 Pang 不会赢。
  10. 若 Alice 手上最大的一张小牌比 Bob 手上最小的一张牌小，则当 Alice 出小牌时若 Bob 手上还有大牌则出大牌，否则可以打出小牌获胜。则 Pang 不会赢。
  11. 若以上所有情况均不满足，则 Alice 手上必定有两张以上的小牌，一张比 Bob 手上最大的牌还要大的大牌和若干用来占位以防止自己获胜的牌。则 Alice 开始时出除最大的小牌外任意一张小牌，则 Bob 必须接牌。则 Alice 放弃出牌直到 Bob 手上只有一张小牌，此时打出最大的那张牌，由于考虑了情况 8，故可以打出且 Bob 无法接牌。则 Alice 打出最大的小牌，由于考虑了情况 10，Bob 无法接牌，故 Pang 可以打出手上的牌从而赢得游戏。

上述的讨论覆盖了该题所有可能的情况，故此题被解决。

I.Future Coder

对 a_i 进行分讨：

最后要减去 (i,i) 的贡献，再将答案除以 2。

J. Elden Ring

不难发现每天都必须挑战 Boss。有以下两种情况：