"蔚来杯"2022牛客暑期多校训练营9¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 22/1300 | 8 | 10 | 11 |
A¶
solved by JLK
题意¶
签到，略
题解¶
B¶
solved by JLK
题意¶
签到，略
题解¶
C¶
solved by TYB
题意¶
\(n\)个点\(m\)条边的有向图，边有边权，\((x,y,d)\)的含义是\(v_x-v_y=d\)，保证存在至少一种方案，去掉一条边后可以满足所有边的限制。求出能去掉哪些边。
\(n,m\le5\times10^5\)
题解¶
显然对于不合法的环，需要至少去掉一条边，对于合法的环，不能去掉上面的边。树上差分即可。
D¶
upsolved by JLK
题意¶
\(n \times m\)的矩阵，四联通，要用一条路径覆盖，并且要求拐点数是\(\frac{nm}{2}\)。
\(1 \le n,m \le 1000\)，都是偶数
题解¶
分类讨论构造题。
见题解。
E¶
solved by YZW
题意¶
题解¶
F¶
solved by JLK
题意¶
有一个\(n\times m\)的矩阵，数值是一个\(nm\)的排列，求每个连续子矩阵的gcd之和。
\(1 \le n,m \le 1000\)
题解¶
考虑每个数作为gcd的贡献。对于一个\(k\)，可以先求出\(k\mid gcd\)的矩阵数量，再容斥。
那么就把\(k\)的所有倍数拿出来，相当于是一个01矩阵，求全1的连续子矩阵数量。
感觉还是比较经典的，可以一行一行考虑，计算当前行作为子矩阵上边界的数量。先预处理出每个点向下有多少个1，然后用笛卡尔树的形式，从小到大分治计算经过当前点的贡献。那么一个点的贡献就是\((siz_l+1)\times (siz_r+1)\times cnt_1\)。
总的1数量相当于调和级数，而每次是线性的，所以总复杂度就是\(O(nm\log nm)\)。
G¶
solved by TYB
题意¶
给\(k\)个串，求有多少本质不同的回文串，同时是\(k\)个串的子串。
\(k\le5,\sum|S|\le3\times10^5\)
题解¶
PAM模板。
H¶
**upsolved by **
题意¶
题解¶
I¶
solved by YZW
题意¶
题解¶
J¶
upsolved by TYB
题意¶
给一张\(n\)个点\(n\)条边的连通无向图，每条边上有一些颜色可以选用，\(q\)次询问从\(a\)出发走一条简单路到\(b\)，初始颜色任意，每经过一条边就选边上的一个颜色刷成当前颜色，最大化颜色发生改变的次数。
\(n,q\le2\times10^5\)
题解¶
显然可以只考虑序列问题，基环树树剖倍增什么的都可以搞。
可以发现，在保证颜色改变次数最多的情况下，任意时刻状态只有两种：一是现在必须选择某种颜色，二是现在有多于一种颜色可以选择，而颜色具体是哪些并不重要。
对于一条边来说，经过它之后状态变化有如下几种情况：
1、经过一条只有一种颜色的边，那么当前颜色一定变为该颜色。
2、经过一条有两种颜色的边，那么有三种可能状态：颜色变为两种颜色之一，或者两种颜色都可以选。
3、经过一条多于两种颜色的边，那么一定有多于一种颜色可以选择。
所以对于每个区间，我们可以维护经过第一条边后，可能变成的状态、最后变成的状态，以及途中颜色改变的次数。
K¶
solved by TYB
题意¶
给\(n\)个\([0,2^k)\)的数，\(\forall i\in[0,2^k)\)，求出至少需要几个输入的数或起来得到。（和原题意不完全一样，但这是核心）
\(n\le10^5,k\le20\)
题解¶
做\(k\)次FWT即可。
记录¶
开局被TYB拉过去看E，感觉不是很好做。
JLK过A(0:08)。
TYB觉得G是板子题，开始写。
写完没过样例，换JLK先写B，JLK过B(0:33)。
TYB过G(0:38)。
一起看I，一开始感觉像之前那个凸包dp题，想决策单调。YZW想到一个单调栈做法，然后过了(1:10)。
JLK写F，WA一次后AC(2:16)。TYB和YZW玩E，搞半天还是进不了100个点。
看K，TYB觉得能写，WA一次后AC(2:54)。
YZW突然想到了E然后过了(3:21)。
然后看C，分析了一下性质感觉搞搞就行，TYB写完就过了(4:14)。
看起来还剩DJ比较可做，D看了一会没找出什么规律，J感觉可以写，但是有点复杂，没时间了。
总结¶
JLK：不要复用全局变量
Dirt¶
F(-1)
K(-1)