====== 简况 ======
[[https://ac.nowcoder.com/acm/contest/5668|比赛链接]]

AC 8题，Rank 49th 

====== 总结与反思 ======
===== cmx  =====
写东西胆子还是大一些，这场的H笛卡尔树几乎是个裸题，可惜信心不足，要是写出来了就幸福了。另外D其实是想到一个更简单搞法的，不知为啥脑抽了。

===== lpy  =====

写完后最好本地多测测，避免过多罚时

构造题还需要加强练习
===== xsy  =====

写题时仔细一点，清醒一点，自信一点...不要慌张。

罚时爆炸。
====== 题解  ======

===== A. Clam and Fish =====

签到题，最开始想法基本是对的但是看着一堆人WA没敢写，浪费了不少时间。

显然有鱼拿鱼，否则能做饵料就做饵料，空地有饵料就直接捞鱼，否则啥也不干。

最后答案需要加上多的饵料/2，相当于剩下一半选择做饵料的位置改为捞鱼。

by MountVoom

===== B. Classical String Problem =====

签到题，把字符串看成首尾相接，每次操作相当于改变了一下开头的位置。

by MountVoom

===== C. Operation Love =====

签到题，长边为9算成10也太傻逼了。

找到相邻两边长度为8和9的顶点，然后用叉积判断一下方向即可。

需要注意的是给定的坐标有一定的误差，但是因为长度都是整数，所以可以+0.5以后直接截断来进行判断。

by MountVoom
===== D.Points Construction Problem  =====
这个题赛场上是lpy通过基本图形组合的方式AC的。其实赛场上有想过另一种方法，可惜脑抽了以为有情况没有覆盖。之后才发现是正确解法。

首先问题等效于构造n个小方块拼接成一个周长为m的图边形。显然m为奇数，是不行的。我们如果用m周长，构造一个尽可能大的矩形($m/2/2,m/2-m/2/2$)，这样，最少我们可以沿着对角线填，个数是长边的长度。最多可以填出一个面积。可以发现，这样的矩形所能达到的方块个数的范围，是比其他矩形只多不少的。而且很容易证明，在这个范围之外，是不可能的。

当然有个问题，$[m/2-m/2/2,m/2/2*(m/2-m/2/2)]$之间所有方块数目都能取到吗？其实是可以的，往对角线两侧紧密填充即可，注意不要让图形出现凹陷，这样周长会大于m。

by cmx

赛场上考虑其主要有三个基本图形：矩形，线，离散点

假设矩形边长为$a,b > 1$,线长为$c > 1$,离散点数为$d$

则有方程$2(a+b)+2c+2+4d=m,ab+c+d=n$

枚举$c+d$并预处理$ab$分解即可暴力求解

但WA了几发后发现矩形可能有一条边有缺失

<code>
XXX **X
XXX XXX
XXX XXX (X表示黑点，*表示白点)
</code>

这两种在周长上贡献一样，耗费点数不同

所以方程变为$2(a+b)+2c+2+4d=m,ab-e+c+d=n,0 \leq e < b$

由于网格很大，知道解后即可构造

by Hardict

===== E.Two Matchings =====

cmx赛场上AC的

一开始发现其实题目就是一堆二元环交换问题，发现具体解和原序列顺序无关

排升序后，$(1,2)(3,4)...$这样即为最小解

但题目要求两个完全不同(每一位都不想等)置换，使和最小

后面发现$4|n$使，$(1,4)(2,3)$这种下去即可，$4\nmid n$使可能有六个一组的情况，而且可能不只一个

而$(1,4)(2,3)$和$$(1,2)(3,4)$相比可以通过简单加减转换

运用$dp$即可

$dp[i] = dp[i - 4] + (a[i] - a[i - 3]) * 2$

$dp[i] = min(dp[i], dp[i - 6] + (a[i] - a[i - 5]) * 2)$

by Hardict

===== F. Fraction Construction Problem =====

首先$d=f$即$gcd(a,b)>1$解是显然的

$(d,f)=x,\frac{c}{d}-\frac{e}{f}=\frac{c\frac{f}{x}-e\frac{d}{x}}{\frac{df}{x}}$

不妨$(d,f)=1$.转换为$\frac{cf-ed}{xdf};xd,xf \leq b$

我们即可知道$b$的两个不同素因子p,q，然后$d=p,f=q$

利用$exgcd$求得$cf-ed=1$,$c$取最小正数解$c_{0}$

故整体解为$c=ac_{0},e=ae_{0},d=px,f=qx,x=\frac{b}{pq}$

而若$b$为$1$或素因子的幂是无解的

by Hardict
===== G. Operating on a Graph =====

开始时把自己给绕晕了导致卡题很久....

一旦一个点把相邻的点染成同色以后，它们就永远会是同一种颜色，可以用并查集来维护每个点的颜色。

每种颜色维护一个链表记录还有哪些这种颜色的点没有把相邻的点染色，即这个颜色区域的边界。

染色时假设扩展的区域为$x$，首先把$x$的边界进行扩展，假设把颜色$y$改为$x$，那么把$y$的链表接在$x$的链表后。

by MountVoom
====== 补题 ======
===== H.Sort the Strings Revision  =====
笛卡尔树题。我们知道如果第一个字符替换出一个更小的字符，那么这个替换之后的操作得到的字符串都会在前面；更大则在后面，相等则等于没有任何影响，对第二个、第三个字符类似递归讨论。可以看出左右的递归形成了一棵二叉树。直接对p数组构造笛卡尔树，就是这个二叉树了。因为笛卡尔树可以选择相同的最小值取左为根。所以对于相等替换，我们全部对对应p修改为正无穷1E9即可。

建树完毕之后dfs，根据大于还是小于分类讨论先左边还是先右边。得到的dfs序列就是我们最后的字符串字典序。

全递归版本也不到一秒，不用卡常。