Petrozavodsk Camp, Summer 2021 IQ test¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 46/90 | 5 | 12 | 13 |
B¶
upsolved by JJLeo
题意¶
数据结构，给定定值 \(k,w\)，维护序列 \(a_1,a_2,\ldots,a_n\)，有 \(m\) 次以下两种操作：
- 设 \(b_1,b_2,\ldots,b_n\) 是将 \(a_1,a_2,\ldots,a_n\) 升序排序后的结果，输出 \(\displaystyle\sum _{i=1}^n \left\lfloor \frac{b_i i^k}{w} \right\rfloor\)。
- 单点修改 \(a_i\)。
(\(1 \le n \le 10^5\)，\(1 \le k,w \le 5\)，\(0 \le a_i \le 10^5\))
题解¶
因此题目转化为分别维护 \(\displaystyle \sum_{i=1}^nb_ii^k\) 和 \(\displaystyle \sum_{i=1}^n\left(b_ii^k \bmod w\right)\)。
注意到 \(a_i\) 范围比较小 (当然很大也是可以离散化的)，建立权值线段树，分别解决这两个问题：
- 对于前者，权值线段树维护某个权值内所有的元素排序后的 \(\displaystyle \sum_{i}b_ii^l\)，这里 \(l=0,1,\ldots,k\)。
合并时右侧区间的元素排名会增大 \(x\)，这里 \(x\) 是左区间元素的个数，变为 \(\displaystyle \sum_{i}b_i{(i+x)}^l=\sum_i \sum_{j=0}^l\binom{l}{j}b_ii^jx^{l-j}= \sum_{j=0}^l\binom{l}{j}x^{l-j}\left(\sum_i b_ii^j\right)\)，预处理组合数和 \(0,1,2,\ldots,n\) 的 \(0,1,2,\ldots,k\) 次幂即可 \(O\left(k^2\right)\) 合并。
- 对于后者，\(\displaystyle \sum_{i=1}^n\left(b_ii^k \bmod w\right)=\displaystyle \sum_{i=1}^n\left((b_i\bmod w){(i \bmod w)}^k \bmod w\right)\)，因此至多有 \(O\left(w^2\right)\) 种不同的取值。
权值线段树维护某个权值内所有的元素排序后 \(b_i \bmod w = A \land i \bmod w = B\) 的元素数 \(c_{A,B}\)。
合并时右侧区间的元素排名会增大 \(x\)，这里 \(x\) 是左区间元素的个数，会对 \(B\) 产生一个 \(x\) 的偏移量，二重循环枚举可以 \(O\left(w^2\right)\) 合并。
总时间复杂度为 \(O\left(m\left(k^2+w^2\right) \log n\right)\)。
C¶
upsolved by
题意¶
官方题解是三页论文。
题解¶
建议发表。
D¶
upsolved by JJLeo
题意¶
初始长度为 \(n\) 的序列 \(1,2,\ldots,n\)，\(n\) 是偶数。每次可以选择两个相邻的数 \(i,j\) 删去，获得 \(c_{i,j}\) 的权值，最小化所有获得权值的最大值。(\(2 \le n \le 4000\))
题解¶
考虑一个 \(O\left(n^3\right)\) 的区间 dp：
- 如果 \(l,r\) 一起选，则有 \(\max(f_{l+1,r-1},c_{l,r}) \to f_{l,r}\)。
- 否则设 \(l\) 和 \(k\) 一起选，那么 \([l,k]\) 和 \([k+1,r]\) 独立，因此有 \(\max(f_{l,k},f_{k+1,r}) \to f_{l,r}\)。
- \(f_{l,r}\) 对所有可能转移过来的可能取 \(\min\)。
可以发现 \(f\) 至多有 \(O\left(n^2\right)\) 个不同的值，可以利用这一点来进行优化。从小到大依次遍历这 \(O\left(n^2\right)\) 个值，将对应的 \(f_{l,r}\) 赋为该值，设遍历到了 \(x\)：
- 如果 \(f_{l,r}\) 已经被转移，\(\max(f_{l,r},c_{l-1,r+1})=x\)，且 \(f_{l-1,r+1}\) 还未被转移，则有 \(f_{l-1,r+1}=x\)。
- 如果 \(f_{l,r}\) 和 \(f_{r+1,k}\) 都被转移，\(\max(f_{l,r},f_{r+1,k})=x\)，且 \(f_{l,k}\) 还未被转移，则有 \(f_{l,k}=x\)。
- 如果 \(f_{l,r}\) 和 \(f_{k,l-1}\) 都被转移，\(\max(f_{l,r},f_{k,l-1})=x\)，且 \(f_{k,r}\) 还未被转移，则有 \(f_{k,r}=x\)。
第一个转移可以 \(O(1)\) 完成，后两个转移如果直接遍历又变成了 \(O\left(n^3\right)\) 了，可以考虑对每个位置维护两个 bitset \(L_i\) 和 \(R_i\)，\(L_{i,j}\) 和 \(R_{i,j}\) 分别表示 \([i,j]\) 和 \([j,i]\) 是否已经被转移，对于第二个转移，对 \(L_l\) 的取反和 \(L_{r+1}\) 的交 \(B\) 不断使用 _Find_next() 找到下一个合法的 \(k\) 进行转移，对于第三个转移同理，这样总时间复杂度为 \(O\left(\dfrac{n^3}{w}\right)\)。
E¶
solved by 2sozx Bazoka13 JJLeo
题意¶
交互题，给定一个 \(n\) 个点的无向连通图，每次可以问一个导出子图的边数，最多问 \(60\) 次，问原图是否有欧拉回路。(\(3 \le n \le 10^4\))
题解¶
原图连通，只需判断每个点度数是否为偶。
先问出总边数，然后随机一个点集 \(A\)，问这个点集的边数，以及剩下点组成集合 \(B\) 的边数，总边数减去这两个边数之和即为 \(A\) 和 \(B\) 之间的边数。
进行 \(29\) 次，如果有一次 \(A\) 和 \(B\) 之间的边数是奇数，说明没有欧拉回路，否则有。
正确性证明：
首先如果 \(A\) 和 \(B\) 之间的边数是奇数，显然从 \(A\) 出发不存在能回到 \(A\) 的回路。或者说，\(A\) 和 \(B\) 之间的边数的奇偶性和 \(A\) 中所有点度数和的奇偶性相同，因此必然存在一个度数为奇的点。
假设有一个点 \(x\) 的度数为奇，在其它点确定被划分到 \(A\) 和 \(B\) 时，这个点如果划分到 \(A\) 使得中间边数是偶数，则其划分到 \(B\) 就会让中间边数为奇，反之亦然。因此每次有 \(\dfrac{1}{2}\) 的概率错判，最终错判的概率是 \(\dfrac{1}{2^{29}}\)，显然是可以接受的。
F¶
solved by 2sozx JJLeo
题意¶
给定质数 \(p\) 和 \(q\) 组询问，每次问将 \((a,b)\) 变为 \((c,d)\) 最少需要多少次操作，或判断无解。一次操作是指：
- 将 \((a,b)\) 变为 \((2a \bmod p,(b+p-a) \bmod p)\) 或者 \(((a+p-b) \bmod p,2b \bmod p)\)。
(\(2 \le p \le 10^9+7\)，\(1 \le q \le 10^5\))
题解¶
容易发现 \((a+b) \bmod p\) 始终为定值，如果 \(c + d \not \equiv a + b \pmod p\)，无解。
否则，设 \(A=(a+b) \bmod p\)，下述所有运算均在模 \(p\) 意义下进行。
每次变化可以写为 \((2a,2b-A)\) 或 \((2a-A,2b)\)，因此进行 \(n\) 次操作后 \(a\) 可以变成 \(2^na-xA\)，其中 \(x \in \left[0,2^{n}-1\right]\)，从而如果 \(c\) 可以被表示为 \(2^na-xA\) 的形式就可以 \(n\) 次操作变过去。注意 \(p\) 是质数因此存在逆元，这等价于 \(A^{-1}\left(2^na-c\right)=x\)，从而只需判 \(A^{-1}\left(2^na-c\right) \bmod p\) 是否在 \(\left[0,2^{n}-1\right]\) 范围内，至多进行 \(O(\log p)\) 次就一定可以，因此从小到大枚举 \(n\) 判定即可，总时间复杂度为 \(O(q \log p)\)。
G¶
upsolved by JJLeo
题意¶
给定一个 \(n\) 个点的完全无向图，每条边被黑白染色，求恰好五条边同色的四阶完全子图的数量减去没有同色三角形的四阶完全子图的数量。(\(4 \le n \le 2000\))
题解¶
超级 IQ test，太离谱了，大致写一下。
有 \(6\) 种本质不同的四阶完全子图，边颜色翻转后相同算一种。设它们的数量分别为 \(x_1,x_2,\ldots,x_6\)，我们需要的是两种分别记为 \(x_6\) 和 \(x_2\)，最后答案为 \(x_6-x_2\)。
计算四个量：
- 四阶完全子图数量 \(\dbinom{n}{4}\)。
- 四元点对 \((A,B,C,D)\) 的数量，四个顶点不同，且 \(AB\) 和 \(BC\) 颜色不同。这个可以枚举每个顶点枚举其两种颜色边的数量后 \(O\left(n^2\right)\) 计算。
- 四元点对 \((A,B,C,D)\) 的数量，四个顶点不同，且 \(AB,BC,AD,DC,AC\) 颜色相同，相当于两个同色三角形共用一条边，对每个点预处理一个 bitset 之后枚举两个点将其 bitset 按位与起来求 \(1\) 的数量即可，复杂度为 \(O\left(\dfrac{n^3}{w}\right)\)。
- 四元点对 \((A,B,C,D)\) 的数量，四个顶点不同，且 \(AB,BC,AD,DC\) 颜色相同，\(AC\) 和前面四条边颜色不同。相当于两个三角形共用一条边，共用的边和其它颜色不同，对每个点预处理一个 bitset 之后枚举两个点将其 bitset 按位与起来求 \(1\) 的数量即可，复杂度为 \(O\left(\dfrac{n^3}{w}\right)\)。
上述四个值均是 \(x_1,x_2,\ldots,x_6\) 线性组合式，将四个式子线性组合就能凑出 \(x_6-x_2\)，好。
H¶
solved by 2sozx Bazoka13 JJLeo
题意¶
构造恰有 \(k\) 个无序点对 \((u,v)\) 有哈密顿路径的无向图，要求 \(2 \le n \le 20\)。(\(1 \le k \le 60\))
题解¶
对于 \(k=1,2\)，输出样例。
对于 \(3 \le k \le 20\)，输出一个环。
考虑一个完全图，随便选两个点再连出一个点，在此基础上，在这两个点之间不断增加点形成一条链，每增加一个点就能让点对数量增加 \(1\)。
初始图为 \(n+2\) 个点，暴力打表出此时的点对数量 \(f_n\)，则还能增加 \(18-n\) 个点，那么 \(k \in [f_n,f_n+18-n]\) 的方案就可以构造。分别取 \(n=5,6,7,8,9\) 可以发现其覆盖了 \([21,60]\)。
官方题解是是设链上增加了 \(m\) 个点，那么所有合法的 \((n,m)\) 覆盖了 \([21,60]\)。
I¶
upsolved by JJLeo
题意¶
二维平面上一堆矩形，为简化题意保证对于两个不同的矩形，其顶点横纵坐标均不相同。
问有多少个矩形三元组，其互不相交。(\(1 \le n \le 2 \times 10^5\))
题解¶
考虑每个矩形代表一个点，两个矩形之间如果有交则连一条黑边，否则白边，那么需要求白色三角形的数量。如果我们能求出同色三角形的数量和黑色三角形的数量，就可以得到答案。
对于前者，黑白边完全图求同色三角形是经典问题，我们只需求出每个点有多少条黑边和白边，也就是每个矩形和多少个矩形相交：
首先需要维护一个数据结构，支持插入线段、删除线段、查询一条线段和多少条线段相交。
和线段 \([l_i,r_i]\) 不相交当且仅当 \(r_j < l_i\) 或 \(l_j > r_i\)，且如果 \(r_j < l_i\) 必然不会 \(l_j > r_i\)，因此用两个树状数组维护 \(r\) 的前缀和和 \(l\) 的后缀和，用总线段数减去这两个即可。
接下来利用扫描线扩大到二维平面上，我们扫描 \(l,r\) 这个维度，在相关点在数据结构中加入/删除/查询 \([d_i,u_i]\) 这条线段。
对于左右边界为 \([l_i,r_i]\) 的矩形和多少矩形相交，首先计算 \(l_j<l_i\) 的矩形，从小到大遍历，对于每个矩形在 \(l_i\) 处加入 \([d_i,u_i]\)，在 \(r_i\) 处删除 \([d_i,u_i]\)，那么每个矩形在 \(l_i\) 处插入线段之前先查询一下 \([d_i,u_i]\) 与多少线段相交，即为 \(l_j<l_i\) 与其相交的矩形个数。
接着再计算计算 \(l_j>l_i\) 的矩形，还是从小到大遍历，对于每个矩形在 \(l_i\) 处加入 \([d_i,u_i]\)，但不在 \(r_i\) 处删除。每个矩形在 \(l_i\) 处加入后记录一下 \([d_i,u_i]\) 和多少线段相交，在 \(r_i\) 处再查询一下 \([d_i,u_i]\) 和多少线段相交，增量即为 \(l_j>l_i\) 与其相交的矩形个数。
对于后者，即为计算两两相交的矩形三元组：
还是需要解决一维上的问题，维护一个数据结构，支持加入线段、删除线段、以及计算有多少个两两相交的线段三元组。
考虑设 \(A_i\) 是有多少条线段覆盖了 \(i\) 这个点，\(B_i\) 是有多少条右端点不是 \(i\) 的线段覆盖了 \(i\) 这个点，\(\dbinom{A_i}{3} - \dbinom{B_i}{3}\) 即为最右线段右端点为 \(i\) 的三元组数量，那么答案即为 \(\displaystyle \sum_i \left[\binom{A_i}{3} - \binom{B_i}{3}\right]\) 。
接下来还是利用扫描线扩大到二维平面上，扫描 \(l,r\) 这个维度，在相关点在数据结构中加入/删除/查询 \([d_i,u_i]\) 这条线段。
从小到大依次遍历，对于每个矩形在 \(l_i\) 处加入 \([d_i,u_i]\)，在 \(r_i\) 处删除 \([d_i,u_i]\)。每个矩形加入时算一下加入后相比加入前增加了多少个三元组，答案即为对于每个矩形对该增量求和。
为什么这样不会算重？因为每个三元组恰好被 \(l_i\) 最大的那个矩形所计算到。
总时间复杂度为 \(O\left(n \log n\right)\)。
J¶
upsolved by JJLeo
题意¶
对于两个排列 \(1\) 到 \(n\) 的排列 \(p\) 和 \(q\)，长度为 \(n\) 的 \(01\) 串 \(s\) ，如果存在一种方案将 \(1,2,\ldots,2n\) 填到一个 \(2 \times n\) 的矩阵 \(a\) 中，满足下述条件：
- 每种数字恰好出现一次。
- \(a_{1,i} < a_{1,j} \Leftrightarrow p_i < p_j\)。
- \(a_{2,i} < a_{2,j} \Leftrightarrow q_i < q_j\)。
- \(a_{1,i} < a_{2,i} \Leftrightarrow s_i=0\)。
那么就称 \(s\) 是合法的，定义 \(f(p,q)\) 为对于排列 \(p\) 和 \(q\) 来说合法 \(01\) 串的数量。
现给定两个排列 \(1\) 到 \(n\) 的排列 \(p\) 和 \(q\)，其中 \(q\) 中有一些位置是不定的，求出对于每一种可能的 \(q\) 的 \(f(p,q)\) 的和。
(\(1 \le n \le 100\))
题解¶
可以发现列之间的顺序不影响答案，因此可以将每列按第一行的元素从小大排序，也就是将 \(p\) 排序成 \(1,2,\ldots,n\)，把 \(q\) 换到对应的位置。
引理：\(f([1,2,\ldots,n],q)\) 是 \(q\) 中上升子序列的数量。
不妨让每个位置代表一个点，排列和字符串所产生的性质 \(u < v\) 则连有向边 \(u \to v\)，则 \(01\) 串合法当且仅当这个图无环，显然只在一行是不能有环的，因此如果有环那么也一定有这样的环：\((1,i) \to (1,j) \to(2,j) \to (2,i) \to(1,i)\)。
考虑 \(q\) 中最大的值 \(q_i\)，如果 \(s_i=0\) 也即 \(i < q_i\)，因为第二行没有再比 \(q_i\) 大的数了，所以 \((2,i)\) 没有任何出边，不会产生环，从而把这一列删掉不会有任何影响。
如果 \(s_i=1\) 也即 \(i > q_i\)，那么对于 \(j > i\) 必然也有 \(j > q_j\)，从而 \(s_j=1\)。对于这些 \(j \ge i\) 的 \((2,j)\) 也不会存在于一个环中，因为它们一旦做到 \((1,j)\) 就只能继续往右走，而右侧所有点都没有出边。
因此每个串的构造过程可以抽象成两种操作：
- 删掉一个最大的数。
- 删掉一个最大的数和它右边所有数。
可以发现每次操作 \(2\) 等价于选一个数，且所有操作 \(2\) 选出来的数都是一个上升子序列，且操作序列不同根据上述分析得到的 \(s\) 也是不同的。
因此问题转化为一个排列中一些位置不定，求对于每一种可能的 \(q\) 的上升子序列的数量的和。
不妨设 \(q_0=0,q_{n+1}=n+1\)，同时 \(f_{i,j}\) 是以 \(i\) 结尾有 \(j\) 个未知位置被选入上升子序列的方案数，设有 \(m\) 个位置是未知的，那么最终答案即为 \(\displaystyle \sum _{i=0}^m (m-i)!f_{n+1,i}\)。
设 \(a_{l,r}\) 为 \([l,r]\) 中的值有多少个没有出现，\(b_{l,r}\) 为位置 \([l,r]\) 中的空位数量，则有如下转移：
总时间复杂度为 \(O\left(n^4\right)\)。
K¶
upsolved by JJLeo
题意¶
\(t\) 组数据，构造 \(n\) 个元素的多重集，使得其恰有 \(k\) 个子集和为 \(0\)，要求 \(n \le 30\) 且元素绝对值不超过 \(10^{16}\)。(\(1 \le t \le 1000\)，\(1 \le k \le 10^6\))
题解¶
考虑如果我们有一个多重集 \(S\)，其和不为 \(0\)，恰有 \(k\) 个子集和为 \(0\)。设其中正数的和为 \(P\)，负数的和为 \(N\)，不妨设 \(P > -N\)，那么我们如果只往里面加是 \(P\) 倍数的数，不妨设新加的数组成的集合为 \(T\)，那么 \(S \cup T\) 中和为 \(0\) 的子集数量即为 \(kx+y\)，其中 \(x\) 是 \(T\) 中和为 \(0\) 的子集数，\(y\) 是 \(T\) 中和为 \(-P\) 的子集数。
子集中属于 \(S\) 的部分的和要么是 \(0\) 要么是 \(P\)，分别有 \(k\) 种方案和 \(1\) 种方案。
如果不是这样，那么其绝对值必然小于 \(P\) 且不为 \(0\)，\(T\) 中元素均为 \(P\) 倍数，从而子集和模 \(P\) 永远不为 \(0\)，从而必然不是 \(0\)。
预处理所有大小不超过 \(8\) 的元素来自 \(\{-3,-2,-1,1,2,3\}\) 的多重集，并记录其和为 \(0\) 和 \(1\) 的子集数。
设 \(f_i\) 为恰有 \(i\) 个子集和为 \(0\) 最少需要的多重集大小，\(P\) 是其正数的和，考虑选择上述预处理的一个集合 \(T\) 加入，设其和为 \(0\) 和 \(1\) 的子集数分别为 \(x\) 和 \(y\)，将 \(T\) 中所有元素都乘以 \(P\)，那么 \(f_i + |T|\) 就可以转移到 \(f_{ix+y}\)。
可以发现这样对 \(i=1,2,\ldots,10^6\) 来说 \(f_i\) 都不超过 \(30\)，只需记录转移过程即可输出方案。有可能加入集合时集合的元素之和为负了，这时将所有数取相反数即可。
一个细节是如果直接用所有预处理的多重集那么数量会过多，乘上一个 \(10^6\) 就 T 了。可以对 \(x,y\) 相同的取多重集大小更小的，这样转移就会减少很多，就卡过去了。
L¶
upsolved by JJLeo
题意¶
两个长度为 \(2n+1\) 由 A,B,C,? 组成的字符串，可以将问号替换为这三种字母，问有多少种替换方式使得两者的最长公共子序列长度恰为 \(n\)。(\(1 \le n \le 10^6\))
题解¶
考虑两个字符串的前两个字符，根据抽屉原理，四个字符必然由两个是相同的。再考虑接下来两个字符串的两个字符，重复 \(n\) 次这个过程，LCS 至少为 \(n\)。
如果能观察到这一点，就可以猜想符合条件的字符串一定具有鲜明特点，且容易计数。
在比赛中如果发现了这一点，那么做法应该暴力打表找规律。可以发现只有以下两种情况 LCS 恰好是 \(n\)：
- 第一个字符串为
AB交替，第二个字符串奇数位置都是C，偶数位置是A或B。 - 两个字符串偶数位置都是
C，前 \(k\) 个奇数位置第一个字符串是A第二个字符串是B，后 \(n-k\) 个奇数位置第一个字符串是B第二个字符串是A。
这两种模式 ABC 当然是可以互换的。
考虑如何计数，一种方式是直接枚举 ABC 的全排列然后计数，但是这样会重，需要限制第二种模式 \(1 < k < n\)，第一种模式如果第二个串偶数位置都是 A 只算 \(\dfrac{1}{2}\) 次 (因为它会算两次)。这样就不会重了。
当然题解给出了严谨证明，大致就是利用数学归纳法，删掉前两个或后两个字符就能得到一个已经归纳过的字符串对，对新增字符暴力分类讨论即可，这里略。
记录¶
0h：MJX 说 M 是签到，ZYF 懵了。懵了一会儿好像懂了，直接暴力过了。然后 MJX 看了看 A 想了下过了，开始和ZYF CSK 想F，逆十字7min过了，但是啥也想不出来，IQ--。
1h：然后卡到快俩小时，E 看错了题意没看到连通，完全是个新题，随机一发过了。ZYF开始想恒等式的解法，推了半天，发现是个恒等式。但是其实是对的，少开个 long long wa 了一发，然后过了。
2~5h：然后开始做梦构造H，开始CSK想了个构造的方法，但是好像覆盖不全，经过亿点点的推进，想到了先构造几个完全图，然后再连起来，去构造这60个数，感觉暴力跑不完就先考虑俩完全图连一起(？为啥不直接考虑一个？)，暴力跑了一堆数据出来，发现差了点，最后想到好像一个完全图自己就最优了（？为什么最后才能想到，属于是构造题血脉压制了）。