2021牛客暑期多校第三场

排名	当场过题数	至今过题数	总题数
50/815	5	9	10

A

upsolved by JJLeo

题意

Alice 自己想一个 \([1,n]\) 的整数 \(x\)，然后 Bob 每次可以猜一个数 \(y\)，Alice 需要告诉他 \([y \ge x]\)。

Alice 可以撒谎至多一次，Alice 希望 Bob 猜尽可能多的次数，Bob 则相反。两人在最优策略下会猜多少次。

(\(1 \le n \le 2000\))

题解

博弈等价于如下形式：

一开始 \(n\) 个数均为 \(0\)，Bob 每次选择一个位置 \(p\)，Alice 要么将 \([1,p-1]\) 的所有数增加 \(1\)，要么将 \([p,n]\) 的所有数增加 \(1\)，直到仅有 \(1\) 个数 \(\le 1\)。

Alice 希望最大化游戏轮次，Bob 则相反。

首先证明这对于 Bob 是等价的：

每次增加 \(1\) 相当于 Alice 否决了一些数，但是 Alice 可能会撒谎，因此一个数被否决一次不能保证其确实不行。但 Alice 只能撒谎一次，因此一个数否决了两次就一定不行，从而剩下 \(1\) 个数 \(\le 1\) 就可以确定是这个数。

再证明这对于 Alice 是等价的：

考虑任何一个游戏终止局面，如果仅有 \(1\) 个数 \(=0\)，说明这个数没有被否决，从而 Alice 所有操作都是合法的；否则如果仅有 \(1\) 个数 \(=1\)，那么覆盖这个数的那一次操作可以认为 Alice 是撒谎的，不考虑这次操作的话，这个数就是 \(0\) 了，从而其它操作均是合法的。综上，转化后的游戏均可以对应原游戏的一个合法操作序列。

也就是说，Alice 如果采取最优策略，那么他到最后一步之前都不一定能完全确定他选的数是哪个，但这从 Bob 的视角看来是完全合法的。

容易发现一个数如果变成 \(\ge 2\) 就可以将其删去，所以序列一定始终形如 \(i\) 个 \(1\) + \(j\) 个 \(0\) + \(k\) 个 \(1\) 的形式。

因此我们考虑最暴力的 dp，设 \(f_{i,j,k}\) 为当前序列为 \(i\) 个 \(1\) + \(j\) 个 \(0\) + \(k\) 个 \(1\)，还有多少轮游戏结束。转移即为 Bob 枚举选哪个位置，Alice 选择能让轮次更大的那一侧 \(+1\)，Bob 在所有位置中选择轮次最少的那个，时间复杂度为 \(O(n^4)\)。

一个优化是对于固定的 \(i,j\)，\(k\) 越大那么选择的位置必然更靠右，利用决策单调性可以优化到 \(O(n^3)\)。

考虑 \(f_{i,j,k}\) 的值不会很大，每个位置问两次也只有 \(O(\log n)\)，因此将第三维和值域调换，记 \(g_{i,j,F}\) 为使得 \(f_{i,j,k} \le F\) 的最大的 \(k\)，如果 \(k=0\) 都不行则令 \(g_{i,j,F}=-1\)。

设当前状态为 \(g_{i,j,F}\)，当前序列为 \(i\) 个 \(1\) + \(j\) 个 \(0\) + \(g_{i,j,F}\) 个 \(1\)，这个序列还能进行 \(F\) 次，有如下转移：

下面我们用 \((i,j,k)\) 来表示 \(i\) 个 \(1\) + \(j\) 个 \(0\) + \(k\) 个 \(1\)。

• 如果枚举位置 \(p\) 在 \(i\) 个 \(1\) 中，也就是 \(p \le i\)，那么向左增加的话序列变成 \((i-p+1,j,k)\)，其还能进行 \(F-1\) 次，因此 \(k\) 至多为 \(g_{i-p+1,j,F-1}\)；向右增加的话，状态直接变为 \((p-1+j,0,0)\)，因此只需保证 \((p-1+j,0,0)\) 可以进行 \(F-1\) 次就可以转移，即 \(g_{p-1+j,0,F-1} \ge 0\)，否则 Alice 选择向右增加就寄了。
• 如果枚举位置 \(p\) 在 \(j\) 个 \(0\) 中，也就是 \(i < p \le i + j\)，那么向左增加的话序列变成 \((p-1-i,j-p,k)\)，其还能进行 \(F-1\) 次，因此 \(k\) 至多为 \(g_{p-1-i,j-p,j,F-1}\)；向右增加的话，状态直接变为 \((i,p-1-i,i+j-p+1)\)，因此只需保证 \((i,p-1-i,i+j-p+1)\) 可以进行 \(F-1\) 次就可以转移，即 \(g_{i,p-1-i,F-1} \ge i+j-p+1\)，否则 Alice 选择向右增加就寄了。
• 如果枚举位置 \(p\) 在 \(k\) 个 \(1\) 中，也就是 \(i+j<p\le i+j+k\)，那么向左增加的话序列变成 \((j,0,k_1)\)，向右增加的话序列变成 \((i,j,k_2)\)，其中有 \(k_1+k_2=k\)，因此只要 \(g_{j,0,F-1} \ge 0\) 且 \(g_{i,j,F-1} \ge 0\) 那么只要 \(k\le g_{j,0,F-1}+g_{i,j,F-1}\) 就可以找到一个位置使得两侧均能再进行 \(F-1\) 轮，超过这个值则不行，从而可以转移为 \(g_{j,0,F-1}+g_{i,j,F-1}\)。

