link: https://qoj.ac/contest/2814 ↗

周六和队友VP了这一场，周末还要早起好难受啊

最后是 8/12, 然而结束没一会我和jeff就都把自己负责那题调出来了痛失 10/12

A. Automatized Mineral Classification#

交互题，队友负责的，我也想了一下，没有什么特别的想法，Yehor提了一嘴可以随机化，突然发现很有道理，这样一个一个数pop来确定当前位的时候期望只用 pop 掉 len/2 个，然后加入回来的时候也只用加 len/2个，这样相当于只用len次就能确定两个新的位置的值

丢给jeff写了

code ↗

C. Connecting Railway Stations#

我负责的这题

第一眼抓住重点，考虑每一条边对答案的最大贡献，对于每个店，能往上传尽量往上传节点

然后尝试一个dfs解决这个问题

结果发现不太行，并不能只考虑子树，得跑两次dfs，考虑从下到上和从上到下的，第一遍尽量往上传，第二遍尽量往下传，贪心求一下即可

然而最后考虑了根是叶子结点的情况，但是忘记把参数传进去，一直没调出来，崩了

code ↗

D. DNA#

jeff 负责这题，感觉是没睡醒，问了一下我，我直接秒了

不难发现，如果一个串 $S$ 是他们的 LCS，因为是 01串，那么0或者1其中一个的个数一定是超过 $len/2$ 的，所以只需一开始对于每个串统计一下 0和1的数量，随便贪心取一下即可

code ↗

F. Foxes#

数据结构题，jeff赛后大力 4.9kb调出来了

G. Game of Darts#

签到题

H. Hiking#

另外两个队友写的，还没看，之后补一下

I. Identical Fences#

同上

J. Joyful Guided Tour#

这题还有点意思

首先根据鸽巢原理，7个边，最坏情况是对于每种颜色，出现次数分别是$2,2,2,1$, 那么对于当前的点，只需要选出现次数最少的那个颜色即可，然后在看那个点需不需要调整颜色，用队列简单实现即可

为什么是对的呢，我们可以考虑设定一个$ret[u]$ 表示和 $u$ 这个点颜色一样的相邻的点的个数，那么不难发现，按照上面的策略，每次会最多让一个点的 $ret + 1$， 让至少两个点的 $ret - 1$, 因为$\sum ret[u]$ 最多为$7n$, 那么每次操作都能让这个 sum 减少，均摊下来时间复杂度就肯定是对的

code ↗

K. Key Properties#

首先看这个数据范围满足 $n>=42$，感觉有点刻意

考虑怎么构造，题目已经给了 10个点的构造方法

然后感觉奇数的点貌似显然没发构造，于是我直接考虑12个点的怎么构造

尝试类似的构造，搞了个一边3个点的二分图连边，然后外面再围一圈，随便连一连就能构造出来

构造出来后，这样我们就得到了 10个点的构造和12个点的构造

因为奇数显然没发构造，所以不妨先把 $n/2$, 就是$n/2>=21$, 然后我们有$5,6$ 两个图可以用

想到noip2017小凯的疑惑，最小的不能构造的是$5*6-5-6=19$ 所以显然是可以构造的，直接大力枚举每个图出现的次数即可

然后因为没看懂题，以为可以不连通一直WA，之后尝试改成联通就过了

具体来说就是把每个图的 $1->2$ 这条边不连，然后排成一排，隔一个连成环即可

code ↗

L. Letters on T-shirts#

签到题，队友写的