XVII Open Cup named after E.V. Pankratiev. Grand Prix of Moscow Workshops¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 26/188 | 9 | 11 | 11 |
A¶
solved by 2sozx Bazoka13 JJLeo
题意¶
给定一颗树，判断是不是点分树。
题解¶
考虑点分树的根节点一定是整棵树的重心，至多有两个，可以分别将其设为根进行检验。
点分树的根节点确定后，所有节点都是当前子树的重心，对于每个节点必须满足最大子树不超过该子树的一半，dfs 检验一下即可。
B¶
solved by 2sozx
题意¶
给定 \(n=10^6\)，构造一个完全积性函数，满足所有质数处点值 \(f(p)=\pm1\) ，且 \(\max \limits_{i = 1}^n|\sum\limits_{j = 1}^i f(j)| \le 20\) 。
题解¶
一顿乱猜，考虑每个质数大概可能的贡献，最后得出： $$ f(p) = \begin{cases} 1,& p \bmod 6 = 1 \land p \ne 37 \newline -1 ,&\text{otherwise} \end{cases} $$
C¶
upsolved by 2sozx JJLeo
题意¶
给定一个 \(n\) 个点 \(m\) 条边的无向连通图，边权为 \(1\)，问有多少无序点对 \((u,v)\) 满足两者之间所有基本路径长度均为奇数/偶数。(\(1 \le n,m \le 2 \times 10^5\))
题解¶
首先有结论：一个点双如果是二分图，那么它所有点对之间路径的奇偶性都是确定的；否则，所有点对之间的路径既有奇也有偶。感性证明：
如果是二分图，所有环都是偶环，不同路径不会改变奇偶性；反之，对于任意两点，以及任意一个奇环，必然有到奇环上不同两点的两条不相交路径，否则必然会出现割点，从而利用这个奇环就可以构造出奇偶性不同的基本路径。
首先建出圆方树，把每条边分到对应的点双里，这个可以以圆点为根 dfs 圆方树，两个圆点之间的边必然属于中间的方点对应的点双，可以维护每个点的父亲节点进行求解。
接下来 dfs 每个点双对应的原图，判断是不是二分图，如果不是二分图，删掉该点双对应的方点及相连的边。
然后圆方树变成了圆方森林，在圆方森林中 dfs 每个连通块，再将每个连通块的所有点在原图上跑出一棵生成树，此时这个连通子图是一个二分图，从而利用深度为奇数点的个数和深度为偶数点的个数就可以算出来有多少点对为奇数/偶数。
时间复杂度为 \(O(n)\)。
D¶
solved by JJLeo
题意¶
给定 \(n\) 个数 \(a_1,a_2,\cdots,a_n\)，将其分为任意段，每段长度必须为 \([L,R]\)，每个数必须恰好属于一段。
对于一段数 \(a_l,a_{l+1},\cdots, a_r\)，它的权值为 \(\operatorname{sgn}\left(\sum \limits _{i=l}^r a_i\right)\)，最大化所有段权值之和，或判断无解。(\(1 \le L \le R \le n \le 3 \times 10^5\))
题解¶
设 \(f_i\) 为将前 \(i\) 个数分段后的最大权值和，注意到 \(\operatorname{sgn}\left(\sum \limits _{i=l}^r a_i\right) \in \{-1,0,1\}\)，从而 \(f_i\) 只可能从满足下列条件 \(j\) 对应的 \(f_j\) 转移过来： $$ \begin{cases} i - L \le j \le i - R \newline f_j\ge\max \limits _{k=i-L}^{i-R} f_k-1 \end{cases} $$ 只需维护 \(j \in [i-L,i-R]\) 中 \(f_j = x\) 的前缀和最小值，然后转移时只需从 \(f_j=\max \limits _{k=i-L}^{i-R} f_k\) 和 \(f_j=\max \limits _{k=i-L}^{i-R} f_k-1\) 两个值的所有位置中前缀和最小值的位置转移过来即可，增加段的权值即为当前前缀和减去对应的最小值，上述过程可以通过开数个 multiset 维护，时间复杂度为 \(O(n \log n)\)。
E¶
upsolved by JJLeo
题意¶
直线上有 \(n\) 个位置，第 \(i\) 个位置的弹跳值为 \(a_i\)，可以跳到 \([i-a_i,i+a_i]\) 的任意位置，但所处位置必须为整数且在 \([1,n]\) 范围内。定义两个位置 \((i,j)\) 之间的距离为下述两者的最小值：
- \(i\) 跳到 \(j\) 所需步数的最小值和 \(j\) 跳到 \(i\) 所需步数最小值。
现在求任意两个位置之间距离的最大值。(\(1 \le n \le 2 \times 10^5\))
题解¶
显然，从一个位置跳固定步数所能到达的位置组成一个连续的区间。
设 \(l_{i,j}\) 和 \(r_{i,j}\) 分别为从位置 \(i\) 跳 \(2^j\) 步能达到的区间范围，转移为：
那么可以使用倍增 + 线段树维护，时间复杂度为 \(O(n \log ^2 n)\)。
接下来，我们去求解最大的步数，满足存在两个位置使得它们都无法在该步数跳到另一位置，那么最终答案就是该步数 \(+1\)。可以从二进制从高位到低位枚举，维护每个位置能跳到的左右范围 \(L_i\) 和 \(R_i\)，如果这一位是 \(1\)，那么使用类似上面的转移扩大每个位置能跳到的范围，如果存在两个位置不能互相到达，必存在 \(i\) 满足 \(L_i > \min \limits _{j=1} ^{i-1} R_j\)，这可以遍历过程中维护一个 \(R_i\) 前缀最小值来完成。若存在，则这一位为 \(1\)，更新每个点的范围；否则这一位为 \(0\)，保留每个点的范围。这一部分时间复杂度为 \(O(n \log n)\)。
综上，总时间复杂度为 \(O(n \log ^2 n)\)。
F¶
solved by JJLeo
题意¶
两个 \(01\) 串初始均为空，\(m\) 次操作，每次操作往其中一个加一个字符，每次操作后问两者最长公共子串的长度，强制在线。(\(1 \le m \le 5 \times 10^6\))
题解¶
对这两个串建广义 SAM，动态添加，每次加点后跳 fail 树将所有点标记上对应串的标记，一个点如果被该串之前都标记了就不跳了，所有被两个点标记的点对应的 len 可以贡献到答案中，这样相当于每个串只会跳自己在 SAM 的部分，总时间复杂度为 \(O(m)\)。
H¶
solved by 2sozx Bazok13 JJLeo
题意¶
交互题，二维平面上 \(n\) 个不同的目标点，均为坐标绝对值不超过 \({10}^6\) 的整点。每次可以询问三个整数 \(x,y,R\)，返回以 \((x,y)\) 为圆心，半径为 \(R\) 的圆内有多少个目标点。你需要询问不超过 \(15000\) 次找到所有目标点。(\(1 \le n \le 100\)，\(0 \le |x|,|y| \le 10^6\)，\(0 \le R \le 10^{18}\))
题解¶
首先选一个点，类似线段树 build 过程二分出所有点到这个点的距离，这个过程的询问次数即为动态开 \(n\) 个点线段树的点数，约为 \(O(n \log R)\)。我们再选一个点，也问上述信息，这样我们就确定了以两个不同点为圆心的各 \(n\) 个圆。
两个圆心不同的圆至多有两个交点，我们可以通过枚举任意两个圆间的交点找到所有可能的目标点，然后询问该点令 \(R=0\) 进行判断，但是这样有至多 \(2n^2\) 种可能，直接暴力询问会超过限制次数。可以发现两个圆如果不是对应一个点，那么它们交点是整点的概率是很小的，因此如果只有在整点处才进行询问，实际的询问量约为 \(O(n)\)。
总询问次数约为 \(O(2n \log R + n)\)，不超过题目给出的 \(15000\) 次。
I¶
solved by 2sozx JJLeo
题意¶
长度为 \(n\) 的序列，一开始均为 \(2^{31}-1\)。\(q\) 次操作，每次修改一个值，之后需要输出全局最小值。输入数据使用伪随机数算法给出。(\(1 \le n \le 10^7\)，\(1 \le q \le 5 \times 10^7\))
题解¶
考虑每新增加一个数就用它和全局最小值取 \(\min\)，如果把全局最小值对应的数改了，就再去把整个序列扫一遍。在数据随机的情况下后者出现的概率几乎为 \(0\)，因此总时间复杂度即为 \(O(q)\)。
J¶
solved by Bazoka13
题意¶
给定一个边长为 \(1\) 的正 \(n\) 边形，用一个正 \(m\) 边形覆盖它，求正 \(m\) 边形的最小边长。(\(3\leq n,m\leq 10^5\))
题解¶
假设有 \(k\ge2\)，如果 \(n=km\) ，只需要令中心到二者的边距离相等即可，并且正 \(n\) 边形中必然有 \(m\) 条边在正 \(m\) 边形上，如果 \(m=kn\) ，则令二者外切圆半径相同。
对于一般情况，参考上面的情况，可以在二者之间塞一个 \(\operatorname{lcm}(m,n)\) 边形，使它和正 \(n\) 边形外切圆半径相等，和正 \(m\) 边形中心-边缘距离相等。
之后画图可得答案为 \(\dfrac{\cos\left(\dfrac{\pi}{\operatorname{lcm}(n,m)}\right)\tan\left(\dfrac{\pi}{m}\right)}{\sin\left(\dfrac{\pi}{n}\right)}\)
证明：反过来考虑在正 \(m\) 边形里塞一个最大的正 \(n\) 边形。按照上述规则构造好后，绕中心旋转正 \(n\) 边形，如果当前正 \(n\) 边形部位最大，那必存在某个位置，使得正 \(n\) 边形所有顶点都在多边形内部。
我们可以把正 \(\operatorname{lcm}(m,n)\) 边形视作 \(m\) 段 \(\dfrac{n}{\gcd(m,n)}\) 个点或者 \(n\) 段 \(\dfrac{m}{\gcd(m,n)}\) 个点，不难证明我们从任意 \(i\in[0,\dfrac{n}{\gcd(m,n)}-1]\) 出发，每次移动 \(\dfrac{m}{\gcd(m,n)}\) ，总能到达 \(m\) 段中某个段的起点与终点，即无论怎么旋转正 \(n\) 边形，总会有顶点位于正 \(m\) 边形外或者边上，与假设不符。
记录¶
久违的记录回来了
假期第一场训练
0min：分题，CSK冲G
12min：CSK 少考虑情况WA1后AC, ZYF冲K
21min：ZYF AC,MJX 去乱搞B
83min：MJX 突然想出了I，ZYF冲I，数组开小RE1，后AC
102min：CSK AC J，MJX 奇奇怪怪的构造出了B冲B
104min：B读题错误导致输入遗漏PE3，后AC
204min：ZYF AC D
221min：判断时少判断点+测试测评机导致PE10 WA1 T1，后AC
?min：CSK 盲猜A题题意MJX冲
243min：MJX 点分树挂了WA1,ZYF改写法后AC
259min：ZYF发现F是模板AC
till end：想到了C的大概写法，但是没AC
after end：C细节很多