CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 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个字符挪到最前面.还有一些询问操作,每次问某个位置的字符是什么.

===== 题解 =====

首尾相接拼成一个环,然后更新首字符所在的位置就行了.

<del>一开始失了智写了个Splay维护区间,还T了一发QAQ</del>


====== [C] Operation Love ======

## 题意

给出一个右手的形状,左手与右手是镜像对称的.现在给出一个图形,判断是左手还是右手.

===== 题解 =====

<del>机器学习</del>

可以找一些特殊的向量来判断叉积,卡精度.


====== [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带调就这么过去了.

之后的工作重点还是在尽可能减少罚时上.
CVBB ACM Team

用户工具

站点工具

页面工具
