======2020牛客暑期多校第三场====== [[https://ac.nowcoder.com/acm/contest/5668|比赛链接]] =====A.===== **solved by JJLeo** ====题意==== 一共有$n$天，每天可能会有鱼或没鱼，可能会有蛤或没蛤，如果有鱼就可以抓鱼，如果有蛤就可以抓蛤做诱饵，如果之前有做好的诱饵就可以用诱饵抓鱼（不需要有鱼），每天至多进行一种操作，问最后最多能抓多少鱼。 ====题解==== 有鱼肯定直接抓，其它情况倒着扫一遍记录后面有几个空的天用于诱饵抓鱼，如果天数够就做诱饵，否则就把诱饵用掉。 =====B.===== **solved by 2sozx** ====题意==== 给定一个字符串 $S,|S|\le2\times10^6$ 定义三种操作，将 $S$ 的前 $x$ 位移动到 $S$ 末尾；将 $S$ 的后 $x$ 位移动到 $S$ 开端；询问 $S$ 的第 $x$ 位是什么字符。 ====题解==== 容易发现前两个操作不改变 $S$ 的相对顺序，因此每次操作记录操作之后 $S$ 的起点在哪即可。 =====C.===== **solved by 2sozx** ====题意==== $t$ 组询问，每个询问按照顺时针或者逆时针给出 $20$ 个点，问这 $20$ 个点是左手还是右手（图为左手），左右手大小不变。\\ {{:2020-2021:teams:farmer_john:牛客多校第三天c.png?400|}} ====题解==== 暴力找哪两个点是最下面的点即可，即两个点的距离位 $9$ ，之后找到大拇指外侧的点，通过叉积判断方向即可判断左右手。 =====D.===== **solved by 2sozx** ====题意==== 设二维平面全部整点均为白色点，现在可以选择 $n$ 个点使其变为黑色。如果有两个点相邻，即 $|x_1-x_2|+|y_1-y_2|=1$ 并且颜色不同，则不同颜色的对数加一，问是否有一种选点方式使得最后有 $m$ 个不同颜色的对数。$n\le 50,m\le 200$ ====题解==== 先考虑 $m$ 在什么范围可以构造出来。显然 $m>4*n$ 不可能构造。我们考虑 $m$ 的下界，显然 $n$ 个数构成一个连通块的时候 $m$ 最小，考虑一种构造方案使得每次构造都最优，即优先向正方形构造。假定已经是一个正方形，下一个黑色的点必定连在一条边的外边，这样可以构造出一个 $L$ 形，下次放在 $L$ 形的中心最优。如果已经是一个矩形，则下一个黑点应该在短边的外面相连，重复这种操作即可。可以预处理出来 $m$ 的下界。考虑构造，在已知的最优情况下考虑移动点，可将仅与两个黑点相连的点移动到仅与一个黑点相邻的白点上，这样会使得 $m+2$ ,如果不存在与两个黑点相邻的点，则选择与一个黑点相邻的白点并将其移动到无穷远处即可，易知这样构造是可以满足条件的。 另一种构造方法：我们先考虑 $x$ 个点对角线相连的情况，这样会有 $4*x$ 个对数，我们很容易会发现再加上 $x^2-x$ 个点依旧可以很容易的做出总对数不变的情况，如果目标的 $m$ 并非是 $4$ 的倍数，我们可以在对角线的端点向外侧连上一个点，总对数为 $4*x+2$ 并且我们会多出 $x$ 个可以使总对数不变的点。这样反过来给定 $m$ 时也可以构造出答案。 =====E.===== **solved by JJLeo** ====题意==== 给定偶数个元素，选择两种完全不相交的使他们两两匹配的方案（不相交指两种方案不能有两个元素都在同一组），使得两次匹配中所有匹配的两元素差值之和最小。 ====题解==== 考虑找到最小和次小的两种匹配方式，最小肯定是排序后然后从小到大两个两个组合即可。次小需要进行dp，考虑排序后的某个元素跨过偶数个元素与后面某个元素匹配，这样自己以及中间的元素就可以错开匹配，扫一遍维护最小值即可。 =====F.===== **solved by 2sozx** ====题意==== 给定两个数 $a,b(a,b\le2\cdot10^6)$，要找到 $c,d,e,f$ 使得满足 $d