2020 ICPC 上海站 ¶

排名	当场过题数	至今过题数	总题数
78/?	5	?	13

A¶

upsolved by

题意¶

题解¶

B¶

solved by 2sozx JJLeo

题意¶

签到

题解¶

签到

C¶

upsolved by

题意¶

题解¶

D¶

upsolved by

题意¶

题解¶

E¶

upsolved by

题意¶

题解¶

F¶

upsolved by

题意¶

题解¶

G¶

solved by JJLeo

题意¶

签到

题解¶

签到

H¶

upsolved by 2sozx

题意¶

一个圆周被平分了 \(n\) 份，有 \(k\) 个人和 \(k\) 份手抓饭各分别在 \(n\) 个点上，可以移动圆周使得每份手抓饭进行同向移动，每个人吃且仅吃一份手抓饭，问最少移动多少距离可以让每个人都吃到手抓饭

题解¶

一个定理，每个人按顺序选择手抓饭一定比选择交叉更优。

因此可以枚举每个人选择的手抓饭，然后可以在 \(O(nlog)\) 的时间内计算出这种情况下的最短距离。

I¶

solved by 爬

题意¶

爬

题解¶

爬

J¶

upsolved by

题意¶

题解¶

K¶

upsolved by

题意¶

题解¶

L¶

upsolved by 2sozx

题意¶

给定一个 \(n \times m\) 的平面，一个点在 \((x, y)\) 只能移动到 \((a, b)\) 其中 \(gcd(a - x, b - y) = 1\) 问从 \((0, 0)\) 到 \((n, m)\) 最短的欧几里得距离是多少。

题解¶

如果没有限制显然是对角线最短。有限制我们考虑对角线上下的两个点，暴力枚举取最小值即可。

2020 ICPC 上海站¶

A¶

题意¶

题解¶

B¶

题意¶

题解¶

C¶

题意¶

题解¶

D¶

题意¶

题解¶

E¶

题意¶

题解¶

F¶

题意¶

题解¶

G¶

题意¶

题解¶

H¶

题意¶

题解¶

I¶

题意¶

题解¶

J¶

题意¶

题解¶

K¶

题意¶

题解¶

L¶

题意¶

题解¶

M¶

题意¶

题解¶

记录¶

总结¶

2020 ICPC 上海站 ¶