ultmaster edited 6 年，3 月前
难度评级可能不是线性的。仅供参考。
这是一套总体难度不大，难点主要在实现上的题目。套路题较多，对中等水平以上的选手来说可能不够有趣。不管怎么样，希望大家能或多或少有所收获吧。
如果把它当多校看的话，怕是只有签到题？
思维难度: 1/3; 实现难度: 1/4. 前置知识: 英语.
读完题模拟就可以。（如果你知道卷积是什么，甚至不用读题）
思维难度: 3/3; 实现难度: 2/4. 前置知识: 英语.
这道题目解法非常丰富。最简单的也是最好实现的一种做法是：先跳到 $(1,y)$，然后跳到 $(1,1)$，然后按行蛇形的扫下来（奇数行从左往右，偶数行从右往左），用一个 vis 数组记录已经访问过的格子。
思维难度: 2/3; 实现难度: 2/4. 前置知识: 扫描线.
由于本场题目是基于之前某一场，所以夹带了之前的某些特色。对于比赛来说，这题真的是过分套路了。
求最大值是扫描线基本问题。平均值也可以用扫描线求。但有一种更好的做法，是把所有的区间长度加起来，除以 $m$。
由于需要前置知识，放在 C 的位置。
思维难度: 3/3; 实现难度: 3/4. 前置知识: 树, 树上差分 OR 树链剖分.
交换次数无限的话，等于可以随意打乱。我们考虑把边按某种顺序排序，然后直接贪心的分配。考虑每条边被订单需要的次数，容易证明被需要次数越多的边应该分配更小的权，需要次数更少的边应该分配更大的权。
接下来就是求每条边被路径覆盖的次数了。这是路径加、单边查，是一个经典问题，而且只有一次查询，用树链剖分或者树上差分都能做。不会的可以自行 Google 或百度。这里不再赘述了。
思维难度: 2/3; 实现难度: 4/4. 前置知识: 数学, DP, 迭代加深搜索.
考虑迭代加深搜索，搜到底了之后验证答案可以用背包 + 经典的 bitset 优化。事实上这么做就能跑出 100 多的数据范围。稍微加点剪枝，可以在能接受的时间内跑出来，交个表上去就能 AC。
Comment: 可以稍微观察下跑出来的结果的性质。其实对每一个答案长度，我们只需要保留它最后一个解：因为如果更多的质数都能凑出来，那么更少的绝对没有问题。然后可以发现这个答案每次都会保留前缀增加一个数：以 1, 2, 5, 11 开头，后面每一项都是前面所有项的和。当然这个只是一个观察出来的性质，在 $n$ 大的时候很有可能是不对的。数学上是否能做出该问题的一个渐进界还是一个问题。总之这问题是 open 的，有兴趣的同学可以写篇论文研究一下。