"蔚来杯"2022牛客暑期多校训练营6¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 31/1456 | 7 | 10 | 13 |
A¶
solved by JLK
题意¶
有一个长度为\(n\)的数组\(a\)，满足\(\sum \frac {1}{a_i} \le \frac {1}{2}\)。要求构造一个长度为\(m\)的数组\(c\)，使得无限扩展\(c\)之后，每相邻\(a_i\)个数至少有一个\(i\)出现。
\(m\)自选。
\(1 \le n \le 10^5\)。
题解¶
一种想法是按\(a_i\)从小到大，每\(a_i\)个数放一个\(i\)，但是这样有些位置会产生冲突。考虑如何充分利用条件。
令\(a_i'=2^{\lfloor \log _2 a_i\rfloor}\)，有\(\frac {a_i}{2}\lt a_i' \le a_i\)。相当于要求更严格，满足新的\(a_i'\)即可。
\(\sum\frac{1}{a_i'} \le \sum\frac{2}{a_i} \le 1\)
即\(\sum\frac{m}{a_i'} \le m\)
令\(m\)是一个比较大的\(2\)的幂次即可，如\(2^{19}\)。然后就可以直接按\(a_i'\)填了。
这样为什么一定不会冲突？考虑一个\(a_i=2^k\)。如果他没有位置放了，说明前面至少有\(k\)个\(2^k\)（小于\(2^k\)的数可以拆成若干个\(2^k\)），再加上这个数就超过限制了，所以不可能出现这种情况。
B¶
solved by JLK
题意¶
签到，略
题解¶
C¶
solved by TYB
题意¶
给出一个\(n\)个点\(m\)条带权边的无向图，求其所有生成子图最小生成森林的边权和。
\(n\le16,m\le100\)
题解¶
考虑每条边\((x,y)\)的贡献，显然只需要得知用边权比它小的边没有使\(x,y\)连通的方案数。
令\(f_S\)表示只考虑两端点都在\(S\)内的边，且使\(S\)这个集合连通的方案数。那么只需要枚举一个包含\(x,y\)的集合\(S\)，再统计出两端点都在\(S\)补集中的边的数量，即可计算该边的贡献。
考虑怎么求\(f\)，显然可以枚举子集，这样是\(\mathcal{O}(m3^n)\)的；可以用子集卷积优化到\(\mathcal{O}(mn^22^n)\)。
D¶
upsolved by TYB
题意¶
\([1,n]\)内有多少个数满足有偶数个质因子，且个数最多的质因子不超过总数的一半。
\(n\le10^{11}\)
题解¶
显然可以往min25筛的方向思考。
常规的min25筛，\(S(n,m)\)表示的是范围在\([1,n]\)，且最小质因子\(\ge prime_m\)的数的答案。这题可以魔改一下，\(S(n,m,sum,mx)\)表示范围在\([1,n]\)，最大质因子\(\ge prime_m\)，且现在选了\(sum\)个数，个数最多为\(mx\)的答案。可以发现，我们只是额外记录了这两个信息，对复杂度没有影响。
E¶
upsolved by TYB
题意¶
给一个\(n\times n\)的矩阵\(a\)，每次操作选择\((x,y,v)\)，将第\(x\)行所有数\(+v\)，第\(y\)列所有数\(-v\)，在\(2n-2\)次操作内将矩阵所有数变为非负或判断无解。
\(n\le501\)
题解¶
先考虑一个必要条件：对于所有排列\(p\)，\(\sum a_{i,p_i}\ge0\)，因为操作不会改变这个值。
实际上这也是充分条件，下面给出一种构造。
首先KM找出最小的\(\sum a_{i,p_i}\)，不妨设\(p_i=i\)。
首先用\(n-1\)次操作使\(a_{i,i}=0,i\in[1,n)\)，那么\(a_{n,n}\ge0\)。
此时，不妨将第\(n\)行的数全部减去\(a_{n,n}\)（但不实际操作，即不会用掉操作次数），只要这种情况有解那么原来也一定有解。
如果我们只对\((i,i)\)操作，不妨设参数为\(v_i\)，那么对于\((i,j),i\neq j\)，需要满足\(a_{i,j}+v_i-v_j\ge0\)，容易发现这是一个最短路的形式，只需要令\(v_i\)为\(1\sim i\)的最短路即可。但看上去这一步需要\(n\)次操作，不符合要求。但我们发现，若\(v_i\ge0\)，可以不对\((i,i)\)进行操作，实际上，\(v_1\ge 0\)一定成立，即不存在负环。可以证明，若存在负环，则\(\sum a_{i,i}\ge0\)不成立。故第二步只需要对\(i\in[2,n]\)操作，也是\(n-1\)步。
F¶
upsolved by JLK
题意¶
定义一棵以\(1\)为根的树\(T\)的哈希函数为\(F(T)=(\sum\limits_{i=1}^n\sum\limits_{j=i+1}^{n}X^iY^jZ^{lca(i,j)})\mod P,P=998244353\)。
给定\(F(T),X,Y,Z\)，构造一个至多为\(50\)个点的树，使得满足哈希值等于给定的\(F(T)\)。
\(0 \le F(T) \lt P,2 \le X,Y,Z \le P-2\)
题解¶
一眼meet in the middle。可以让\(1\)只有两个儿子，确定好所有点归属哪棵子树，先枚举第一个儿子的子树形态，用第二个儿子的子树去撞。整棵树的哈希值可以分为，两个子树内的哈希值，两个子树之间的哈希值，和所有点到\(1\)的哈希值之和。
由于一开始确定好所有点归属哪棵子树，后面两个是确定的，只需要算两个子树内的哈希值。
但是枚举所有树的复杂度太大。
考虑随机。一开始随便把所有点分成两份，然后在两份里面不断随机连成两棵树。
第一棵树随机\(\sqrt P\)次存起来，第二棵树也随机\(\sqrt P\)次之后，就有挺大概率能撞上。
算子树内部哈希值的时候需要用到常数比较小的\(O(n^2)\)做法。一种方法是，只记录每个点的父亲，然后从小到大枚举点，每个点可以把贡献累加到所有祖先上，为了不算重复需要差分一下，即\(a\)在\(b\)处的贡献为\(X^aZ^b-X^aZ^{father_b}\)。这样后面的点\(c\)可以直接枚举所有祖先，算出和前面的点的贡献\(\sum Y^csum_b\)。
每个点先算自己作为大的点贡献，再把自己作为小的点的贡献加入所有祖先即可。
复杂度大概是\(O(\sqrt P n^2)\)。
G¶
solved by YZW
题意¶
题解¶
H¶
**upsolved by **
题意¶
题解¶
I¶
solved by YZW
题意¶
题解¶
J¶
solved by YZW
题意¶
题解¶
K¶
**upsolved by **
题意¶
题解¶
L¶
**upsolved by **
题意¶
题解¶
M¶
solved by TYB
题意¶
签到。
题解¶
略。
记录¶
JLK过B(0:09)。
YZW过G(0:18)。
TYB过M(0:29)。
YZW过J(0:33)。
一起看A，没什么思路。JLK猜了个做法然后WA了。
TYB开始写C。
YZW搞出来一个A的正确做法，JLK改了一下过了(2:12)。
C TLE了，怀疑是复杂度不对，在想优化。
JLK尝试卡了卡常，然后过了(3:01)。
YZW写I，WA了几次，看不出哪里有问题。
TYB写D，WA了，后来才发现题意有问题。
最后乱试I，突然就过了(4:57)。
总结¶
JLK：数据范围小的题可以多想想随机化。感觉完全没往这方面想。
TYB：常数真是太重要了！
Dirt¶
A(-1)
C(-1)
I(-8)