直接进行转移复杂度为 \(O(n^3 \log n)\)，考虑如何优化。前两个转移是 \(O(n)\) 的，转移条件和值分别为：

• 如果 \(g_{p-1+j,0,F-1} \ge 0\)，则可从 \(g_{i-p+1,j,F-1}\) 转移。
• 如果 \(g_{i,p-1-i,F-1} \ge i+j-p+1\)，则可从 \(g_{p-1-i,j-p,j,F-1}\) 转移。

可以发现两者的条件各自随着 \(p\) 增大， \(1\) 越少 \(0\) 越多；可从转移的状态随着 \(p\) 增大，\(1\) 越多 \(0\) 越少。从而 \(p\) 越小，越难转移，但同时对应可从值转移的也越小。

因此对于这两个转移各自维护一个最优决策点，对于 \(g_{i,j,F}\)，当 \(j\) 固定时，随着 \(i\) 的增加，也就是左侧 \(1\) 的增加，\(g_{i-1,j,F}\) 的最优决策点可能无法进行转移，因此需要减小，根据上面的结论，减小到可以转移一定就还是最优决策点，因此可以将转移优化到均摊 \(O(1)\)。

综上，时间复杂度为 \(O(n^2 \log n)\)。

B

solved by 2sozx Bazoka13 JJLeo

题意

\(n \times m\) 的格子，每个格子有一个花费 \(a_{i,j}\)，一开始所有格子都是白的，每次可以用以下两种操作涂黑一个格子 \((i,j)\)：

• 直接花费 \(a_{i,j}\)。
• 如果存在另外三个格子使得这四个格子构成一个正方形的四个顶点，则可以免费涂黑。

求将所有格子涂黑的最小花费。(\(1 \le n,m \le 10^5\)，\(0 \le a_{i,j} < 10^5\))

题解

考虑将每一行当作一个点，每一列当作一个点，每一个格子当作连通一行一列的一条边，则可以发现第二个操作不改变连通性，因此等价于求最小生成树，权值较小可以用计数排序。

C

solved by 2sozx Bazoka13

题意

对于一个 \(n \times n\) 的矩阵，一些位置可以放数，其它位置不能放，同时给出每行每列的最大值 \(b_i,c_j\)，求所有元素和的最小值，保证一定有解，同时 \(b_i,c_j\) 中出现次数最多的数出现次数不超过 \(500\)。(\(1 \le n \le 2 \times 10^3\))

题解

从大到小放数，将所有最大值是 \(x\) 的行和列拿出来，考虑最少要放多少个 \(x\)，显然 \(x\) 越少越好，因此要尽可能在行列交点处放，这可以做一个二分图匹配，左边行右边列，交点数能放数则有连边。设最大匹配数为 \(A\)，最大值是 \(x\) 的行和列有 \(B\) 个，则最少需要放 \(B-A\) 个 \(x\)。

设 \(m=500\)，总时间复杂度不超过 \(O\left(\dfrac{n}{m}m^2\sqrt m\right)=O\left(nm\sqrt m\right)\)。

正确性感性证明：因为一定有解，每次都是取最大匹配放数，因此省下了最多的位置，那么剩下的数肯定依然有位置放。

D

upsolved by JJLeo

题意

\(n\times n\) 的矩阵，\(k\) 个位置不能选，要求每行、每列、正对角线、负对角线都至少有一个格子选，求恰好选 \(C\) 个格子的方案数。(\(1 \le n \le 32\)，\(1 \le k \le 7\))

题解

首先容斥两条对角线是否 ban 掉，共 \(4\) 种可能，设 ban 了 \(d\) 个格子。

接着容斥 \(k\) 个格子是否必选，共 \(2^k\) 种方案，如果和对角线被 ban 冲突，方案为 \(0\)。

接着容斥第 \(i\) 行、第 \(n-i+1\) 行、第 \(i\) 列、第 \(n-i+1\) 列是否要 ban，使用一个三维背包记录没被 ban 的行数 \(a\)、没被 ban 的列数 \(b\)、有多少个对角线上的格子被 ban 了两次 \(c\)，那么最终可以放置的位置数量为 \(ab+c-d\)。设容斥了 \(K\) 个格子必选，方案数为 \(\dbinom{ab+c-d-K}{C-K}\)。

之所以要考虑第 \(i\) 行、第 \(n-i+1\) 行、第 \(i\) 列、第 \(n-i+1\) 列是因为这样可以正确获得对角线上是否被 ban 的信息，同时要注意如果 \(n\) 是奇数那么最中间的两行两列是重合的，需要特判一下。

