"蔚来杯"2022牛客暑期多校训练营（加赛）¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 27/1208 | 6 | 11 | 13 |
A¶
**upsolved by **
题意¶
题解¶
B¶
upsolved by JLK
题意¶
\(n\)个点的基环内向森林，每个点有一个人，每个人每秒钟走到当前点指向的那个点。问每个点上至少有\(k\)个人的最早时间。
\(2 \le k,n \le 10^6\)。
题解¶
每个基环内向树单独考虑。
首先对于树的部分很简单，用长链剖分维护一下即可。合并的时候更新答案，并且当前点的答案可以以1的代价往上推（\(ans_{a_x}=\min\{ans_{a_x},ans_x+1\}\)）。
对于环，环上的人在循环运动，并且对于每个人来说和他同行的人数会越来越多。
考虑环上的点的子树对环上的贡献。可以把点和人对应，用一开始在环上的点的人来代表某个时刻在环上某个点的一群人。把环外的人走到环上看做合并到环上的某个人。对于环外的每个人都可以求出他会合并到环上的哪个人。
按合并时间扫，不断把环外的人合并进去，那么环上的人的个数递增。每次合并之后判断是否达到条件，如果达到条件就把当前在的点的答案更新。
这样相当于把环上每个人群第一次达到条件的点更新了。最后在环上按顺序扫两遍，把答案更新一下（和树上往上推的过程差不多）。扫两遍就可以保证所有点都更新到了。
\(O(n)\)
C¶
solved by TYB
题意¶
长度\(n\)的字符串，\(q\)次询问，每次询问右端点在\([l,r]\)区间的串中本质不同的串有多少。
\(n,q\le5\times10^5\)
题解¶
对于每个位置来说，有贡献的节点是parent tree上该点到根路径上的所有点，那么每次询问就相当于问若干条链并的权值和，可以参照区间本质不同子串个数的做法，用LCT/树剖解决。
D¶
upsolved by JLK
题意¶
有环上逆时针排列的\(n\)个点，不知道具体位置，只知道相对关系（东、西、未知）。
给定相对关系的矩阵，求把未知的关系填上的方案数。
\(1 \le n \le 500\)
题解¶
可以固定1号点，然后把剩下的点分成两部分，全部在1号点的西边或者全部在1号点的东边。每一部分是一段连续的点。
如果固定了这两部分点，每一部分内部的相对关系是确定的，要保证不能冲突。然后就是要确定两部分之间的相对关系。
两部分之间的相对关系，可以把一部分全部转180°，转化成比较先后关系。
因此，一部分（A）正着枚举，一部分（B）倒着枚举。由于两部分内部的先后关系是确定的，相当于不断把两个有序序列往一个序列里归并。每次填数的时候要保证一个前缀和后缀的相对关系。
可以dp解决，\(dp_{i,j}\)表示\(A\)的前\(i\)个点，\(B\)的后\(j\)个点填完了的方案数。处理一个前缀和就可以\(O(1)\)转移。
需要注意方位判断的细节。
\(O(n^3)\)
E¶
solved by JLK
题意¶
签到，略
题解¶
F¶
upsolved by TYB
题意¶
\(P\times Q\)的二维平面，有\(n\)个怪兽，第\(i\)个怪兽的坐标为\((x_i,y_i)\)，血量为\(h_i\)，分数为\(v_i\)。\(m\)次操作，分为三种：
1、\(\forall i\in[1,n],x_i\in[l,r],h_i-=1\)；
2、\(\forall i\in[1,n],y_i\in[l,r],h_i-=1\)；
3、新增加一个怪兽。
若某个怪兽\(h\)变为\(0\)，则获得其分数，且该怪兽永久消失，每次操作后输出当前分数。
强制在线。
\(P,Q,n,m\le10^5\)
题解¶
如果\(h\)比较小，可以用两棵线段树维护，在每个怪兽\(h\)发生变化时，暴力修改这个怪兽在另一棵线段树的值。
仿照这个思路，有一个巧妙的做法：若一个怪兽血量为\(h\)，把血量为\(\lceil\frac{h}{2}\rceil\)的怪兽放进两棵线段树，当血量变成\(0\)的时候再暴力重构。这样重构的次数就是\(\log h\)的。
G¶
upsolved by JLK
题意¶
给定一个r,e,d,?组成的字符串，问是否能把每个?填成三种字母的一种，使得整个串可以划分成若干个red的子序列。
\(|s| \le 3\times 10^5,3\mid|s|\)
题解¶
对于一个没有?的串来说，合法的条件是，每个前缀有\(cnt_r\ge cnt_e\ge cnt_d\)且每个后缀有\(cnt_r\le cnt_e\le cnt_d\)。
由于整个串要满足\(cnt_r=cnt_e=cnt_d\)，所以前缀的\(cnt_e\ge cnt_d\)等价于后缀的\(cnt_e \le cnt_d\)，后缀的\(cnt_r \le cnt_e\)等价于前缀的\(cnt_r \ge cnt_e\)。
只需要保证前缀的\(cnt_e\ge cnt_d\)和后缀的\(cnt_r \le cnt_e\)即可。
以前缀为例。当\(cnt_d \gt cnt_e\)的时候，就需要把前面的一个?改成e。贪心地去填，肯定是选最后一个填e，因为前面的?可能要改成r。可以用一个栈维护。后缀同理。
这样贪心实际上是尽量避免冲突的。
剩下的?按red次序填即可。最后再check一下。
\(O(|s|)\)
H¶
solved by YZW
题意¶
题解¶
I¶
**upsolved by **
题意¶
题解¶
J¶
solved by YZW
题意¶
题解¶
K¶
solved by JLK
题意¶
给\(n,m,k\)，构造一个\(n \times m\)的01矩阵，使得1的个数是\(k\)，并且每行每列都有奇数个1。
\(1 \le n,m,k \le 10^5\)
题解¶
几个比较显然的性质：
- \(n,m,k\)奇偶性一定要相同
- \(\max\{n,m\}\le k \le nm\)
直接构造比较难搞，考虑先搞成方阵。
不妨设\(n \lt m\)，每次可以减少两列，只要两列相同并且是奇数个1即可。
而且在剩下的矩阵满足\(\max\{n,m-2\}\le k'\)的情况下，这两列填越多越好。因为当\(k=\max\{n,m\}\)的时候构造方案很显然（一个对角线+一条横/竖即可）。
然后现在变成了方阵。每次减少两行两列，仍然是填越多越好。1填的数量应该满足\(2 \le cnt \le 4n-4\)。而当\(cnt\)接近上界的时候有几个值无法构造，需要适当减少一些。
加上无解的判断和最后一步的构造，递归即可。
L¶
upsolved by TYB
题意¶
\(n\)个数，范围是\([0,n]\)，\(i\)的个数为\(a_i\)，设这些数的共\(\frac{n!}{\prod_{i=0}^n a_i!}\)种排列组成的集合为\(A\)，求\(\sum b\in A\sum_{1\le l\le r\le n}f(l,r)\)，其中\(f(l,r)=mex(b_l,\dots,b_r)\)。
\(n\le10^5\)
题解¶
首先把\(mex=k\)转化为\(\sum[mex\ge k]\)，更好计数。
考虑计算长度为\(L\)，\(mex\ge k\)的连续段的贡献，显然任意连续\(L\)个数都是等价的，不妨考虑前\(L\)个数的连续段，最后再乘\(n-L+1\)的系数。
设\(i\)有\(b_i\)个在前\(L\)个数，有\(c_i(a_i=b_i+c_i)\)在后\(n-L\)个数，那么贡献为\(\frac{L!}{\prod_{i=0}^nb_i!}\frac{(n-L)!}{\prod_{i=0}^nc_i!}\)。
若不考虑\(mex\ge k\)，则显然可以生成函数解决，设\(g_i(x)=\sum_{j=0}^{a_i}\frac{x^j}{j!(a_i-j)!}\)，那么\([x^L]\frac{\prod_{i=0}^ng_i(x)}{L!(n-L)!}\)就是长度为\(L\)连续段的贡献。
若要求\(mex\ge k\)，也就是\([0,k)\)这些数一定在前\(L\)个数中出现，可以令\(f_i(x)=g_i(x)-\frac{1}{a_i!}\)，也就是必须选择\(i\)这个数。
所以我们最终要求的是\(\sum_{k=1}^{n}\prod_{i=0}^{k-1}f_i(x)\prod_{j=k}^{n}g_i(x)\)。
可以分治NTT解决。
M¶
solved by YZW
题意¶
题解¶
记录¶
YZW过M(0:06)和H(0:17)。
一起看E，但是题意比较难懂。后来JLK感觉了一发就冲过去了(0:41)。
TYB开始写C。JLK和YZW看GJ。YZW想了个J的做法。
C过了(1:58)之后YZW过了J(2:15)。
YZW想到A一个log的写法，不敢写。
G感觉不太好搞，JLK试了一下，WA了。后来找到了hack数据，没法修。
换题，搞K。JLK想了个方法，WA了。发现有几种情况处理不了。TYB改进了一下方法，RE一次之后过了(4:48)。
TYB推出了L的式子，但是没时间了。
总结¶
JLK：F**k 构造
TYB：像GK这种题目可以现在本地跑一下小数据，减少罚时。
Dirt¶
K(-2)