"蔚来杯"2022牛客暑期多校训练营10¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 57/891 | 4 | 8 | 11 |
A¶
upsolved by TYB
题意¶
给一棵树，点\(i\)有参数\(b_i\)，求满足\(1\le a_i\le b_i\)且对任意相邻点\(u,v\)满足\(a_u\neq a_v\)的序列\(a\)个数。
\(n\le5\times 10^5\)
题解¶
题解写得挺好的。
关键是如何设计状态，使得初始总结点数是\(\mathcal{O}(n)\)，从而可以用线段树合并优化。
B¶
**upsolved by **
题意¶
题解¶
C¶
**upsolved by **
题意¶
题解¶
D¶
upsolved by TYB
题意¶
求\(S\)所有子串整周期长度之和。
\(|S|\le10^6\)
题解¶
求出runs之后咋做都行。
E¶
solved by TYB
题意¶
有\(m\)篇论文和\(n\)个审稿人，给出每个审稿人能审论文的集合，要求给每个审稿人安排一篇论文。令\(f(i)\)表示被至少\(i\)个审稿人审过的论文数量，要求求出一种分配方案，使得\((f(1),f(2),...,f(n))\)字典序最大。
\(n,m\le400\)
题解¶
迷，有空再想想。
F¶
solved by JLK
题意¶
J和C玩游戏，有一个图，可能有重边，C先手。一个棋子要从\(s\)移到\(t\)。C每次可以删掉一个棋子周围的边，J每次删掉一个棋子周围的边并把棋子移动到边的另一端。
如果到达\(t\)就是J赢，否则C赢。问谁赢。
\(1 \le n \le 100,1 \le m \le 10^4\)。
题解¶
考虑怎样J能赢。J能赢当且仅当棋子到达的每个点都有至少两个邻接的必胜点。
首先\(t\)是必胜点，然后从\(t\)开始bfs。把它邻接的点都标记一下，然后把被标记两次的加入队列，一直这样做下去，能推出\(s\)是否是必胜点。
最后实际上有个必胜点集合。所有在集合里的点一定必胜，因为符合上面的条件。
所有不在集合里的点一定必败，因为至多有一条边连向必胜点，C只需要切断这条边即可。所以这样做是对的。
\(O(n+m)\)
G¶
upsolved by TYB
题意¶
对于一个单调递增的整数序列\(A\)，Alice和Bob依次对序列进行如下操作，无法操作的玩家输。
选择\(1\le i\le n\)以及整数\(x\)满足\(A_{i-1}\le x<A_i\)，将\(A_i\)替换为\(x\)，其中\(A_0=0\)。
现在给定正整数\(n,m\)，问后手必胜的初始序列\(A\)满足\(A\)单调递增且\(0\le A_i\le m\)有多少。
\(1\le n\le40000,0\le m\le 10^{12}\)
题解¶
考虑差分数组，其实是在进行阶梯博弈。
阶梯博弈：每次可以从一个阶梯上拿掉任意数量石子放到下一层阶梯，不能操作的为输。 SG 函数为奇数阶梯上的石子的异或和，如果移动偶数层的石子到奇数层，对手一定可以 继续移动这些石子到偶数层，使得其 SG 不变。 必胜：SG 不为 0，必败：SG 为 0。
那么问题可以转化为：有\(n+1\)个数，要求前\(\lfloor\frac{n+1}{2}\rfloor\)个数的异或和为\(0\)，且\(n+1\)个数的和为\(m\)。
数位DP，\(f_{i,j}\)表示前\(i\)位满足条件，且第\(i\)位给\(i+1\)位贡献了\(j\)个\(1\)的方案数。那么有转移：\(f_{i+1,k+\frac{j}{2}-m_{i+1}}\leftarrow f_{i,j}\times g_k\)。其中\(g_k\)表示长度为\(n+1\)的\(01\)序列，共\(k\)个\(1\)，且前\(\lfloor\frac{n+1}{2}\rfloor\)个数异或和为\(0\)的方案数。
FFT优化即可。
\(\mathcal{O}(n\log n\log m)\)。
H¶
solved by TYB
题意¶
签到。
题解¶
略。
I¶
solved by JLK
题意¶
给两个数组\(A,B\)，找到\(i\ne j,k\ne l,1\le i,j \le n,1 \le k,l \le m\)，使得\(|A_i-A_j|=|B_k-B_l|\)。
\(2 \le n,m \le 10^6,0 \le A_i,B_i \le 10^7\)
题解¶
去掉绝对值，钦点\(A_i\ge A_j,B_k \ge B_l\)（不满足就swap）。那么就有\(A_i+B_l=A_j+B_k\)。
首先排个序，然后看有没有重复。如果两边都有重复，那么直接输出。否则可以直接把重复元素只留一个。
值域只有\(2\times 10^7\)，那么枚举\(A_i+B_l\)最多枚举\(2\times 10^7\)次之后就会有相同的，有相同的直接输出即可。所以可以直接暴力枚举。
\(O(n \log n+2\times 10^7)\)
J¶
**upsolved by **
题意¶
题解¶
K¶
upsolved by TYB
题意¶
给一棵带点权和边权的树，找到\(k\)个点权不同的点，使得它们之间路径覆盖的边权和最大。
\(n\le 5000, 2\le k\le5\)
题解¶
感觉就是THUSC2017巧克力的改编，但这个套路比较少见，还是要记录一下的。
随机染色，为原来的每种颜色随机一个\([1,k]\)之间的颜色，然后再状压DP。
做一次找到一组解的概率为\(\frac{k!}{k^k}\)，做个几百次就行了。
记录¶
这次是2.5个人
开局TYB觉得H可做，讨论了一下直接冲，然后WA了一次。
JLK改了改式子，然后过了(0:18)。
然后看别的题，都不太会。讨论了一下F，感觉能写，JLK过F(1:41)。
L过了一堆人，但是不会，让YZW过来看了下题，然后会了，JLK过I(2:24)。
然后看E，感觉就是个流，但是想起来有点绕。TYB开始写，改了很多次。
TLE两次WA两次后发现题目有个小地方读错了，改对了就过了(4:33)。
然后就不玩了。
总结¶
Dirt¶
E(-4)
H(-1)