最后这样的复杂度是 \(O\left(4 \times 2^k \times n^3 \times \dfrac{2n}{4} \times 2^4\right)\)，大约为 \(4 \times 10^{10}\)，背包如果滚动数组逆序枚举会直接跑满导致 TLE。但是注意到其实背包很多状态是不存在的，因此可以正序枚举，对于不存在的状态就不要去 \(O(2^4)\) 转移，这样就可以减小掉大量常数，从而可以通过。

G

upsolved by JJLeo

题意

给定一颗 \(n\) 个节点的以 \(1\) 为根的树，一开始所有点都没有颜色，有 \(q\) 次以下两种操作：

• 给一个点染色，保证这个点没被染色，且颜色是全新的。

• 询问距离 \(u\) 最近的满足下列条件的祖先 \(v\) 是哪个点，或判断没有这样的祖先：

• \(v\) 被染色且颜色序号在 \([l,r]\) 间。

• \(v\) 的颜色序号被 \(x\) 整除。

保证所有颜色序号范围是 \([1,n]\)。

(\(1 \le n,q \le 1.1 \times 10^5\))

题解

所有颜色不同且范围是 \([1,n]\)，容易想到经典调和级数复杂度 \(O(n \log n)\)。

将所有操作离线，一个点如果被染成 \(c\)，就将它拆分为数个操作，放到它所有因数那里。

接下来依次处理每个 \(x\) 对应的询问，现在所有添加的点都是符合颜色序号被 \(x\) 整除的了，我们只需按时间顺序添加点完成剩下的询问即可，现在相当于寻找最近的祖先满足其颜色序号在 \([l,r]\)，可以重链剖分后树状数组套线段树维护。

一种方案是第一维维护颜色，第二维维护 dfn 序，之后在线段树上二分最大的 dfn；另一种方案是两维维护什么都行，找到最深的有答案的重链后，这条重链的 dfn 序连续，可以利用查询在上面再二分最深的点是哪个。两者复杂度相同，均为 \(O(\log ^3 n)\)，线段树上二分看起来常数大一些，因为外层套了树状数组，每层都要存 \(O(\log n)\) 个节点编号。

查询操作共有 \(O(q)\) 次，总复杂度 \(O(q \log ^ 3n)\)，修改操作共有 \(O(q \log n)\) 次，单次修改复杂度 \(O(\log ^2 n)\)，因此总时间复杂度为 \(O(q \log ^3 n)\)。

这里有一个 trick 就是，每次清空的时候只需记录哪些线段树的根被用到，将他们清空就可以了。

脑瘫的我每次直接让第 \(i\) 个根编号就是 \(i\)，这样每次 cnt 从 \(n\) 开始，然后每次把 cnt 个节点都清空，复杂度直接就起飞了。

H

upsolved by 毒瘤

题意

一堆 \(\sum,\max\) 套来套去，隔这儿排列组合。

题解

爬。

I

upsolved by JJLeo

题意

给定一个长度为 \(n\) 的序列，\(q\) 次以下两种操作：

• 给一个区间异或上一个给定数。
• 给一个区间异或上一个差为 \(1\) 的等差数列，首项给定。

最终问序列中每个数是什么，值域为 \(A\)。(\(1 \le n \le 6 \times 10^5\)，\(1 \le q \le 4 \times 10^5\)，\(0 \le A < 2^{30}\))

题解

第一个操作直接差分即可。

第二个操作边界情况不好处理，可以将区间加等差数列改为对两个后缀异或等差数列，只不过第二个后缀首项的值要加上对应的长度，下面只需考虑对一个后缀 \([l,n]\) 异或上一个差为 \(1\) 的等差数列，设首项为 \(x\)。

首先先利用差分数组给 \([l,n]\) 都先异或上 \(x\)，再考虑每个位置相较上一个位置的变化量。

按位考虑每一位，如果看实际贡献，对于每一位都是形如 \(111100001111\) 这样的形式，那么考虑变化量实际就是每隔 \(2^i\) 有一个 \(1\)，当然第一个 \(1\) 的位置需要判断，易得即为这一位变化所需要加上的值，为 \(2^i-(x \bmod 2^i)\)。

那么对于每一位我们找到这个 \(1\) 的位置，维护其二维差分，那么只需在这个位置加一个 \(1\)，最后将其看作一个 \(\left\lfloor\dfrac{n}{2^i}\right\rfloor \times 2^i\) 的矩阵做每一列的前缀和，就可以得到一维差分数组，再结合整体的差分，再做一次前缀和即可得到最终序列。

总时间复杂度为 \(O(n \log A)\)。

记录

0h：看着有人过J了，ZYF说是个原题，而且F也是个原题，直接去写了，MJX想了个B的算法，CSK写完发现假了，MJX直接跑去想E，然后ZYF把F过了，MJX把E打了个表发现规律直接过了

1h：一直在想BC

2h：B被卡常了，MJX YY的C算法完全不对

3h：B过了，C有想了个假算法

4h：C应该用最开始的网络流直接跑就行，想太多了，数组开小了T了一发

after end：B也是个原题，组题人爬

总结

Dirt

B(+4)：MJX两发假算法，加上两发卡常
C(+3)：MJX一发假算法，CSK一发假算法，MJX数组开小了