2020牛客暑期多校第三场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 35/1175 | 8 | 10 | 12 |
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\) 个点是左手还是右手（图为左手），左右手大小不变。
题解¶
暴力找哪两个点是最下面的点即可，即两个点的距离位 \(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<b,f<b,c,e\le10^{12},\frac{c}{d}-\frac{e}{f}=\frac{a}{b}\)。如果找不到输出 \(-1 -1 -1 -1\)
题解¶
先判断 \(gcd(a,b)\) 是否为 \(1\)。如果不为 \(1\) ，容易构造出来 \(c=\frac{a}{gcd(a,b)}+1,d=\frac{b}{gcd(a,b)},e=1,f=\frac{b}{gcd(a,b)}\)
若 \(gcd(a,b)=1\) ,判断 \(b\) 是否存在至少两个不同的质因数。如果存在则找到 \(p\not =1,q\not =1\) 有\(gcd(p,q)=1\)，令 \(d=p,f=q\)，之后会得到一个裴蜀方程 \(fc-de=a\) ，扩展欧几里得解一下正整数解即可。如果不存在，则一定不存在 \(d<b,f<b\) 使得 \(lcm(d,f)=b\),输出 \("-1 -1 -1 -1"\) 即可。
G¶
solved by JJLeo
题意¶
给定一个\(n\)个点\(m\)条边的无向连通图，一开始\(i\)点的颜色就是\(i\)。每次操作选择一个颜色\(c\)，如果已经不存在这个颜色则无事发生；否则如果某个点的颜色为\(c\)，另一个颜色为\(d\)的点与该点相邻，则所有颜色为\(d\)的点全部变为颜色\(c\)。问全部操作完成后所有点的颜色。\((n,m \le 8 \times 10^5)\)
题解¶
显然每次操作后每种颜色组成的点是一个联通块。因此每种颜色的点在扩张一次后就不会再产生作用，可以将其称作某种颜色的内侧点，而每次新加入的点则称作外侧点，可以考虑开一个vector放每种颜色的外侧点。扩张某种颜色时遍历上述vector中的全部外侧点，合并所有相连的其它颜色对应的vector，并将扩张过的点弹出vector，除合并外每个点仅进出vector一次，合并时采用启发式合并，时间复杂度\(O(\log n)\)。
H¶
upsolved by Bazoka13
题意¶
每次替换一个位置的字符，将所有到达的字符串排序
题解¶
因为给了\(2e6\)的数据，硬排会\(T\)掉,考虑到一种分治的思路，每次取当前区间会改变字符的最小值，那么区间被分成的两部分就可以确定大小，而最小值可以用笛卡尔树找到，二者结合即可
I¶
upsolved by
题意¶
题解¶
J¶
upsolved by
题意¶
题解¶
K¶
upsolved by JJLeo
题意¶
两人玩游戏。给定一个由数字和至少一个问号组成的序列，每人轮流将一个问号改为一个数字。如果问号数量为奇数则A先手，否则B先手。最终所有问号的被填完后，如果所得数字是\(11\)的倍数，则本轮游戏得分为该数字，否则得分为该数字的相反数。A希望数字越大越好，B希望数字越小越好，如果他们会按照最优策略进行操作，求最终游戏结果。
题解¶
前置芝士：一个数是\(11\)的倍数等价于奇数位之和减去偶数位之和是\(11\)的倍数。
可以发现A永远走最后一步，因此我们不妨考虑一个状态是A必胜还是A必败。设此时有\(x\)个奇数位的问号和\(y\)个偶数位的问号，奇数位之和减去偶数位之和模\(11\)为\(z\)，那么状态\((x,y,z)\)是A必胜态等价于\(10(y-x) \equiv z \pmod {11}\)，证明如下：考虑如果\((x,y,z)\)是A必胜态，那么\((x-1,y,z-10),(x+1,y,z+10),(x,y-1,z+10),(x,y+1,z-10)\)都是必败态，而当前者是必败态时后者都是必胜态；我们以前者是必胜态为例分析该结论，每次操作最多只能\(\pm 9\)，不可能实现\(\pm 10\)，如果自己的回合无法到达必胜态，那么对手就可以通过操作达到必败态（因为\(\pm 20\)在模\(11\)下等价于\(\pm 9\)，一先一后两次操作后，后手一定可以达到这个值）；而最终A胜利状态为\((0,0,0)\)，即可推导出结论中的公式。
输赢确定后，考虑双方会如何进行最优操作。必赢的一方要保证每一步操作后都是对手的必败态的前提下使得最终数字的绝对值更大，而必输的一方只用考虑使得最终数字的绝对值更小。如果必胜一方先手，那它第一步有两种选择，在奇数位填或在偶数位填进入对手的必败态，可以直接将两种情况都算一遍最后取绝对值更大的即可，此时填的数字可以通过上述结论算出来，如果是非\(0\)数，那么要填在奇数位或偶数位的最高位，否则要填在奇数位或偶数位的最低位，这样做显然是最优的。接下来，进入必败方-必胜方-必败方-必胜方的循环，必败方显然要让更高的位填\(0\)才能使绝对值更小。通过对上述结论可以得到如果必败方在奇数位填\(0\)，那么必胜方只能在奇数位填\(9\)或在偶数位填\(0\)，如果必败方在奇数位填\(9\)，那么必胜方只能在奇数位填\(0\)或在偶数位填\(9\)，奇偶反转过来也是同样成立的。因此通过亿阵博弈思考，得出以下结论：设奇数位置上有\(x\)个问号，偶数位置上有\(y\)个问号，那么如果\(xy\)奇偶性相同，最终双方的策略都是按顺序填\(09090909 \cdots\)；否则可以在其中一个填\(009090909 \cdots\)，另一个还是按顺序填\(09090909 \cdots\)，哪个先填两个\(0\)可以由必败方决定，因此讨论对应位置的前后即可得到大小关系，选择更小的那一个即可。
值得一提的是，必败方并不是只会一直填\(0\)，上述先填两个\(0\)的方案就是通过必败方从后往前填\(9\)逼迫必胜方填\(0\)从而达成的。
L¶
solved by JJLeo
题意¶
签到
题解¶
比手速
记录¶
0min：分配读题
2min：ZYF 秒L，和MJX 看B，CSK 冲F
14min：CSK WA F
21min：找到B性质 MJX AC B，ZYF 看 A， MJX看C
34min：MJX AC C,ZYF 看A
47min：ZYF WA1 后 AC A，大家一起看F
97min~113min：经过漫长的讨论终于 AC F，CSK ZYF 看E，MJX 看D
114min：CSK ZYF 秒 E，看G
152min：CSK ZYF 秒 G，ZYF MJX构造D，CSK 看 H
227min：ZYF构造心态崩了，MJX接盘
261min：MJX AC，讨论 K
till end：对K有初步想法，然而没时间写了。
after end：ZYF 对于 ? 以及数字构成的序列产生了厌恶
总结¶
- CSK强制下机，很痛苦，CSK\(H\)题写了傻逼线段树，很痛苦
- MJX写代码常有小 bug ，下场尤为突出
- ZYF在懵逼时要及时交给队友接盘，避免浪费时间。