扔过去给校内当训练赛，顺便自己单挑了玩玩。

[A Bookshelf Filling]

solution

做法：推推式子，二分一下。

[B Lovely Fish]

solution

做法：推下式子，看成 后，发现等价于维护区间最大子段和状物，线段树即可。

[C Tree Division]

solution

做法：冷静一下可以发现就是基础的树形 dp，设 表示放 集合的最小/大值的最大/小值，分八类讨论转移即可。时间复杂度 。

[D Collision Detector]

solution

做法：计几，推一下发现就是一些叉积点积等东西算算角度。

[E Exclusive Multiplication]

solution

做法：可以发现 ，经典地枚举分母的值，然后枚举倍数，用莫比乌斯函数转化 结构，观察一下就是两个调和级数处理的东西。时间复杂度 。注意下这种题都是可能数相同的，所以要记录的是每种权值出现次数而不是每种权值。

[F 342 and Xiangqi]

solution

做法：可以发现路线一定可以不交叉，所以每个象单独分类讨论即可。

[G Chevonne’s Necklace]

solution

做法：容易证明每一种背包对应一组合法解。

[H Kanbun]

solution

做法：预处理出每一组括号匹配的右，剩余就是模拟。

[I Equal Sum Arrays]

solution

做法：容易发现答案就是 。

[J JOJO’s Happy Tree Friends]

solution

做法：树上游走，容易想到一次函数消元。设出 后一通转移，但由于跟子树每个点都有关，很难找到一个合适的序来消元。一个 key observation 是若一个点的子树里没有终点，则这个子树每个点的期望都是一样的，证明可以归纳。有了这个性质后，除了终点到根的那条链以外，其余点的消元都是容易的。此刻特殊地写出那条链的转移式，发现也就有序了，一次函数消元即可。时间复杂度 。

[K Monkey Joe]

solution

做法：拆完贡献后，就是很经典的树上二维数点状物。暴力就可持久化线段树，否则利用 dfs 时的进出可以树状数组解决。时间复杂度 。

[L Let’s Swap]

solution

做法：注意到相同操作使用两次直接复原，所以实际操作序列只有两种。而每两次操作发现就是位移，置换群的大小可知步长等价于 ，直接哈希，枚举步数检验即可。