2018.8 月赛题解

ultmaster edited 6 月,1 周前

难度评级可能不是线性的。仅供参考。

这是一套总体难度不大,难点主要在实现上的题目。套路题较多,对中等水平以上的选手来说可能不够有趣。不管怎么样,希望大家能或多或少有所收获吧。

如果把它当多校看的话,怕是只有签到题?

Problem A

思维难度: 1/3; 实现难度: 1/4. 前置知识: 英语.

读完题模拟就可以。(如果你知道卷积是什么,甚至不用读题)

Problem B

思维难度: 3/3; 实现难度: 2/4. 前置知识: 英语.

这道题目解法非常丰富。最简单的也是最好实现的一种做法是:先跳到 ,然后跳到 ,然后按行蛇形的扫下来(奇数行从左往右,偶数行从右往左),用一个 vis 数组记录已经访问过的格子。

Problem C

思维难度: 2/3; 实现难度: 2/4. 前置知识: 扫描线.

由于本场题目是基于之前某一场,所以夹带了之前的某些特色。对于比赛来说,这题真的是过分套路了。

求最大值是扫描线基本问题。平均值也可以用扫描线求。但有一种更好的做法,是把所有的区间长度加起来,除以

由于需要前置知识,放在 C 的位置。

Problem D

思维难度: 3/3; 实现难度: 3/4. 前置知识: 树, 树上差分 OR 树链剖分.

交换次数无限的话,等于可以随意打乱。我们考虑把边按某种顺序排序,然后直接贪心的分配。考虑每条边被订单需要的次数,容易证明被需要次数越多的边应该分配更小的权,需要次数更少的边应该分配更大的权。

接下来就是求每条边被路径覆盖的次数了。这是路径加、单边查,是一个经典问题,而且只有一次查询,用树链剖分或者树上差分都能做。不会的可以自行 Google 或百度。这里不再赘述了。

Problem E

思维难度: 2/3; 实现难度: 4/4. 前置知识: 数学, DP, 迭代加深搜索.

考虑迭代加深搜索,搜到底了之后验证答案可以用背包 + 经典的 bitset 优化。事实上这么做就能跑出 100 多的数据范围。稍微加点剪枝,可以在能接受的时间内跑出来,交个表上去就能 AC。

Comment: 可以稍微观察下跑出来的结果的性质。其实对每一个答案长度,我们只需要保留它最后一个解:因为如果更多的质数都能凑出来,那么更少的绝对没有问题。然后可以发现这个答案每次都会保留前缀增加一个数:以 1, 2, 5, 11 开头,后面每一项都是前面所有项的和。当然这个只是一个观察出来的性质,在 大的时候很有可能是不对的。数学上是否能做出该问题的一个渐进界还是一个问题。总之这问题是 open 的,有兴趣的同学可以写篇论文研究一下。

Comments

你正在回复博客
存在问题!