老年退役选手感受单调队列力量。
初中组没有实现,如果有问题欢迎爆 d 我。
小学组
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$ 出发:
先假装每个点 $i$ 的负贡献是 $|x-i| \times a_i$。
然后每次向左/右选的贡献就是一个前缀/后缀和的形式。于是可以直接贪心,复杂度 $O(n(r-l))$。
因为数据随机,所以相邻的轮的贡献可能很快就会到达相同的状态 $(l,r)$,感觉上直接加个记忆化就能过。
鲜花
初中组 T2 放过 $O(n^2\log n)$,T3 边权随机并放过小常数 $O(n^2+qn)$,水老师实乃良心出题人!!!