“科大国创杯”2023 年安徽省青少年信息学科普日活动 简要题解
小学组
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)→(x, y)
和 (x, y)→(n, n)
的最短路 单次询问简单讨论一下 O(n)
是容易的。
总时间复杂度 O(n^2 + min(n, q)n)
,即 O(n^2)
。
T4 stone
首先你考虑不依赖随机性质怎么做。
对于每一轮从 x
出发:
先假装每个点 i
的负贡献是 | x ? i | ×a i
然后每次向左 / 右选的贡献就是一个前缀 / 后缀和的形式。于是可以直接贪心,复杂度 O(n(r ? l))。(假的假的,我若治了 / ll)
因为数据随机,所以相邻的轮的贡献可能很快就会到达相同的状态 (l, r)
,感觉上直接加个记忆化就能过。
鲜花
初中组 T2 放过 O(n 2 logn)!!!
T3 边权随机并放过小常数 O(n 2 + qn)
水老师实乃良心出题人!!!
点个赞再走吧!!!
标签:题解,复杂度,T2,T3,2023,创杯 From: https://www.cnblogs.com/niuzeyu1/p/17612473.html