====== 2020牛客暑期多校第三场 ====== ====== 比赛地址 ====== [[https://ac.nowcoder.com/acm/contest/5668|牛客OJ]] Pro: 8/8/12 Rank: 71/1175 ====== [A] Clam and Fish ====== ===== 题意 ===== 有一片池塘,有四个状态,有/无蛤蜊,有/无鱼.有蛤蜊的时候可以做一个诱饵,有鱼的时候可以直接钓鱼.其他时间可以消耗一个诱饵钓一条鱼.求最多能钓几条鱼. ===== 题解 ===== 贪心.在有鱼的时候尽量钓,其他时间做诱饵. 如果最后会剩下诱饵就在做后面一半诱饵的时候钓鱼. ====== [B] Classical String Problem ====== ===== 题意 ===== 给出一个字符串,有两种操作,一种是把最前面的k个字符挪到最后面,另一种是把最后面的k个字符挪到最前面.还有一些询问操作,每次问某个位置的字符是什么. ===== 题解 ===== 首尾相接拼成一个环,然后更新首字符所在的位置就行了. ~~一开始失了智写了个Splay维护区间,还T了一发QAQ~~ ====== [C] Operation Love ====== ## 题意给出一个右手的形状,左手与右手是镜像对称的.现在给出一个图形,判断是左手还是右手. ===== 题解 ===== ~~机器学习~~ 可以找一些特殊的向量来判断叉积,卡精度. ====== [D] Points Construction Problem ====== ===== 题意 ===== 给出一个无限大的网格平面,一开始每一个格子都是白色的.现在要求将$n$个格子染成黑色,使得相邻的两个格子为黑白两色的格子对的数目恰好为$m$.求染色方案. ===== 题解 ===== $m$为奇数一定无解,且$m$最大为$4n$.然后当这些黑色格子构成一个正方形时,黑白格子对数目最少. 根据以上信息简单构造下就行了. ====== [E] Two Matchings ====== ===== 题意 ===== 给一个长度为$n$的序列,定义重排方案$p$为,$p_{i}!=i,p_{p_{i}}=i$.且p为1到n的一个排列. 现在要求找出两个完全不同的重排方案$p,q$(也就是两个排列对应位置均不相同),使得原序列在分别经过这两个重排后的代价之和最小.求这个最小代价. 代价的定义是$\sum_{i=1}^{n}\frac{a_{i}-a_{i}'}{2}$ ===== 题解 ===== 不难发现,当$n=4,6$时,答案就是最大值减去最小值的两倍.当$n$比较大时,就需要把这个序列切为一些小段,每一个小段的代价也是最大值减去最小值的两倍. 所以有如下dp式子:$f[i]=Min(f[i],f[j]+2(a[i]-a[j+1])$.其中的a是从大到小排好序的.这个式子和单调队列优化dp的式子非常像,不过这里只需要记录下$f[i]-2a[i+1]$的最大值.之后直接dp就行了. ====== [F] Fraction Construction Problem ====== ===== 题意 ===== 给出$a,b$,求$c,d,e,f$,使得$\frac{c}{d}-\frac{e}{f}=\frac{a}{b}$. 且要满足$d,f