2021牛客暑期多校训练营3¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 39/814（校内3/22） | 5 | 9 | 10 |
A¶
upsolved by JLK
题意¶
Alice和Bob玩游戏，Alice一开始想好一个\([1,n]\)的整数\(a\)，Bob每次猜一个整数\(x\)，Alice回答是否\(x\ge a\)。Alice可以有一次撒谎机会，并且第一次询问一定回答是。对于每个Bob第一次询问的数\([1,n]\)，求出最少需要多少次能确定\(a\)。
\(1 \le n \le 2000\)
题解¶
可以把游戏简化为：有一个长度为\(n\)的数列，一开始都为0，Bob每次选一个位置把数列分成两段，然后Alice选择一段，把这一段的每个数都加1。当只有一个数小于2时，Bob可以确定。
考虑合法性：当Alice回答大于等于的时候，给小于的数都打上一个“不可能”标签，当某个数被打上两次以上“不可能”标签后，Alice就不可能在这个数上撒谎，而且这个数肯定不是Alice开始选的数。小于同理。
可以发现在游戏中，对Bob最优的情况一定是数列去除大于等于2的数后，第一段\(a\)个1，第二段\(b\)个0，第三段\(c\)个1。
设\(dp_{a,b,c}\)表示这种状态下最少还需要猜多少次。枚举Bob选的分界点转移，对所有分界点取min，对一个分界点左右分别到达的两个状态取max。对分界点在\(a,b,c\)三部分内分别讨论。可以参考这份代码。\(b\)大的一定从\(b\)小的转移，所以要先枚举\(b\)。
这样是\(O(n^4)\)的。不难发现固定\(a,b\)，对于\(c\)是决策单调的。可以优化到\(O(n^3)\)。参考这份代码。
注意到\(dp_{a,b,c}\)最大是\(O(logn)\)级别的（最坏情况就是二分，每个位置问两次）。实际上\(n=2000\)时最大也只有16。
交换值域和第三维。即\(dp_{i,a,b}\)表示再进行\(i\)轮能够猜出，目前数列为\(a,b,c\)的情况中，\(c\)最大是多少。并且这也是有单调性的，\(a,b\)不变，\(i\)越大，\(c\)越大，分界点越大。
最暴力的转移可以参考这份代码。相当于把上面\(O(n^3)\)解法的转移条件全部套到新的状态上。一直往后找，找到第一个不可能的\(c\)停止。利用决策单调，修改一下得到这份代码。但这样还是\(O(n^3)\)的，因为这个单调是基于\(a,b\)固定，决策点仍然会移动\(n\)次。
考虑固定\(i,b\)。\(a\)增大，\(c\)会减小，决策点也会减小（在每次\(a\)增大时先同时增大）。由于变量很多，把三种情况同时考虑没有决策单调性。但是如果分开考虑，三种情况是分别有单调性的。找到满足指定条件的最大决策点就可以转移。转移条件和之前的代码是差不多的。参考这份代码。
\(O(n^2logn)\)
B¶
solved by JLK&TYB
题意¶
一个\(n\times m\)的矩阵，每个点有权值\(c_{i,j}\)。一开始都为白色，可以花费权值将一个点染黑。同时，如果有三个点落在一个长方形的三个顶点上，那么第四个顶点可以免费染色。求染成全黑的最小花费。
\(1 \le n,m \le 5000,1 \le c_{i,j} \le 10^5\)
题解¶
不难发现，答案中有花费染色的点有且仅有\(n+m-1\)个，且他们不会构成长方形的四个顶点。因为如果有长方形的四个顶点，一定可以去掉一个。这样的\(n+m-1\)个点也一定能生成全黑的矩阵。
那么就对点的权值从小到大排序（计数排序），每次取最小的，判断会不会构成长方形。
判断可以使用并查集，比较巧妙。就是把每行和每列建并查集，每次加入一个点\((i,j)\)，就把\(i\)行和\(j\)列连起来。这样如果一个点在加入之前就联通了则会构成长方形。
\(O(n^2+max\{c\})\)
C¶
solved by YZW
题意¶
\(n\times n\) 的网格中有 \(m\) 个位置可以填数，要求所填数大小不超过 \(k\)，并且满足第 \(i\) 行最大值为 \(b_i\)，第 \(j\) 行最大值为 \(c_j\)，给出位置可以不填数，求所有位置填数之和的最小值。
\(1\leq n\leq 2\times 10^3\)，\(1\leq m\leq 8\times 10^5\)，\(1\leq k\leq 10^6\)，并且保证相同的 \(b_i,c_j\) 至多出现 \(500\) 次。
题解¶
贪心地从大到小考虑填写的各个数。设当前考虑数字 \(x\)，那么必须满足所有 \(b_i=x\) 与 \(c_j=x\) 的限制。我们希望填写的 \(x\) 尽量少，因此需要尽可能在 \(b_i=x\) 与 \(c_j=x\) 这样的行列交点填数。二分图匹配可以求得最少填写 \(x\) 多少次，求和即可得到答案。
\(O((n/p)\times p^3)\)，\(p\) 至多 \(250\)。
D¶
upsolved by TYB
题意¶
\(n\times n\)的矩阵，有\(k\)个格子不能选，要求选恰好\(c\)个格子，使得每行、每列、两条对角线都至少选了\(1\)个格子，求方案数。
\(n\le32,k\le7,k\le c\le n^2-k\)
题解¶
显然需要容斥，这种多个限制条件的题目容斥先后顺序是关键。我们先\(2^k\)枚举\(k\)个不能选的格子的状态，因为这个状态决定了后面哪些行、列、对角线不能被ban掉（即最少选择一个格子），容斥掉这个限制，然后再考虑后面怎么做。注意到方案数与最后剩下几个可以选择的格子有关，设\(A\)为可选择的行数，\(B\)为可选择的列数，\(X\)为所在行列均可以选择但因为对角线的限制而不能选择的格子数，则最后可选的格子数为\(A\times B-X\)。\(A、B、X\)均为\(O(n)\)级别，考虑这个怎么算。先枚举两条对角线是否选择，然后做一个DP：\(f_{i,j,k}\)表示有\(i\)行可选，\(j\)列可选，\(k\)个因为对角线不能选，即\(i,j,k\)分别对应\(A,B,X\)，DP转移每次考虑第\(i\)行，第\(i\)列，第\(n-i+1\)行，第\(n-i+1\)列，因为它们对对角线的贡献是互相影响的，而没有后效性。枚举它们的\(2^4\)个状态，相当于是一个三维背包，选\(\frac{n+1}{2}\)个物品，每次从这\(2^4\)个中选择一个。然后就可以算了。
复杂度\(O(2^kn^4)\)，但常数较小。
E¶
solved by YZW
题意¶
给出 \(n\)，求 \(xy+1|x^2+y^2\) 且 \(1\leq x\leq y\leq n\) 的 \((x,y)\) 对数。
\(1\leq n\leq 10^{18}\)。
题解¶
打表可以发现通解 \((a,a^3)\)。
对于 \(a\)，令 \((x_0,y_0)=(a,a^3)\) 为 \(a\) 生成的解，那么 \((x_i,y_i)=(y_{i-1},a^2y_{i-1}-x_{i-1})\) 也为解。
可以计算得到形如 \((a,a^3)\)，\((a^3,a^5-a^3)\) 的解的数量，预处理剩余解，查询即可。
F¶
solved by TYB
题意¶
经典的24点游戏是\(4\)个数算出\(24\)，这题是\(n\)个数算出\(m\)。求出所有\(n\)个数的问题中，能算出\(m\)的，且每种算出\(m\)的方法中都存在小数的问题，输出方案数，并按字典序输出所有方案。 每个数都是\([1,13]\)范围内的，\(1\le n\le 4,1\le m\le 10^9\)
题解¶
注意到只有\(n=4\)时会有解，且只用check\(13^4\)种方案，直接爆搜即可。
G¶
upsolved by TYB
题意¶
给出一棵\(n\)个节点以\(1\)为根的树，初始每个节点没有权值。有两种操作，一是把节点\(u\)的权值改为\(x\)，二是询问节点\(u\)的祖先中，离\(u\)最近的满足权值在\([l,r]\)范围内，且是\(x\)的倍数的祖先。
修改操作保证每个节点的权值只会被修改最多一次，且修改操作中的\(x\)不会重复。
\(n,q,x\le 1.1\times 10^5\)
题解¶
比较难处理的是倍数这个限制，其它的都可以用常规的数据结构解决。注意到修改操作的\(x\)不会重复，可以考虑对于每个修改操作的\(x\)，枚举它的因数，把这个修改操作挂在它的因数那里，也就是将其拆成因数个修改，那么此时的修改个数是\(n\ln n\)级别的。然后枚举每个数\(x\)，处理它的询问，现在就去掉了倍数这个限制条件，也就是询问节点\(u\)第一个权值在\([l,r]\)范围内的祖先。做轻重链剖分，从\(u\)开始跳重链，每次就是询问某个\(dfs\)序范围内是否有\([l,r]\)范围内的数，是个二维数点问题，可以树套树。找到第一个满足的重链，然后在上面二分即可。
复杂度\(O(n\log^3 n)\)
H¶
upsolved by
题意¶
题解¶
I¶
upsolved by JLK
题意¶
长度为\(n\)的序列\(a\)，\(q\)次操作，一种是区间异或某个数，一种是区间里下标为\(i\)的数异或\(x+(i-l)\)。求最终序列。
\(1 \le n \le 6\times 10^5,1 \le q \le 4\times 10^5,0 \le a_i \lt 2^{30}\)
题解¶
第一种操作直接差分即可。只考虑第二种操作。
对每一位单独考虑。
Sol.1¶
对于当前第\(bit\)个二进制位，只考虑二进制的后\(bit\)位。那么如果一个操作让\(a_i\)需要异或一个\(2^{bit}\)，则\((i-l+x) \mod 2^{bit+1} \ge 2^{bit}\)。下面操作全部取模。
进而可以求出\(x-l\)的范围：\(2^{bit}-i\le x-l \lt 2^{bit+1}-i\)（在模意义下有可能拆成前后两个区间）
那么从小到大扫一遍\(n\)，只要用一个BIT，在\(l\)的时候插入\(x-l\)，在\(r+1\)的时候删去，对于每个\(i\)都可以区间求和求出有影响的操作的数量，进而得到答案。
注意到，\(bit\)比较大的时候，无法用BIT存储。但是也没有必要用BIT存储。比如\(2^{bit}\ge n\)的时候，这个操作对整个序列至多只有一段0和一段1的影响。可以把所有操作比较大的部分拎出来，剩下的再做之前的步骤。对于拎出来的部分，找到进位的位置，然后就转化成第一种操作。可能细节较多。
\(O(nlognloga)\)
Sol.2¶
和上面类似，注意到\(2^{bit}-(x-l)\le i \lt 2^{bit+1}-(x-l)\)。
在模\(2^{bit+1}\)下，如果把\(n\)看成\(\lfloor \frac{n}{2^{bit+1}}\rfloor+1\)行\(2^{bit+1}\)列的矩阵，那么需要异或的位置其实是一个矩形加上一些边角料。可以做二维差分，前缀和相当于异或的奇偶性。把所有询问做成差分，每次扫一遍\(n\)做一次前缀和就可以得到了。
\(O(nloga)\)
J¶
solved by YZW
题意¶
给出 \(n\) 个点的完全图，每条边为黑白二色其一。求同色三元环的数量。
\(n\leq 8000\)
题解¶
给连接同一个点的两条同色边赋权 \(1/3\)，连接同一个点的两条异色边赋权 \(-1/6\)，求和即可。
\(O(n^2)\)
记录¶
开场被人带歪看A，JLK莽了一发错误解法没过样例。
然后YZW跟榜签J(0:19)，TYB签(?)F(0:53)。
YZW对E打表找规律，得到了一些想法。JLK和TYB讨论B后觉得可做，踢下来写B。发现考虑不完善，WA一发后改并查集AC(1:38)。
随后YZW写完了E(1:43)。
随后YZW写了C(2:19)。
此时五题，排名靠前。然后三人看I，JLK&TYB想了个解法，YZW想了个解法。认为YZW的解法好写，于是YZW开写，JLK&TYB看G。想了个时间爆炸的算法（后来发现假了）。
YZW WA了(3:08)，对拍后发现假了。JLK开始接盘I。4:16写完，然后一直WA/TLE。本地拍不出来。成功罚坐3h。
总结¶
JLK：没啥好说的，最后有个小错误没发现确实没办法，只能说积累经验了。
Dirt¶
B(-1)