ICPC WF 2020 部分题解

icpc-2020-editorial.md

WF 2020

A. Cardiology

理解题意后，不难理解枚举 $p$ 之后，一次洗牌实际上对应的是行号到行号的映射，其中一定存在不动点。问题可以拆分为：

• 判断不动点是否唯一
  • 不动点一定是连续的，解方程求出一个之后判断一下后一个是否还是不动点即可
• 求收敛到不动点的最大轮数
  • 最晚收敛到不动点的一定是第 1 行或第 n 行，证明略。

C. Domes

裸半平面交，可能卡 eps。

D. Gene Folding

Manacher 求出回文半径后左右分别贪心，能折就折。

E. Landscape Generator

打标记签到题

F. Ley Lines

枚举一个必在边界上的点 A，剩余点 B 根据其与枚举的点的距离分两种情况：

• 距离不大于 L， B 在区域里面的角度范围是一个半平面

• 距离大于 L，B 在区域里面的角度范围是两个区间，区间大小为切线的转角。

G. Opportunity Cost

考虑二维情况，cost 实际上是 $\max{ 0, x_i -x , y_i - y, x_i+y_i- x - y }$，三维则是 8 个项。所以只需求出八个方向最大的点，然后只用这些点 check 某个点的 cost 即可。

J. 'S No Problem

Tree dp，状态为以 x 为根，当前内部已经产生 0/1/2 条链，并且往上还有 0/1 条插头的最小代价。

M. Trailing Digits

枚举 k，问题转化为求一个关于前若干非 d 位的同余方程。

O. Which Planet is This?!

问题可以转化为判断两个字符串是否旋转同构。