"蔚来杯"2022牛客暑期多校训练营8¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 24/1294 | 3 | 4 | 12 |
A¶
**upsolved by **
题意¶
题解¶
B¶
**upsolved by **
题意¶
题解¶
C¶
**upsolved by **
题意¶
题解¶
D¶
solved by JLK
题意¶
打牌题。
题解¶
状压记搜判断胜负即可。需要判断德扑牌型。
E¶
**upsolved by **
题意¶
题解¶
F¶
solved by JLK
题意¶
签到，略
题解¶
在第二个序列里，找每个在第一个序列里相同的位置即可。
G¶
upsolved by JLK
题意¶
有排列\(a\)和\(p\)，一开始\(a_i=p_i=i\)。
有一个排列的序列\(A\)，\(A_1=a\)，\(A_{i,j}=A_{i-1.p_j}\)。
有\(q\)次操作：
- 交换\(a_x\)和\(a_y\)
- 交换\(p_x\)和\(p_y\)
- 询问\(A_x\)和\(A_y\)哪个字典序大
\(1 \le n,q \le 10^5\)
题解¶
把\(i\rightarrow p_i\)连边，会形成若干个环。\(i\)每增加一次相当于整个环移动一次。
对于\(x,y\)，要比较它们的字典序，主要是看环。对于环长能够整除\((x-y)\)的环，显然在\(A_x,A_y\)当中都是相同的，可以直接忽略。
对于不能整除的，实际上只需要考虑下标最小的那个位置，因为比较的是字典序。找到最小的不同的下标，接下来就是要求这个下标在\(x\)和\(y\)时间的情况。
如果我们能求出这个下标在\(x\)步之后是原来的哪个下标，就只需要求出下标之后直接读\(a\)数组即可。因此交换\(a_x\)和\(a_y\)没什么影响。
也就是说，可以看做\(i\rightarrow p_i\)的连边情况下，走\(x-1\)步到达了哪个点。
考虑维护这个环的形态，交换\(p_x,p_y\)可能导致两个环结合，也可能导致一个环分裂。可以使用平衡树来维护。
具体来说，可以用splay，每个环是一个splay，按顺序存放环（相邻和首尾有边）。splay上维护区间最小下标以及size。
操作的时候需要分类讨论一下。
对于结合，可以把\(p_x,p_y\)分别移动到第一个（把前边的一段移到最后），然后把\(y\)所在整个splay接到\(x\)后面。
对于分裂，可以把\(p_y\)移动到第一个，把\([p_x,y]\)切下来单独成一个splay。
现在可以维护环，那么怎么找环呢？直接大力根号分治，环长小于根号的每个环长存个set，环长大的所有存在一个set里。询问的时候小的枚举环长，大的直接遍历。找到所有环里最小的下标，再到splay里去询问。
\(O(q\log n +q\sqrt n)\)
H¶
**upsolved by **
题意¶
题解¶
I¶
solved by TYB
题意¶
给出\(k\)个图\(G\)，每个图都是\(n\)个点，给出\(G_1\)的\(m\)条边，而对于\(G_i(i>1)\)，是从\(G_j(j<i)\)增加或删掉一条边得到的。将这些图按照连通性分成若干个集合，输出每个集合内的元素。两个图连通性相同当且仅当\(\forall i,j\in[1,n]\)，\(i,j\)在两个图的连通情况都一样。
\(n,m,k\le10^5\)
题解¶
建出操作树，每条边的存在区间在dfs序上是连续的若干段，总段数是\(\mathcal{O}(n)\)级别的。所以直接线段树分治解决动态图连通性问题即可。
J¶
**upsolved by **
题意¶
题解¶
K¶
**upsolved by **
题意¶
题解¶
L¶
**upsolved by **
题意¶
题解¶
记录¶
JLK过F(0:18)和D(1:04)。
TYB会了G，跟JLK讨论后觉得可行，但是太麻烦了先不写。
一起看J，感觉有思路，但是不好写。
然后看I，讨论了一下有点思路，JLK先开始写G。
TYB会了I，开始写I，然后TLE了。
JLK写完G，也是TLE了。
此时YZW说A可以搞，开始搞A，G和I在看代码。
到4:40的时候G和I改了一些错误，I过了(4:41)但G还是TLE。
A最后也搞不动了。
总结¶
TYB：提高代码能力，一些平常少用的东西也要保持熟练度，比如这次的splay，线段树分治。
Dirt¶
I(-2)