“科大国创杯”2023 年安徽省青少年信息学科普日活动 简要题解

ElzaYork · 2023-04-09 16:42:57 · 个人记录

老年退役选手感受单调队列力量。

全家桶

小学组

T1 grade

直接累加即可。不需要按百分比算（也就是别 /100），那样可能会出现一些浮点数误差。

T2 order

暴力枚举 t 就可以了

T3 string

答案即为 cnt4+cnt5-cnt20。注意到对于一个数，我们只关心其个位和十位就可以判定了，然后就是 O(n)。

T4 hex

并查集维护连通性即可。注意如果不建虚点的话需要特判 n=1。

初中组

T1 score

和小学组一样，不做除法就可以了。

T2 count

排好序，枚举一个 i，然后枚举 j 的时候 k 尺取一下，时间复杂度 O(n^2)。

记得开 long long。

T3 walk

先找全局最短路。

如果询问边不在最短路上，直接输出全局最短路。

这样本质不同的询问个数就是 O(n) 了。

然后可以预处理 (1,1) \to (x,y) 和 (x,y) \to (n,n) 的最短路 单次询问简单讨论一下 O(n) 是容易的。

总时间复杂度 O(n^2+\min(n,q)n)，即 O(n^2)。

T4 stone

考虑贪心。如果在还没有合并的点中，最小值就在当前可以合并到的位置，那么我们一定会去合并它。

进一步的，以最小值在左边为例：设最小值在位置 x，我们可以直接将 x 和 x+1 看作一堆，因为合并到 x+1 时，一定会立刻合并 x。

更进一步的，合并完之后的这若干堆石子，其贡献可以类似地看作它们的平均值。

于是考虑贪心在两边维护好这样的栈，以左边为例，从左向右扫，如果当前栈顶的平均值大于其下方的元素，则将它们合并。

数据随机下，栈内元素是 O(\log n) 的。然后就预处理出每个栈的形态，询问时暴力地不停合并左右两个栈中较小的栈顶即可。

时间复杂度 O(n \log n)。

存在不依赖随机性质的做法。

鲜花

初中组 T2 放过 O(n^2\log n)，T3 边权随机并放过小常数 O(n^2+qn)，水老师实乃良心出题人！！！