目录
2020牛客暑期多校第三场
比赛地址
[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<html><b$
题解
变形,有$\frac{cf-ed}{df}=\frac{a}{b}$.将b拆分成互质的两个数,作为$d$和$f$.此时由裴蜀定理可知,上面这个不定方程是有解的,解出$c,e$即可.
当$b$只含有一个质因子或者在$b<1$时是无解的.还有一些其他特殊的情况也要特判掉.
[G] Operating on a Graph
题意
给出一个图,有$n$个集合.一开始,第$i$个集合中只有点$i$.接下来有一系列操作,每次会钦定一个集合$x$,把与$x$相邻的所有集合全部并到$x$集合中.求在这些操作后,每个点分别属于哪些集合.
集合相邻的定义是,存在一条边,连接了两个集合中的一对点.
题解
首先,把集合的合并想象成染色操作,不难发现,每条边至多会传递染色操作一次.于是,对于每一个集合,维护这个集合有哪些边,是连接了这个集合的点与集合外的点.每一次合并的时候,就通过这些边找到相邻的集合来合并,通过并查集维护集合的关系.合并之后,更新一下新集合的边集.
一开始,每一条边一定会属于两个边集,且边集的总大小是不变的,故使用按秩合并的话,时间复杂度就可以降为$O(mlogm)$.边集的储存通过vector实现,内存方面就没问题了.
[L] Problem L is the Only Lovely Problem
题意&题解
签到题
总结
整场比赛基本上没有闲着的时候.
签完到之后在想F和G.G题一开始的写法有问题,导致莫名MLE,中间还针对vector换了一个释放内存的写法2333.思路是对的,但是码力没太跟上,浪费了很多时间也多吃了好几次罚时.F题的推导速度也有些慢,直接导致了在最后一小时才发现D题很可做(当然这跟榜有些歪也有关系).五个小时连WA带调就这么过去了.
之后的工作重点还是在尽可能减少罚时上.
