2017-Sp214-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，cjb和yzc讨论了下A，yzc上机wa了，发现少了case，'''A2y20'''。看榜发现大家都过了D，cjb猜了结论冲上去'''D1y26'''。之后sub开了H丢给cjb，cjb上机'''H1y38'''。yzc上机写J，'''J1y43'''。sub上机写E，'''E3y76'''。cjb推了F的式子丢给sub然后上机敲NTT，之后sub '''F1y115'''。yzc上机写G，写了一大半，cjb开出了正确解法，上机敲了lct给yzc，sub中途上机'''L1y162'''。之后G wa了，对拍之后'''G3y208'''，最后cjb和yzc开I和M，I一直没猜出科学的结论，sub上机写K，炸了之后下机思考，最后15min上机rush，'''K1y298'''。
== 总结 ==
=== chenjb ===
感觉今天很爽？压哨绝杀sub有点牛逼啊？
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：一定可以做到次大值减最小值，如果最大值存在至少两个，则最大值减次小值也能做到，取最优即可。

 * B：

 * C：

 * D：无cycle输出0，否则输出1

 * E：答案是<=n的2的幂次，直接取2的幂次即可。

 * F：推公式可以求得和自己reverse的NTT。

 * G：a[i]向右边第一个a[i]或a[i]+1连边，用lct维护link和cut，某个值改变的时候暴力重构这个点所有连向这个点的点和这个点可能会连向这个点的点。

 * H：将行和列分开排序后只考虑相邻的边，跑kruskal。

 * I：yzc

 * J：答案是每个点到目标距离和的一半。

 * K：树形dp，f[i][j][k]代表答案为(j,k)的状态数，然后再去维护只满足左侧纳什均衡和右侧纳什均衡的状态数即可dp。

 * L：答案是prufer序且没人过n/2，直接计算。把比赛视为边，结果是棵树，即可推得。

 * M：cjb

流水账

出门各自看题，cjb和yzc讨论了下A，yzc上机wa了，发现少了case，A2y20。看榜发现大家都过了D，cjb猜了结论冲上去D1y26。之后sub开了H丢给cjb，cjb上机H1y38。yzc上机写J，J1y43。sub上机写E，E3y76。cjb推了F的式子丢给sub然后上机敲NTT，之后sub F1y115。yzc上机写G，写了一大半，cjb开出了正确解法，上机敲了lct给yzc，sub中途上机L1y162。之后G wa了，对拍之后G3y208，最后cjb和yzc开I和M，I一直没猜出科学的结论，sub上机写K，炸了之后下机思考，最后15min上机rush，K1y298。

总结

chenjb

感觉今天很爽？压哨绝杀sub有点牛逼啊？

oipotato

subconscious

题解

  • A：一定可以做到次大值减最小值，如果最大值存在至少两个，则最大值减次小值也能做到，取最优即可。
  • B：
  • C：
  • D：无cycle输出0，否则输出1
  • E：答案是<=n的2的幂次，直接取2的幂次即可。
  • F：推公式可以求得和自己reverse的NTT。
  • G：a[i]向右边第一个a[i]或a[i]+1连边，用lct维护link和cut，某个值改变的时候暴力重构这个点所有连向这个点的点和这个点可能会连向这个点的点。
  • H：将行和列分开排序后只考虑相邻的边，跑kruskal。
  • I：yzc
  • J：答案是每个点到目标距离和的一半。
  • K：树形dp，f[i][j][k]代表答案为(j,k)的状态数，然后再去维护只满足左侧纳什均衡和右侧纳什均衡的状态数即可dp。
  • L：答案是prufer序且没人过n/2，直接计算。把比赛视为边，结果是棵树，即可推得。
  • M：cjb
附加文件