2019-2020 ICPC SWERC 2019-20
in GYM训练 with 0 comment

2019-2020 ICPC SWERC 2019-20

in GYM训练 with 0 comment

A、(zyj 1:41 +0)

给一张图,点和点之间的距离为欧几里得距离,要从起点到终点,有多种交通工具,每种的单位距离花费不同,求路长在B之内的最小花费。
建边求到每个位置时路径长为j的最小花费,用$d_{i,j}$进行转移。

B、(zyj 0:04 +0)

给定n个字符串,求是否有哪个字符串出现次数严格超过一半
map即可

C、(wrf 0:13 +1)

求给定所有数中没出现过的最小的自然数
记录一下所有大小小于等于$1e6$的数,然后查找即可

D、(wrf 4:30 +5)

大模拟

E、

待补

F、(wrf 0:47 +4)

求凸包面积

G、(zyj 2:45 +3)

给一个序列,然后一些对可以在相邻的时候互换,求最小字典序
可以确定一些对的相对位置不会变化,将每个值和在它前面与其不能互换的每种值的最后一个相连,根据拓扑序即可得到答案

H、(lmj 赛后)

给一个伪随机的算法,求前n次操作有多少个为偶数。
分块打表,通过打表可以发现该随机算法获得的数据在后面出现了循环,打两种表,一个是前面没有循环的部分,一个是循环的部分,每$1e7$位打一个数据。

I、(zyj 0:06 +0)

签到

J、(wrf 2:18 +0)

给一个小根堆的中序遍历,求堆有多少种可能性
区间最小值分组+卡特兰数

K、(zyj 0:26 +0)

bfs

L、(lmj 赛后)

状压dp+sg函数

Responses