“科大国创杯”2023 年安徽省青少年信息学科普日活动 简要题解
发布时间 2023-04-09 16:53:03作者: 铃兰星夜
初中组没有实现，如果有问题欢迎爆 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)$，水老师实乃良心出题人！！！