=====比赛信息===== * **日期：2020.7.20** * **比赛地址：** [[https://ac.nowcoder.com/acm/contest/5669#rank|传送门]] * **做题情况：lxh(A)，tyx(F)，gyp(BH)** =====题解===== ====A - Ancient Distance==== ===solved by lxh=== ===题意=== 我们定义远古距离为其到其最近的有标记的祖先的距离（自己有标记则为0）。现在依次给 $1~n$ 个点，问在树上有这么多标记了的点时，最大的远古距离最小是多少。 ===数据范围=== 点数 $n \le 2e5 $ ===题解=== 正面想这个问题不太好解决，我们不妨反过来想，由于答案的单调性让问题变为当最大远古距离为 $k$ 时，最少需要多少个点，这样我们就可以通过在最深的点处向上爬 $k$ 层再将整个子树去掉的方法贪心（需要借助线段树和dfn序维护），最后从 $1~n$ 扫一遍处理出每个的答案。 ====B - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====C - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====D - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====F - Finding the Order==== ===solved by tyx=== ===题意=== 现在有两条直线$AB$和$CD$平行，但是我们不知道$C$和$D$谁先谁后，给出$|AC|,|AD|,|BC|,|BD|$，判断是$AB//CD$还是$AB//DC$ ===数据范围=== $1 \le |AC|,|AD|,|BC|,|BD| \le 1000$ ===题解=== 直接找最大距离，如果最大距离是$|AD|$或者$|BC|$，答案就是$AB//CD$，否则是$AD//DC$ ====G - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====H - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====I - Investigating Legions==== ===solved by -, upsolved by tyx=== ===题意=== 一个国家有$n$支军队和若干个军团，现在给出两两之间是否属于同一个军团，构造一个每支军队属于哪个军团的解，要求字典序最小，注意给出的是否属于同一个军团有$\frac{1}{S}$的概率是错误的 ===数据范围=== $30 \le n \le 300$，$20 \le S \le 100$ ===题解=== 其实并没有完全的正解，我每次把一个没有归属的军队拉出来然后看看数据中和它在同一个军团的有哪些，同时记一个数量，然后再记录有哪些其它的军队和这些军队再同一个军团中，如果大于一个阈值就丢到同一个军团里。其实就是乱搞 ====J - ==== ===solved by === ===题意=== ===数据范围=== ===思路=== =====Replay===== 第一小时：三人发现F很简单，于是tyx直接过了F，gyp开始想B并快速通过，之后开始想H，tyx和lxh开始想E，gyp的H不通过 第二小时：gyp发现了H题的问题通过了H，lxh开始写E，gyp开始想D 第三小时：lxh的E没通过，gyp开始写E但是也没有通过，tyx看了CDJ以后开始想J 第四小时：gyp写完D以后一直WA，找到了几个错误以后还是不对，tyx想不出J和lxh一起想A 第五小时：tyx和lxh一起想出了A并且通过，gyp一直在改D但是始终没有通过 =====总结===== * 在提交之前一定要注意题目的条件，否则就会罚时++