第45届ICPC亚洲区域赛昆明赛区个人题解与心得

2021-04-04 22:33 作者:俊杰_Charles 0人读过 | 我要投稿

比赛地址：https://ac.nowcoder.com/acm/contest/12548

官方题解：https://www.zhihu.com/question/435057733

难度：ICPC区域赛

赛后合影左起：rockdu, Macaron_lin, cjj490168650

本文中的题目顺序参照牛客网上的题目顺序。由于B站专栏的代码块功能有 bug，如果代码块不能正常显示，请通过代码链接查看代码。

H. Hard Calculation

题意：输出 $2020%2Bx$ 。

题解：签到题，很幸运我们队一开始就找到了这道题。

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47376389

I. Mr. Main and Windmills

题意：在一个二维平面上，你从点 $s$ 沿线段走到点 $t$ 。在 $st$ 的一侧有 $n$ 个点，对于其中两个点 $u%2Cv$ 以及 $st%20$ 上一点 $p$ ，当你经过 $p$ 之前观察 $u%2Cv$ 时 $u$ 在 $v$ 的左侧，而经过 $p$ 之后观察 $u%2Cv$ 时 $u$ 在 $v$ 的右侧，则称 $u%2Cv$ 在 $p$ 处发生了一次“交换”。现有 $m$ 次询问，每次询问某个点与其他点第 $k$ 次发生“交换”的位置。保证任意三点不共线。

题解：对于每个点来说，它和某点发生“交换”的地方位于这两点所在直线与线段 $st$ 的交点处。因此发生第 $k$ 次“交换”的位置，则是这个点与其他所有点形成的直线与线段 $st$ 的交点离 $s$ 第 $k$ 近的点。询问前预处理出交点位置并排序，时间复杂度 $O(n%5E2%5Clog%20n%2Bm)$ 。

这题很多人说是数据“卡精度”了，其实不然，就赛后出题人的说明来看这题的数据其实挺水的。如果被“卡精度”，很可能是在代码中引入了不必要的精度问题。具体可见这篇帖子：https://www.zhihu.com/question/435057733/answer/1816005081。我作为队里的几何选手，赛前做过一些涉及求交点的几何题，如 WF2017 的 Airport Construction，踩了一些坑，所以赛场上也有意识的避免了类似问题。所以说多做题还是很有必要的。

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47376405

J. Parallel Sort

题意：给出一个 $1$ 到 $n$ 的排列，每轮你可以选择若干对互不相同的数进行交换，要求将数列排好序，且操作轮数最少，输出方案。

题解：后六题里最需要思维的题目了。首先可以想到的是，不同的置换环可以分开考虑。比如考虑如下的置换环（第 $i$ 个数为 $p_i$ 的话， $i$ 向 $p_i$ 连边）。

可以发现对于一次交换操作，交换的是两个点的出边。比如交换第 3 和第 6 个数，置换环发生如下变化。

最开始的时候有一个朴素的想法，就是每次交换置换环中相邻两点，如在第一张图中交换 (1,2) (3,4) (5,6)，得到如下置换环。

可以发现，每次操作会有一半的点归位，剩下一半的点形成一个新的置换环。如此下去，每次置换环的大小减半，操作轮数为 $O(%5Clog%20n)$ 。

感觉非常的有道理啊，然后写好代码交上去，喜提 WA。在检查代码确认无代码错误后，我分析认为这种策略很可能不是最优的，因此开始寻找更好的策略。一通分析后，我意识到可能有操作轮数至多为 2 的策略，关键在于将原置换环构造形成若干个二元环。随后我找到了正确的方法，就是从两边往中间交换，如在第一张图中交换 (1,7) (2,6) (3,5)。

按照这种策略，任意大小的置换环都可以经过一轮操作形成若干大小至多为 2 的环，然后再进行一轮操作便可将所有数归位，操作轮数至多为 2。

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47376420

K. Riichi!!

题意：给定一麻将牌型，如果能直接和牌输出“自摸”，否则输出打哪张牌能听牌以及听哪些牌。注意本题中每种牌的张数没有上限。

题解：写一个判和牌的函数。如果给出的牌型能直接和牌则输出“自摸”，否则枚举打出的牌，再枚举进张的牌，判断能否和牌。

本场比赛唯一把我坑到的一题。本来作为麻将玩家自信满满地去开这道题，结果写了个爆搜 T 飞了。后尝试了一系列剪枝，未果。最后在队友的帮助下，将判断和牌的策略从爆搜改为了贪心，过了此题。赛后询问了出题人，出题人表示确实故意卡了爆搜的时间。个人不是很喜欢这题，既然有这么复杂的背景我觉得就没必要太卡时间了。

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47376463

L. Simone and graph coloring

题意：给定一个数列 $a_1%2Ca_2%2C%5Cdots%2Ca_n$ ，每对逆序对 $(a_i%2Ca_j)$ 在图中对应一条 $(i%2Cj)%20$ 的无向边。然后在图中染色，要求相邻两点不能染成同一颜色，求最少颜色数并输出方案。

题解：最长下降子序列，队友写的。

M. Stone Games

这题是队友写的，我没有读题，应该是个可持久化线段树的题，据说还是 19 年徐州原题。虽然队友貌似没有原题的印象，不过还是成功分析并通过了此题。

其实我们队更好发挥的话还有可能过 G 题和 C 题，然而由于被 K 题卡的时间太长，队友写 G 的时间不太够了，最终 6 题收尾。还好保住了金牌，否则我就要背锅了555。

比赛整体体验还行，个人觉得题目整体难度偏低，题目质量中等，J 题让我眼前一亮，但 K 把我卡得挺不爽。主办方提供的鲜花饼挺好吃，但承办比赛水平不足，给参赛者传达的信息经常前后不一致，希望主办方能够所有反思。

这是我拿到的第二块ICPC金牌，我觉得这块金牌的意义比第一块更大。如果说第一块金牌是抱队友大腿拿到的话，那这一块金牌可以说是我们实实在在努力的结果。

这里感谢我的两个队友：Macaron_lin 和 rockdu（下称小马和小杜）。小马是我的大学同学，也是被我拉进算法竞赛坑的人。小马没有任何中学OI基础，但依旧凭借自己的努力通过了校队选拔。小马的竞赛之路并不顺畅，在其他队伍纷纷获得ICPC或CCPC金牌后，小马最好成绩仍是铜牌。而昆明这场比赛，算是小马的“背水一战”了。这块金牌，圆了小马的梦，也完成了我俩共同的目标。而小杜是我的中学同学，是一名OI爷，在赤兔马缺少一名成员时及时补位，他扎实的基础可以说是拿到这块金牌的有力保障。同时还要感谢前赤兔马成员zh，暑期集训时优异的表现让赤兔马拿到了打EC-Final的机会。

这个赛季结束后，赤兔马这支队伍可能就解散了。我之后的算法竞赛路途会是怎样，我不清楚，但至少现在，我已经完成了一个阶段性的目标。之后的路途，我会继续努力的。

大兔子的算法竞赛交流群：1043272289

标签：