『RETOI』ROUND 1 全题解
T1 损友
题目大意
给定一张 n×mn \times mn×m 地图，且每个格点都有一个权值 wi,jw_{i,j}wi,j ，再给你 kkk 个传送门，限制最多只能使用 ppp 次，求从 (1,1)(1,1)(1,1) 到 (n,m)(n,m)(n,m) 的最小权值和。
题目分析
SUBTASK 1
说句实话，针对于本部分分出题人并没有想到合理的做法，用来留给一些奇奇怪怪的搜索。
SUBTASK 2
注意到 k<1k \lt 1k<1，而题目又保证了 kkk 为整数，且 k≥0k \ge 0k≥0，所以 k=0k=0k=0，也就是说该地图没有传送门，所以只需要跑一个简单的 dp 就行了，代码就不贴了。
SUBTASK 3 & 4
两个部分分较为相似，同样是留给一些奇奇怪怪的搜索，也可以理解为是出题人为了防止你们太快猜出正解所设置的误导部分分。
SUBTASK 5（正解）
想象一下，在地图上我们找到两个关键格点 A,BA,BA,B（起点和终点不算），那么只传送一次（AAA 传到 BBB）的费用为 d(1,1),A+dB,(n,m)d_{(1,1),A} + d_{B,(n,m)}d(1,1),A +dB,(n,m) ，其中我们用 dX,Yd_{X,Y}dX,Y 表示从 XXX 到 YYY 不使用传送门的最小代价。
同理，传送两次（AAA 传到 CCC 和 DDD 传到 BBB）我们需要找到四个关键点，费用为 d(1,1),A+dC,D+dB,(n,m)d_{(1,1),A}+d_{C,D}+d_{B,(n,m)}d(1,1),A +dC,D +dB,(n,m) ，为了方便表述，我们将 A,B,C,DA,B,C,DA,B,C,D 的顺序进行了调换。
我们注意到题目中保证了对于任意的 i,j(1≤i≤n,1≤j≤m,)i,j(1 \le i\le n,1 \le j \le m,)i,j(1≤i≤n,1≤j≤m,)，满足 wi,j≥0w_{i,j} \ge 0wi,j ≥0，也就是说 dC,Dd_{C,D}dC,D 一定为非负整数。利用小奥作差法，我们可以得出 d(1,1),A+dB,(n,m)≤d(1,1),A+dC,D+dB,(n,m)d_{(1,1),A} + d_{B,(n,m)} \le d_{(1,1),A}+d_{C,D}+d_{B,(n,m)}d(1,1),A +dB,(n,m) ≤d(1,1),A +dC,D
+dB,(n,m) ，再形象点，我们可以得出：传送两次一定没有只传送一次更优。
以此类推，无论传送几次，一定没有只传送一次更优，所以我们可以将上面的结论推广成：传送多次一定没有只传送一次更优。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
根据上述结论，我们可以将最终答案分成两种形式，一种是使用传送门，一种是不使用传送门。前者的答案为有传送门的最靠近起点的的格点到起点的距离加有传送门的最靠近终点的格点到终点的距离，其中我们说的“最靠近”指距离最短，后者的答案为起点到终点的最短距离，最终答案为两者中的最小值。
形式化的，
ans=min{d(1,1),(n,n),min{d(1,1),I,isokI=1}+min{dJ,(n,m),isokJ=1}}。ans=min\{d_{(1,1),(n,n)},min\{d_{(1,1),I},isok_I=1\}+min\{d_{J,(n,m)},isok_J=1\}\}。 ans=min{d(1,1),(n,n) ,min{d(1,1),I ,isokI =1}+min{dJ,(n,m) ,isokJ =1}}。
其中我们用 isokXisok_XisokX 表示 XXX 格点上有没有传送门，isokX=1isok_X=1isokX =1 表示有，否则反之。
当然，如果 k<2k<2k<2 或是 p=0p=0p=0，最终答案 ansansans 就等于 d(1,1),(n,m)d_{(1,1),(n,m)}d(1,1),(n,m) 。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
小注：有些人可能会问当 III 和 JJJ 表示同一个格点时是不是还有减掉它们重复计算的 WIW_IWI ，答案是不用的，至于为什么留给读者自己研究。
CODE
T2 海岛
题目大意
pzh 被困在一个长为 nnn 的正方形海岛上，其所在坐标为 (x,y)(x,y)(x,y) ，给定救援队的速度 kkk、距离 mmm 以及海岛的下沉速度 sss、每个坐标的海拔 hhh，求救援队到达时 pzh 能否获救。
题目分析
救援队正在 mmm 米外以 kkk 米每秒的速度向海岛驶来，则救援队还要 $\frac{m}{k} $ 秒抵达海岛，又因为海岛正以 sss 米每秒的速度下沉，所以在救援队来到之前海岛下沉了 $\frac{ms}{k} $ 米，救援队到达时 (i,j)(i,j)(i,j) 的海拔变为 $h_{i,j}-\frac{ms}{k} $。
如题目所述，只有当 (x,y)(x,y)(x,y) 海拔小于 000 且其周围至少存在一个位置同样满足其坐标小于 000，我们才认为 (x,y)(x,y)(x,y) 被淹没。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
考虑一种极端情况
救援队到达之前海岛下沉 333 米，此时海岛各个坐标上的海拔为：
pzh 所在坐标 (2,2)(2,2)(2,2) 此时海拔为 −2-2−2 ，虽然海拔低于 000 ，但他周围四个坐标均为被淹没，所以 pzh 得救。
数据范围中 1≤n≤1001 \le n \le 1001≤n≤100 ，用 DFS 搜索一遍即可。
注意：DFS 记得要在四个边各搜一遍，否则可能搜不完整！！
CODE
T3 最佳出题人
题目大意
给定 nnn 个人，每个人都有 mmm 个指标，按照三条评定规则对他们进行排序，求出第 ppp 个人的编号。
题目分析
每个人都含有 mmm 个指标，所以考虑结构体排序，具体也没什么好讲的，直接看代码吧。
CODE
比较方差
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
另外，针对于此类涉及到方差的比较都可以通过一些操作（具体操作可以自行上网学习）改为平方和的比较，这样就可以避免一些精度问题。不过本题保证“每个人所有指标之和是 mmm 的倍数”，所以即使不优化也可以 AC 本题。
比较平方和
T4 高塔
题目大意
把 nnn 个元素插进有一个长度为 hhh 的序列中，其中序列的每个格点里最多只能容纳 kkk 个元素，且第 nnn 元素只能插进序列中下标小于或等于 fif_ifi 的元素。已知序列中下标为 iii 的每有一个元素，就需要 mim_imi 的代价，求将所有元素插入序列中的最小代价。
题目分析
我的老师教过我一个分辨贪心和背包 DP 的方法：一般对于既有代价又有价值的题目，如果所有元素的代价和价值均不相同，那么这题就是 DP，否则就是贪心。
我们注意到这道题每个元素都只会占用一个空间，所以只能是贪心。
对于贪心策略，最好的方法就是无脑猜，如果猜完可以证，那么它就一定是对的，如果猜完不可以证明且没时间了，那么它也一定是正确的（自信
让我们考虑一下这道题的贪心策略，对于两个元素 i,ji,ji,j，满足 fi≥fjf_i \ge f_jfi ≥fj ，且 mp=min{ml(fj≤l≤h)}m_p=min\{m_l(f_j \le l \le h)\}mp =min{ml (fj ≤l≤h)}，那么肯定优先将元素 iii 插入格点 ppp，如果还有空位再插 jjj，否则将 jjj 插入 ooo，其中 ooo 满足 mo=min{ml(fj≤l≤h)}m_o=min\{m_l(f_j \le l \le h)\}mo =min{ml (fj ≤l≤h)}。
那么为什么会这样呢？其实也很好证明，因为 fi≥fjf_i \ge f_jfi ≥fj ，所以元素 jjj 可以插入的范围是严格包含元素 iii 可以插入的范围的，换句话说，元素 iii 可以插入的格点元素 jjj 一定能，反之则不一定能。那么感性理解，既然这样如果有空出来一个空位肯定优先选择插入 iii，因为 jjj 可以插入的范围更大。
CODE
