- XXII Open Cup: GP of Dolgoprudny
- XXII Open Cup: GP of IMO
- XXII Open Cup: GP of XiAn
- XXII Open Cup: GP of Korea
- XXII Open Cup: GP of Siberia
- XXII Open Cup: GP of EDG
- XXII Open Cup: GP of Southeastern Europe
- XXII Open Cup: GP of Poland
- XXII Open Cup: GP of Nanjing
- XXII Open Cup: GP of Kyoto
- XXII Open Cup: GP of Daejeon
- XXII Open Cup: GP of Grushevka
- XXII Open Cup: GP of Gomel
- XXII Open Cup: GP of BSUIR
- XXII Open Cup: GP of Yuquan
- XXII Open Cup: GP of Urals
[TOC]
XXII Open Cup: GP of Dolgoprudny
XXII Open Cup: GP of IMO
B
简要题意.
给定 \(k,w,n\)，维护大小为 \(n\) 的集合 \(S\)。
\(q\) 次操作，每次修改 \(S\) 中一个元素，然后令 \(S\) 排序后为 \(s_1,s_2,\dots,s_n\)，询问 \[ \sum_{i=1}^n \left\lfloor\frac{s_i \cdot i^k}w\right\rfloor \]\(n,q,s_i \le 10^5\)，\(k,w \le 5\)。
整除并不好做，拆成 \(s_i \cdot i^k\) 和 \((s_i \cdot i^k) \bmod w\)。
前者用二项式定理合并，后者在线段树上维护大小为 \(\Theta(w^2)\) 的数组即可。
C
简要题意.
多组数据。
给定 \(n,l\) 和大小为 \(n\) 的下标集合 \(S\)，表示有一个长为 \(l\)，字符集无限大的字符串，对于 \(i\in S\) 都满足前缀 \(i\) 是回文串，问这个字符串的所有回文前缀的个数的最小值。\(\sum n\le 3\times 10^5\)，\(l\le 10^{18}\)。
dengls 和 duls 在这道题上 \(-13\)。
题解 \(7\) 页。
摸了。
D
简要题意.
给定偶数 \(n\)，你需要对数组 \([1,2,\dots,n]\) 做 \(\frac n2\) 次删除相邻元素 \(i,j\) 的操作。
操作每对 \(i,j\) 具有代价 \(\operatorname{cost}(i,j)\)，请最小化所有操作中代价的最大值。\(n\le 4000\)。
首先有个 \(\Theta(n^3)\) 的区间 DP。
然后按照值的大小做主动转移可以规避没用的比较，利用 bitset 可以做到 \(\Theta(\frac{n^3}w)\)。
I
简要题意.
给出 \(n\) 个矩形，问有多少三元组两两不相交。
\(n\le 2\times 10^5\)，保证矩形两两边界不会重合。
通过原图的三元环和各点度数可以得到补图的三元环个数。
扫描线，度数很容易计算，因为不交的线段数是容易计算的。
同时注意到三个矩形两两相交等价于全部相交。
我们不妨利用交集的最右端元素来去重，即对于每个 \(i\) 算出 \(i\in[l,r]\) 和 \(i\in[l,r)\) 的 \([l,r]\) 个数然后维护其 \(\binom{\cdot}3\) 之和即可。
J
简要题意.
对于 \(n\) 阶排列 \(p,q\)，称一个 \(2n\) 阶排列 \(r\) 合法当且仅当：
- \(r_1,r_2,\dots,r_n\) 离散化后等于 \(p\)。
- \(r_{n+1},r_{n+2},\dots,r_{2n}\) 离散化后等于 \(q\)。
记 01 串 \(s\)，其中 \(s_i = [r_i < r_{n+i}]\)，令 \(f(p,q)\) 为所有合法的 \(r\) 生成的本质不同的 \(s\) 的个数。
给定 \(p\) 和含空位的 \(q\)，求所有 \(q\) 的 \(f(p,q)\) 之和，对 \(998244353\) 取模。\(n \le 100\)。
注意到我们可以把问题变成 \(p=[1,2,\dots,n]\) 的情况，问题得以简化。
接下来证明 \(f([1,2,\dots,n],q)\) 就是 \(q\) 的上升子序列个数。
考虑对于 \(s\) 判断是否有方案。将所有小于关系连边，判断是否有环即可。同时可以发现如果有环，一定有长为 \(4\) 的环。
考虑通过 \(q\) 构造合法的 \(s\)：按照元素从大到小考虑对应位置是 \(\texttt 0\) 还是 \(\texttt 1\)，如果是 \(\texttt 0\) 则可以直接删除该位置而无影响；否则要删去一整个后缀。
将第二类操作对应上升子序列的元素，从而将 \(q\) 删空的方案数就是 \(q\) 的上升子序列个数。
这样考虑确定的元素中包含在上升子序列中的部分，然后直接 DP 就行了。
K
简要题意.
\(T\) 组数据。
给定 \(K\)，构造长度不超过 \(30\)，元素在 \([-10^{16},10^{16}]\) 内的序列 \(A\) 使得恰好有 \(K\) 个子序列的和为 \(0\)。\(T \le 1000\)，\(K \le 10^6\)。
智慧题。
标算给出了这样一个做法：对于已有的元素非零且和非零的集合 \(S\)，其零和子集数为 \(K\)，正数和负数之和分别为 \(P,N\)，不失一般性，假设 \(P>-N\)。
考虑加入若干 \(P\) 的非零倍数，则新的集合的零和子集个数要么是 \(K\) 乘新元素中的零和子集个数，或是新元素中和为 \(-P\) 的子集个数。
因此我们将这些元素除以 \(-P\)，那么实际上就是加入了若干小元素，考虑其和为 \(0,1\) 的子集个数即可。
我们考虑生成若干个固定的 Pattern 用来构造，根据测试，通过 \(\{-3,-2,-1,1,2,3\}\) 生成的大小不超过 \(10\) 的所有集合已经足够满足题目限制。于是 DP 即可。
L
学车人之前给搬模拟赛里了，不想再做第二次。
XXII Open Cup: GP of XiAn
F
简要题意.
给定 \(a,b,c,d,e,f\)，令 \(E = \{(x,y)\mid x,y\in \mathbb Z \land a(x-b)^2+c(y-d)^2+e(x-b)(y-d)\le f\}\)，求 \[ \sum_{(x,y)\in E} (x\oplus y)^{33} x^{-2} y^{-1} \] 模 \(10^9+7\)。
\(1 \le a,c \le 100\)，\(|e| \le 100\)，\(1 \le b,d \le 4\times 10^6\)，\(0\le f\le 10^{15}\)。
保证 \(\forall (x,y)\in E, 0 < x,y < 4 \times 10^6\)。
令 \(n = \max_{(x,y)\in E} \max\{x,y\}\)。
考虑一个 \(\Theta(n\log^2 n)\) 做法。以边长为 \(2^n\) 的正方形对平面进行四分，当当前正方形完全在椭圆内部时做一次 FWT 并返回。
由于椭圆的性质，得到的块的边长之和是 \(\Theta(n\log n)\) 的。因此复杂度是 \(\Theta(n\log^2 n)\)。
考虑优化一个 \(\log\)，注意到分治也是以 \(2^n\) 为单位，因此不妨把分治和 FWT 结合一下，就可以变成 \(\Theta(n\log n)\)。
H
简要题意.
给定三维空间中的 \(n\) 个整点 \((x_i,y_i,z_i)\)，初始时你在 \((-10^{300},-10^{300},-10^{300})\) 处，每次可以 \((+1,0,0)\) 或 \((0,+1,0)\) 或 \((0,0,+1)\)，或是将以当前点为中心的，棱长为 \(2k\) 的立方体空间内的整点全部删除。
问删除所有整点所需的最小的 \(k\)。\(n\le 5\times 10^5\)，\(|x_i|,|y_i|,|z_i|\le 10^9\)。
考虑每次跳到剩下的点每一维的最小值。接下来我们必然要从每个维度的最小值中选择一组删除，注意到并不需要真的把范围内的全部删完，于是贪心以得到这一步最小的 \(k\) 即可。
XXII Open Cup: GP of Korea
F
简要题意.
有一张 \(10^6\) 个点的有向图，保证每个点恰有一条出边，且整张图恰有一个环，且该环大小至少为 \(3\)。
保证每个点的出边指向的点都在环上。
你可以执行 \(900\) 次 \((v,x)\) 的询问，表示从 \(v\) 开始走 \(x\) 步会到达哪个点。
请求出环长。
交互库自适应。
\(2\sqrt V+\log V\) 次询问：
首先找到一个环上的点 \(s\)，然后对于所有 \(1 \le i \le 10^3\)，询问 \((s,i)\) 和 \((s,10^3i+1)\)，则一定会至少有一个点出现了两次。
从而可以得到环长的一个倍数，由于询问的性质，可以一个个试除其质因子来得到确切的环长。
\(\sqrt V+2\log V\) 次询问：
注意到我们只需要能凑出 \([5\times 10^5+1,10^6]\) 中的整数即可，因为 \([1,5\times 10^5]\) 中的数一定存在一个倍数在前者中出现。
令 \(U=5\times 10^5,L=10^3\)，我们构造 \(A_{1,2,\dots,L/2},B_{1,2,\dots,L/2}\) 使得 \[
A_i - B_j = (U+(i-1)L+j)(U+iL-(j-1))
\]
这显然包含了 \([U+1,10^6]\) 中所有数作为因子。在行上和列上差分即可求出 \(A,B\)。
\(\sqrt{2V/3}+3\log V\) 次询问：
沿用上述想法，我们考虑后 \(2/3\) 的奇数，也就是凑出 \(333335,333337,\dots,999999\)。
用类似的方法即可，只需要 \(\lceil\sqrt{166667}\rceil = 409\) 的总长。
这样的话，奇数显然可以全部凑出，而 \(10^6\) 内的所有偶数都可以写作 \(2^k (2a+1)\)，其中 \(2a+1 \le 10^6\)，\(1 \le k \le 19\)。因此我们乘上 \(2^{19}\) 再问一遍即可。
I
简要题意.
给出一个 \(n\times m\) 的 \(01\) 矩阵，你可以选取 \(w,h\)，以任意多长度为 \(w\times h\) 的子矩阵覆盖 \(0\) 位置。不能覆盖 \(1\) 位置。可以重叠。
问有多少组 \((w,h)\) 能够覆盖所有 \(0\)。\(w,h\le 3\times 10^3\)。
一个想法是考虑对于每个 \(0\) 求出无法覆盖其的 \((w,h)\)，然后取并即得答案。但是并不好做。
进一步发现一个结论：如果不可行，则一定存在某个无法覆盖的 \(0\) 是贴着边界或者贴着 \(1\) 的。
因此我们只需要考虑这些位置。
再进一步，事实上我们只需要枚举每一行，往上往下算出所有极大矩形；列也类似。这可以用单调栈解决。
XXII Open Cup: GP of Siberia
XXII Open Cup: GP of EDG
C
简要题意.
给出有根树，每个点上有字符 \(\texttt A/\texttt C/\texttt ?\) 之一。
进行 \(q\) 次单点的字符修改，然后询问：将所有 \(\texttt ?\) 替换为 \(\texttt A/\texttt C\) 之一所能得到的最多的祖先与后代构成的 \(\texttt{AC}\) 子序列个数。\(n,q \le 3\times 10^5\)。
记 \(f(u,c),g(u,c)\) 分别为 \(u\) 的祖先和后代中 \(c\) 的个数。
易知答案为 \[
\sum_{s_u=\texttt A} (g(u,\texttt C)+g(u,\texttt ?)) + \sum_{s_u=\texttt ?} \max\{g(u,\texttt C)+g(u,\texttt ?)-f(u,\texttt A)-f(u,\texttt ?),0\}
\]
然后对询问分块（定期重构），考虑相关点的虚树简单维护即可 \(\Theta(q\sqrt n)\)。
H
简要题意.
令 \(w(l,r)\) 为 \(s_ls_{l+1}\cdots s_r\)，其中 \(s_i = \operatorname{popcount}(i) \bmod 2\)。
给出 \(n\) 个区间 \([l_i,r_i]\)，令 \(S = w(l_1,r_1) + w(l_2,r_2) + \dots + w(l_n,r_n)\)。
给定 \(q\) 个询问串，问每个询问串在 \(p\) 中出现的次数。\(n,q \le 10^5\)，\(l_i\le r_i \le 10^9\)，询问串总长不超过 \(5 \times 10^5\)。
写出 \(w(0,n)\) 可以发现这就是 T. M. 序列（也可以直接利用递推过程）。
根据递归定义，可以把询问串拆成 \(O(n \log r)\) 个 T. M. 序列中的项。
建出 AC 自动机，用倍增 DP 正着预处理一下匹配过程，再反着算一下答案。
L
简要题意.
给定两侧均为 \(n\) 个点的完全二分图，边有边权 \(w_{i,j}\)，点有点权 \(u_i,v_j\)。
\(q\) 次询问，每次询问给定 \(a_i,b_i,c_i,d_i\)，仅考虑左侧编号在 \([a_i,b_i]\) 和右侧编号在 \([c_i,d_i]\) 的点，求选择若干条在结点外不交的边，其边权和减去其涉及的结点的点权和的最大值。\(n \le 500\)，\(q \le 3\times 10^5\)，\(u_i,v_j,w_{i,j} \le 10^4\)。
注意到边不交，那么我们就有办法 DP。设 \(f,g,h\) 分别处理总答案，一个左侧或右侧的点已被连接的答案。
可以把询问转化为 \(\Theta(n^2)\) 个点，\(\Theta(n^2)\) 条边的 DAG 上两点最长路。
对询问的两维区间轮流猫树分治，利用 \(g,h\) 作为中转点即可做到 \(\Theta(n(n^2+q))\)。
XXII Open Cup: GP of Southeastern Europe
B
简要题意.
给定 \(n,k,q\)，你需要可持久化地维护 \(k\times n\) 的矩阵 \(A\)。令 \(A_{i,j}^{(t)}\) 表示第 \(t\) 个版本时 \(A_{i,j}\) 的值，\(B_j^{(t)} = \sum_{i=1}^k A_{i,j}^{(t)}\)。
支持在某一版本 \(t\) 某一行区间赋值，区间加，查询 \(\min_{i=l}^r B_i^{(t)}\)。\(k \le 4\)，\(n \le 2.5\times 10^5\)，\(q \le 2\times 10^4\)。
直接用主席树维护，可以发现为了能支持下推赋值标记，需要对每列维护 \(k\) 行的所有子集的和的区间 \(\min\)。
时间复杂度 \(\Theta((n+q\log n)2^k)\)。
D
简要题意.
给定 \(N,M\)，对于 \(1 \le pos,val \le NM\)，计算最长上升子序列和最长下降子序列长度分别等于 \(N\) 和 \(M\) 的 \(NM\) 阶排列 \(p\) 中 \(p_{pos}=val\) 的个数，记为 \(f(pos,val)\)。
对大质数取模。\(NM \le 100\)。
考虑一个不太一样的双射。
令 \(inc_i,dec_i\) 分别为 \(i\) 结尾的最长上升和下降子序列长度，那么我们维护两个 \(N\times M\) 的矩阵 \(A,B\)，令 \(A_{inc_i,dec_i}=i,B_{inc_i,dec_i}=p_i\)。
可以发现 \(A\) 是行列单调增，\(B\) 是行单调减列单调增，并且一对 \((A,B)\) 和 \(p\) 是双射。
因此我们 DP 刻画出 \(A\) 的形态，设 \(f_s\) 表示填至形状为 \(s\) 的方案数，其中 \(s\) 是 \(N \ge a_1 \ge a_2 \ge \dots \ge a_M \ge 0\) 的 \((a_1,a_2,\dots,a_M)\)，共有 \(\binom{N+M}N\) 种。
则 \(f(pos,val)\) 就是在 \(A,B\) 的对应位置上分别是 \(pos\) 和 \(val\) 的 \((A,B)\) 对数。这可以用 \(f\) 统计的结构拼出。
时间复杂度 \(\Theta\left(\binom{N+M}N NM + (NM)^3\right)\)。
I
简要题意.
多组数据。
给定排列 \(p_1,p_2,\dots,p_n\)，每个位置被染成了 \(k\) 种颜色之一。
给定 \(S,C_1,C_2,\dots,C_k\)，你可以任意进行以下操作：
- 交换两个元素，花费 \(S\)。
- 将第 \(i\) 种颜色的位置任意排列，花费 \(C_i\)。
求将其排序的最小代价。
\(\sum n \le 10^5\)，\(k \le 5\)。
注意到操作的顺序并不影响，因此考虑先做第一种操作再做第二种操作。
同时每种颜色显然最多只需用一次第二种操作。先用 \(\Theta(2^k)\) 来枚举一下。
则用了第二次操作的颜色可以直接合并为一个大点，接下来的交换次数是 \(n-cyc\)，其中 \(cyc\) 是我们从这张有向图上分解出的环数。
我们需要最大化 \(cyc\)。
将入度与出度为 \(1\) 的点缩起来，这样最多只有 \(k\) 个点。然后自环和二元环直接拆出来必然不劣。
当不超过 \(4\) 个点时必然能找到出度为 \(1\) 的点，直接缩掉即可。
当有 \(5\) 个点时必然能找到出度为 \(2\) 的点，且其入度不超过 \(2\)，暴力枚举入边和出边的配对方式再缩掉即可。
M
简要题意.
构造 01 串 \(S,T\)，使得它们的最长公共子序列的个数恰为 \(K\)。
\(K \le 10^9\)，\(1 \le |S|,|T| \le 8848\)。
很厉害的 idea。
字符串的次幂表示重复。我们考虑构造 \[ \begin{aligned} S &= \texttt 0^{k_1} \texttt{01} \texttt 0^{k_2} \texttt{01} \cdots \texttt 0^{k_t} \texttt{01} \\ T &= (\texttt{01})^{n+t} \end{aligned} \]
且满足 \(\sum_{i=1}^t k_i \ge n\)。
从而显然 LCS 长度为 \(n+2t\)，且其一定形如 \[ \texttt 0^{a_1} \texttt{01} \texttt 0^{a_2} \texttt{01} \cdots \texttt 0^{a_t} \texttt{01} \]
满足 \(0 \le a_i \le k_i\)，\(\sum_{i=1}^t k_i = n\)。
为了方便，我们不妨设 \(k_i > \frac n2\)，从而可以大大简化容斥过程，LCS 个数即 \[ \binom{n+t-1}{t-1} - \sum_{i=1}^t \binom{n-k_i-1+t-1}{t-1} \]
取 \(t=4\) 时可以满足大部分需求。具体地，我们找出最小的 \(n\) 满足 \(\binom{n+t-1}{t-1}\ge k\)，然后背包凑出 \(K\) 即可。如果无解就将 \(n\) 自增重试。
同时，在 \(k\) 较小的时候，我们可以另取 \[ \begin{aligned} S &= (\texttt 0^{k-1} \texttt{01})^2 \\ T &= (\texttt{01})^{k+1} \end{aligned} \]
XXII Open Cup: GP of Poland
XXII Open Cup: GP of Nanjing
B
简要题意.
给定两个 \(n\) 个点的无向完全图 \(G,H\)，边带权。
可以进行以下操作 \(10^5\) 次将 \(G\) 变成 \(H\)：选择 \(a,b,c,d,x\)，令 \(a\) 分别连向 \(b,c,d\) 的边加 \(x\)，令 \(b,c,d\) 之间连接的边减 \(x\)。
判断是否有解并构造。\(4\le n \le 100\)。
考虑选择 \(5\) 个点 \(a,b,c,d,e\)，进行：
- \((d,a),(d,b),(d,e)\) 减 \(x\)，\((a,b),(b,e),(e,a)\) 加 \(x\)；
- \((d,a),(d,b),(d,c)\) 加 \(x\)，\((a,b),(b,c),(c,d)\) 减 \(x\)；
- \((e,a),(e,c),(e,d)\) 加 \(x\)，\((a,c),(c,d),(d,a)\) 减 \(x\)；
- \((e,a),(e,b),(e,c)\) 减 \(x\)，\((a,b),(b,c),(c,a)\) 加 \(x\)。
最终可以将 \((a,b),(a,e)\) 加 \(x\)，\((a,c),(a,d)\) 减 \(x\)。
从而 \(n\ge 6\) 时只要边权和不变就有解，由上容易构造。
\(n=5\) 时可以以 \(2\) 为单位转移，判断奇偶。
\(n=4\) 时列出方程判断一下。
F
恐怖计几，鸽了。
G
简要题意.
多组数据。
给定 \((n+1)\) 个结点的树和长为 \(n\) 的序列 \(a_1,a_2,\dots,a_n\)。
从树上选择一个点染黑，然后依次染黑当前黑色连通块邻接的白点，将对应边权赋值为 \(a_i\)。
求最大直径。\(O\left(\sum n^3\right)\) 可过。
最大直径显然可以变成枚举某条路径然后使其最大。
假设知道路径上每个点可以往外走多少步，即可直接 DP。
将这个过程放到树上，发现只要知道下一步往哪走即可。
K
简要题意.
给定 \(n\) 个点的完全图，其中有 \(m\) 条边是红色的，其他边是蓝色的。
问所有同构于 \(K_4\) 的子图中，全为红边的个数和全为蓝边的个数的差值。\(n \le 10^5\)，\(m \le 2\times 10^5\)。
考虑容斥，则只需要考虑容斥不超过 \(5\) 条边有限制的。
注意到本质不同的情况都可以用枚举三元环和计数四元环来刻画。
L
简要题意.
有 \(n\) 盏灯排在圆周上。每次你可以选一盏没亮的灯，反转它和相邻两盏的状态。
你需要在 \(2n\) 步之内达成给定状态或者输出无解。\(n \le 10^5\)。
dengls WC 讲了。
枚举前两个状态可以解出整个方程。
考虑如何对于给定的解 \(x_i\) 操作到 \(s_i\)：
先把所有 \(x_i=1,s_i=0\) 的操作完，那么能操作的一定只有 \((0,0)\)，从而可知其右边两个都是 \((1,1)\)。直接对这样的结构操作就行了。