2021牛客暑期多校训练营10¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 20/1015（校内2/18） | 4 | 10 | 11 |
A¶
solved by JLK
题意¶
给\(n\)个字符串\(A_i\)，对于每个\(i\)，要求选出最小的字符串集合\(S\)，使得\(j \le i\)时，\(A_j\)至少有一个前缀在\(S\)里，并且\(j \gt i\)时，\(A_j\)没有一个前缀在\(S\)里。求\(S\)的最小大小。
\(1 \le n \le 10^5,1 \le len(A_i) \le 100\)
空间限制32MB。
题解¶
如果没有空间限制，可以建一个Trie树，那么每个结点代表一个前缀，当子树里含有的所有字符串都需要有一个前缀时，就可以用这个结点来表示所有子树里的字符串。否则，就需要在子树里细分。可以用一个差分来解决。
问题是空间卡死了。可以使用SA中按Height从大到小合并建成一棵树的方法，建出来的树本质上类似与压缩后的Trie树。
由于长度很小，可以直接基数排序得到SA，枚举得到Height。然后建树计算即可。
\(O(\sum len)\)
B¶
**upsolved by **
题意¶
题解¶
C¶
upsolved by JLK
题意¶
一个两边各\(n\)个点的二分图。对于左边的点\(i\)，它和有\(k_i\)个右边的点没有连边，和其他右边的点都有连边（即，有\(n-k_i\)条边）。求一个完美匹配的方案。
\(1 \le n \le 3\times 10^4，0 \le k_i \le 100\)
题解¶
由于\(0 \le k_i \le 100\)，下面\(k\)均当做100。\(k_i\)小于\(100\)的情况在做法上是一样的。
Sol.1¶
对于左边的前\(n-k\)个点，在右边找，找到能匹配的就匹配。这样每个点是都可以找到的，因为每个点有\(n-k_i\)个点可选，不可能出现全被其他点选了的情况。
对于剩下的\(k\)个点，每个点\(i\)跑一遍匈牙利找增广路。连边方式是：\(i\)能连的边都连，对于\(j\lt i\)的点\(j\)，找到\(i\)不能连而\(j\)能连的边连起来。显然，若\([1,i]\)都能被匹配，那么从\(i\)出发一定能找到一条新的增广路。不能匹配则无解。
这样边数是\(O(nk)\)，找一条增广路也是\(O(nk)\)。总复杂度为\(O(nk^2)\)。
Sol.2¶
先把右边的度数小于\(100\)的点找出来，点的个数是\(O(k)\)级别，跑一遍二分图匹配。这样的复杂度为\(O(k^3)\)或\(O(k^{2.5})\)。若无解直接跳出。
然后剩下度数大于等于\(100\)的点，再枚举左边没有匹配的点，找到能匹配的就匹配。由于最多找\(k_i+1\)次就能找到或无解，这部分复杂度为\(O(nk)\)。
总复杂度为\(O(nk+k^{2.5})\)，不会证明。
D¶
upsolved by TYB
题意¶
求所有\(n\)个点有标号无根树的直径之和。
\(n\le500\)
题解¶
树计数问题主要是要找到一种不重不漏的计算方法。
对于本题，考虑利用直径的中心计数。设直径为\(d\)，若\(d\)为奇数，则直径的中心是一条边，若根节点的深度为\(1\)，则这棵树可以看做是边的两个端点挂了两棵深度恰好为\(\lceil \frac{d}{2}\rceil\)的树；若\(d\)为偶数，则直径的中心是一个点，这棵树可以看做这个点挂了若干棵树，所有深度都\(\le\frac{d}{2}\)，且至少两棵树的深度为\(\frac{d}{2}\)。
考虑算出\(f[i][j]\)表示\(i\)个点深度恰好为\(j\)的树有多少。直接算不好算，考虑算出\(g[i][j]\)表示\(i\)个点深度\(\le j\)的树有多少，再用容斥原理算出\(f[i][j]\)。以上的树指除了根节点其他点都有标号的有根树。根节点无标号是因为避免一些算重的问题。\(g[i][j]\)的转移方程为： $$ g[i][j]=\sum_{k=1}^{j-1}g[i-k][j]\times g[k][j-1]\times k\times \tbinom{i-2}{k-1} $$ 即每次在深度\(\le j\)树的根节点下挂一棵深度\(\le j-1\)的数，乘\(k\)是为了把新加树的根节点算上，组合数是强制标号为\(1\)的节点在当前新加的这棵子树中避免重复。
然后就是最后的统计答案。中心是一条边的情况比较简单，不赘述；中心是一个点的情况，考虑容斥，减去不合法的情况，即用深度恰好为\(\frac{d}{2}+1\)的树，减去只有一棵子树深度为\(\frac{d}{2}\)的情况，具体细节可以参考代码。
复杂度\(\mathcal{O}(n^3)\)。
E¶
upsolved by JLK
题意¶
\(k\)维空间，每一维的范围为\([1,a_i]\)，现在有一个棋子在\((b_1,b_2,\cdots,b_k)\)，\(q\)次询问，每次永久改动\(d\)个维度的坐标，求按照给定规则移动一步的方案数。
五种棋子：
King：选择一个维度的非空集合，对集合中每个维度的坐标分别加1或减1。（可以一部分加一部分减，下同）
Queen：选择一个维度的非空集合，再选择一个正整数\(x\)，对集合中每个维度的坐标分别加\(x\)或减\(x\)。
Rook：选择一个维度，再选择一个正整数\(x\)，对这个维度的坐标加\(x\)或减\(x\)。
Bishop：选择一个维度，再选择一个正整数\(x\)，对这两个维度的坐标分别加\(x\)或减\(x\)。
Knight：选择一个维度，对这个维度的坐标加1或减1，再选择一个维度，对这个维度的坐标加2或减2。
\(1 \le k,q,\sum d_i \le 3\times 10^5,1 \le a_i \le 10^6\)
题解¶
Rook的答案就是\(\sum\limits_{i=1}^n (a_i-1)\)。
对于King，只需要知道有多少维度既可以加1也可以减1，多少维度只能加1或只能减1。设前者为\(x\)，后者为\(y\)，答案就是\(3^x2^y-1\)。
对于Queen，考虑暴力做法，枚举长度，就可以转化为King的做法。
实际上一个维度对每个长度的贡献只有三段，设当前维度到两端的最小距离为\(p\)，最大距离为\(q\)，那么对\([1,p]\)长度的贡献是乘3，对\([p+1,q]\)的贡献是乘2，否则是乘1。每次修改也只会改动三段的贡献。可以用线段树来维护，需要区间乘法和区间求和。
对于Knight，可以把每个维度到两边的距离单独考虑，只需要知道有多少方案能移动1，有多少方案能移动2，两个相乘再减去选到同一个维度的方案即可。
对于Bishop，枚举长度，那么就是选两个维度的King。
同样把所有方向单独考虑，先不考虑选到相同维度的两个方向，那么对于长度\(i\)，能移动\(i\)的方向有\(x\)个，那么就是\(C_{x}^2\)。每个维度的贡献为三段，这也可以用线段树维护。相当于是区间加以及区间维护\(x^2-x\)。
\((x+k)(x+k-1)=x^2-x+2kx+k^2-k\)，用\(\sum x\)和\(\sum1\)来更新\(\sum (x^2-x)\)即可。
\(O(d \log a_i)\)
F¶
solved by JLK
题意¶
有\(n\)个点，他们有一个入栈出栈的序列。给定\(n\)个颜色（有可能重复），要给\(n\)个点分配颜色，使得每次有点入栈后，得到的栈的颜色序列都是不同的。
\(1 \le n \le 10^6\)
题解¶
很容易能够把这个入栈出栈的序列用树来表示。即每个点连到他入栈时的栈顶。
那么问题就变为给树染色，使得每个点的儿子颜色各不相同。
对于一个点的所有儿子，只需要选取剩余出现次数最多的几个颜色去染即可，这样一定是最可行的。如果染不够了，就是无解。可以用堆来维护剩余出现次数最多的颜色。
\(O(n\log n)\)
G¶
upsolved by TYB
题意¶
\(n\)个人围成一圈，每个人独立随机地选择一名其他玩家并向其开一枪，开枪是同时的，被命中者立刻阵亡退出游戏。假设所有人的命中概率都为\(p\)，问恰好\(k=0,1,2,\cdots,n\)个人存活的概率。
\(n\le3\times10^5\)
题解¶
设\(g_i\)为最后至少\(i\)人存活的概率，则\(g_i=\tbinom{n}{i}(1-p+p\frac{n-i-1}{n-1})^{n-i}(1-p+p\frac{n-i}{n-1})^i\)。
就是要选出\(i\)个人，然后每个人要么没有打中，要么没有打到这\(i\)个人。
设\(f_i\)为最后恰好\(i\)人存活的概率，则\(f_i=\sum_{j=i}^n(-1)^{j-i}\tbinom{j}{i}g_j\)。
可以通过二项式反演得到，也可以看做是容斥系数多带了一个组合数。
再化一下得到\(f_i\times i!=\sum_{j=i}^n\frac{(-1)^{j-i}}{(j-i)!}j!g_j\)，用NTT优化即可。
H¶
solved by YZW
题意¶
题解¶
I¶
**upsolved by **
题意¶
题解¶
J¶
solved by YZW
题意¶
题解¶
K¶
upsolved by TYB
题意¶
\(n\times m\)的矩阵，初始在\((a,b)\)，求走恰好\(t\)步且没有走出过边界的方案数。
\(n,m,t\le5\times10^5\)
题解¶
首先行和列可以分开考虑，因此只用考虑该问题的一维版本，即\(n\)个格子，初始在\(a\)，走\(t\)步后不走出边界的方案数。
有一个朴素的做法：\(f[i][j]\)表示走了\(i\)步到了\(j\)的方案数，转移显然，复杂度\(\mathcal{O}(nt)\)。
换一个思路考虑，设\(K[i]\)表示走了\(i\)步的答案，则
\(K[i]=\sum_{j=1}^nf[i][j]\)
\(=\sum_{j=2}^{n-1}f[i-1][j+1]+f[i-1][j-1]+f[i-1][2]+f[i-1][n-1]\)
\(=2\sum_{j=1}^nf[i-1][j]-f[i-1][1]-f[i-1][n]\)
\(=2K[i-1]-f[i-1][1]-f[i-1][n]\)
这启发我们，只要能快速求出\(f[i-1][1]\)和\(f[i-1][n]\)就能直接递推下去。
以计算\(f[i][1]\)为例，设起点在\(a\)，要走\(t\)步。将问题形象化，即初始在\((0,a)\)，往左走一步坐标由\((x,y)\)变成\((x+1,y-1)\)，往右走变成\((x+1,y+1)\)，不穿过\(y=1\)和\(y=n\)这两条直线，最后走\(t\)步到达\((t,1)\)的方案数。这是个经典问题，若只有直线\(y=1\)的限制，则直接减去穿过这条线的方案即可，具体来说，若穿过\(y=1\)，则一定会经过\(y=0\)，考虑如何计算一定经过\(y=0\)后再到达终点的方案数，假设一种方案中第一次到达\(y=0\)时的坐标为\((x',0)\)，将\((x',0)\)到\((t,1)\)的这段路径关于直线\(y=0\)对称翻折过来，则可以发现一定经过\(y=0\)再到\((t,1)\)的方案与到\((t,-1)\)的方案可以一一对应，那就可以直接计算了。对于本题，有两条直线的限制，考虑分为两部分，减去先穿过\(y=n\)和先穿过\(y=1\)的两类不合法方案，但不合法方案不能够像上面的一样简单计算，因为算穿过\(y=1\)的方案时，会把先穿过\(y=n\)的方案算上，考虑减去先穿过\(y=n\)再穿过\(y=1\)的方案数，则又会多算先后穿过\(y=1,y=n,y=1\)的方案数……这样实际上是不断的做对称变换的过程，而对称的增长速度大概每次为\(n\)，所以最多\(\frac{t}{n}\)次后的贡献就都为\(0\)，用这种方法做，复杂度是\(\mathcal{O}(\frac{t^2}{n})\)。
平衡一下复杂度，\(\mathcal{O}(t\sqrt t)\)。
（感觉说得不太清楚，建议结合这里的图片和官方题解最后的式子来看）
记录¶
开局签H(0:11)。
JLK和TYB讨论后过F(0:46)。
TYB想G，但是式子推不出来。
不断换题后发现A可做，JLK过A(2:42)。
YZW写J(4:08)。
其余时间基本都在东想西想，都不会做。
总结¶
JLK:这场大家都比较谨慎，所有题目都是1A，还是不错的。可能在计数题目方面需要加强训练。
Dirt¶
无