BUAA XCPC Team Supplementary Training 01¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 5/21 | 5 | 11 | 12 |
B¶
unsolved by Kotlin
题意¶
高精度 FFT 警告！
题解¶
狗都不写！
C¶
upsolved by JJLeo
题意¶
给出一棵树，和一些路径，选择尽可能少的点使得每条路径至少包含一个点。
题解¶
考虑将所有路径 lca 按深度排序，最深的那个路径肯定在上面选一个，因为它是所有 lca 中最深的，容易发现选 lca 一定比不选 lca 更优，选完后继续考虑其它路径，用树剖线段树维护每条路径上是否有点被选即可。
D¶
solved by 2sozx Bazoka13 JJLeo
题意¶
OO 电梯 Night 模式降智版。
电梯容量无限，如果电梯在一层不走那么来了人就会进去，第 \(i\) 个人 \(t_i\) 时刻到要去 \(a_i\) 层，保证 \(t_1,t_2,\cdots,t_n\) 升序。求送完所有人回到一层的最短时间，开门关门不花时间。(\(1 \le n \le 2 \times 10^5\))
题解¶
如果 \(a_i \le a_j\)，而 \(t_i \le t_j\)，则第 \(i\) 个人不如等第 \(j\) 个人一起走，因此先用单调栈处理使得 \(a_1,a_2,\cdots,a_m\) 降序。
设 \(f_i\) 为送完前 \(i\) 个人回到一层的最短时间，则有转移 \(f_i= \min \limits _{j<i}(\max(f_j,t_i)+2(a_{j+1}-1))\)，当 \(f_j>t_i\) 时，可以用单调队列维护，当 \(f_j \le t_i\) 时，因为 \(a\) 单减显然取大的 \(j\)，维护分界点即可，时间复杂度为 \(O(n)\)。
然而 zyf 前一天写了单调栈 + 线段树，结果写了两个小时的单调栈 + 线段树，而且还认为如果 \(f_j \ge t_{i+1}\) 则转移不成立因为第 \(i\) 个人此时必须和第 \(i+1\) 个人走，导致巨复杂无比，感觉都可以出新题了（x
其实并不需要考虑这点，因为令 \(a_1,a_2,\cdots,a_m\) 降序后如果能多带一个人走却不带必然会更劣，从而不需要考虑。脑瘫的 zyf 没有听从崔佬的意见先用单调栈处理，结果寄了。
E¶
upsolved by JJLeo
题意¶
给定一个 \(n\) 个点 \(m\) 条边的无环有向图，可能有重边，要求选出两个不相交的边集，分别组成节点 \(a\) 的叶向树和节点 \(b\) 的根向树，判断无解或输出方案。(\(2 \le n \le 5 \times 10^5\)，\(1 \le m \le 10^6\))
题解¶
这题是 Mike 出的，晦气
对于 \(a\) 的叶向树，除了 \(a\) 所有点入度都是 \(1\)；对于 \(b\) 的根向树，除了 \(b\) 所有点出度都是 \(1\)。
建立二分图，左侧 \(2n-2\) 个点，分别表示上述 \(2n-2\) 个点的入度或出度，右侧 \(m\) 条边，与可以贡献入度或出度对应的两个点连边，每选一条边就可以满足左侧的一个条件，因此相当于求这个图的最大匹配，dinic 可以在 \(O(m\sqrt n)\) 的复杂度内完成，而这题的范围竟然也能过，看起来跑不满（x
考虑这个二分图的特殊性，可以在更快的复杂度内完成。我们考虑让右侧所有点度数均为 \(2\)，现在因为 \(a,b\) 这两个点在作为根时分别不需要入度和出度，并不满足右侧所有点度数均为 \(2\)，我们可以强行让 \(a\) 的入度也是 \(1\)、\(b\) 的出度也是 \(1\)，并加入两条 \(b \to a\) 的边防止无解，输出方案时不要输出这两条边即可。
现在右侧所有点度数均为 \(2\)，考虑直接在左侧图中进行匹配，若右侧一个点与左侧点 \(x,y\) 连边，则在这两点之间连一条无向边。那么左侧点全部被匹配等价于在这个新图中每个点都可以选择一条与它相邻的边，且没有边被选了两次。
可以发现，对于左侧每个连通块，设其点数为 \(n\)，只要边数不为 \(n-1\)，也就是不是树，那就一定可以满足上述条件，考虑随便建出一个基环生成树，环外全部和父边匹配，环上绕一圈选上一条边匹配即可。
总时间复杂度为 \(O(n+m)\)。
F¶
solved by 2sozx Bazoka13 JJLeo
题意¶
CF364D 的加强版，给出一个序列 \(a_1,a_2,\cdots,a_n\)，删掉至多 \(k\) 个元素，剩下元素 \(\gcd\) 最大是多少。(\(2 \le n \le 10^5\)，\(0 \le k \le \dfrac{n}{2}\)，\(1 \le a_i \le 10^{18}\))
题解¶
首先介绍原题做法：
\(0 \le k \le \dfrac{n}{2}\) 从而一个元素最后不在答案中出现的概率不超过 \(\dfrac{1}{2}\)，随机选择一个元素假设其最终存在于最优方案中，则进行 \(b\) 次全部错误的概率低于 \(\dfrac{1}{2^b}\)。
设取的这个元素是 \(x\)，最终答案必然是 \(x\) 的因子，从大到小考虑每个因子 \(y\)，如果 \(\sum \limits _{i=1}^n[y \mid a_i] \ge n-k\)，那么 \(y\) 就是可行的。
那么随机一次的时间复杂度就是 \(O\big(n\sigma_0(x)\big)\)，\(\sigma_0(x)\) 是 \(x\) 的因数个数，原题数据范围是 \(1 \le n \le 10^6\)，\(1 \le a_i \le 10^{12}\)，随机 \(10\) 组，基本跑不满，因此可以通过。
然而按原题这个做法，随着 \(a_i\) 来到 \(10^{18}\)，\(\sigma_0(x)\) 可以达到 \(10^5\) 级别，如果 \(n\) 个数都是这个数，无论怎么随机连一次都跑不完。
然而数据比较弱，加一个熔断机制，快 T 了就退出，就过了。
正解是高维前缀和，考虑对 \(x\) 做质因子分解，每个质因数都是一维，从次数高遍历到次数低，这样可以在 \(O\big(\sigma_0(x)w(x)\big)\) 的时间内求出每个因子能整除多少个 \(a_i\)。其中 \(w(x)\) 是不同质因子个数，不超过 \(20\)，这样随机 \(10\) 次复杂度就是对的了。
G¶
solved by Bazoka13
题意¶
二分答案 + 差分约束，一些变量是定值。
题解¶
建立一个超级点 \(s\)，如果 \(x=a\) 是定值，连边 \(s \to x\) 边权 \(a\)，\(x \to s\) 边权 \(-a\)，就可以保证其最终答案一定是 \(a\)，否则更小就会产生负环，无解。
H¶
solved by 2sozx Bazoka13
题意¶
题解¶
I¶
upsolved by JJLeo
题意¶
给定一个长度为 \(n\) 的字符串，\(q\) 次询问，每次给定其中 \(k\) 个子串，问其 \(2^k\) 个有子集中有多少个满足，任意两个子串一个都不是另一个的前缀。(\(1 \le n,q,\sum k\le 4 \times 10^5\))
题解¶
将串翻转，条件改为任意两个子串一个都不是另一个的后缀。
建出 SAM，找到这些子串在 parent 树上的节点，建出虚树，即为不存在祖先关系的子集有多少个，进行简单的树形 dp 即可。注意如果多个子串属于同一个节点，也只能选一个，因此转移时方案数要乘以对应的数量。
总时间复杂度为 \(O\big((n+\sum k) \log n\big)\)。
J¶
upsolved by JJLeo
题意¶
给定一个长度为 \(n\) 的序列，给出定值 \(m\)，\(q\) 组询问，每次问 \([l_i,r_i]\) 这部分序列有多少个子序列模 \(m\) 是 \(0\)。(\(1 \le n,q \le 2 \times 10^5\)，\(1 \le m \le 20\))
题解¶
分治，设当时区间为 \([l,r]\)，处理跨过 \(\textit{mid}\) 的询问，\(O\big((r-l)m\big)\) 复杂度维护从中点往前往后模 \(m\) 为 \(i\) 的子序列方案数，对每个询问找到对应两个位置 \(O(m)\) 进行合并，剩下询问必然都分布在两侧，递归处理。
总时间复杂度为 \(O\big((n\log n + q)m\big)\)。
K¶
upsolved by JJLeo
题意¶
一个长度为 \(n\) 的文本串，再给出 \(m\) 个模式串，问每个模式串在文本串中最多不重叠出现了几次。
题解¶
直接 AC 自动机暴力匹配即可，和上一次匹配位置比较如果重叠了就跳过，否则就匹配，更新答案，显然正确。
时间复杂度利用经典结论为 \(O(n+m\sqrt m)\)。
L¶
upsolved by JJLeo
题意¶
给定一个连通带权无向图，问每条边是从 \(1\) 出发到达多少个点最短路的必经之路。
题解¶
首先建出最短路 DAG，连所有满足 \(d_x + w_{x,y} = d_y\) 的有向边 \(x \to y\)。
按拓扑序依次考虑每个点，如果一个点的入度 \(>1\)，显然这些边不会影响到任何点，因为封掉一条走另一条就好了。对于入度 \(=1\) 的点，指向它的这条边是有可能影响一些点的，下面考虑它能影响到哪些点。
如果目前所有点 (除了 \(1\) 号点) 入度均为 \(1\)，那显然形成了一个叶向树，能影响到的点显然就是对应的子树大小。如果出现了入度 \(>1\) 的点，就不是一个叶向树了，考虑哪些边会影响到这个点及接下来它指向的点，可以发现就是所有指向它的点的 lca 及其祖先所对应的边，因为所有在这之下的边都存在另一条路，从而将它放在 lca 下面即可，这样仍是一个一个叶向树，可以边插入便维护祖先的倍增数组以求 lca。
总时间复杂度为 \(O\big((n+m) \log n\big)\)。
记录¶
0h：逛了一圈，没找到签到题，心态大崩，看了看榜过了A，想了想A确实挺可写，ZYF直接冲了，给了两发过了，想了J的算法，然后开写
1h：CSK YY了一个H的做法，喂给MJX，MJX直接开冲，然后RE1了，大概是ci n,cout的flush问题，改了个fflush这样就可以WA2了，ZYF发现算法假了，抛弃J题。CSK发现H有个corner case，加了就过了。
2h：开始噩梦电梯，MJX、ZYF忘了CSK开始说的一个条件（最后CSK看代码才发现），开始乱冲，ZYF写了会直接自闭。CSK和MJX说G题，看起来就是个查分约束，CSK开冲了
3h：G过了，开始乱玩F，之前有个和F题一模一样的题，但是值域比这个小，就先延续之前的做法做，发现可以根据运行时间exit，一卡直接干到了4.30
4h：F调参没事干的时候ZYF继续改D，最后F过了后CSK看了眼代码然后改了一下就过了。