Petrozavodsk Winter-2018. Jagiellonian U Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 41/172 | 8 | 12 | 12 |
A¶
solved by 2sozx JJLeo
题意¶
给定一个可重复集合 \(S\) 将其分成两个子集 \(A,B\) 使得两个子集内部的异或和差的绝对值最小，求最小值。\(n \le 10^5, x \le 10^{18}\)
题解¶
显然对于二进制的某一位如果出现了偶数次是没有意义的，将这些删去。
找到最高的二进制位给 \(A\) ，其余的扔进线性基中，贪心的使得 \(A\) 的每一位都为 \(0\) 即可，显然线性基不能保证全部取到，因此令 \(tot = \operatorname{xor}(S)\) ，因此 \(tot \oplus \operatorname{xor}(A)\) 即为 \(B\) ，即可得到最小值。
B¶
solved by 2sozx JJLeo
题意¶
对于一个隐藏的可重集 \(A\)，给定其 \(2^{|S|}-1\) 个非空子集的元素和所组成的可重集 \(B\)，求 \(A\)，或判断无解。(\(1 \le |S| \le 20\))
题解¶
不断从 \(B\) 中拿最小的数 \(x\)，将所有 \(C \subseteq A\) 的 \(C \cup \{x\}\) 从 \(B\) 中移除，如果不存在对应的数则无解。最后再将 \(x\) 加入 \(A\)，直到 \(B\) 为空，此时 \(A\) 即为所求。
C¶
solved by JJLeo
题意¶
求解双关键字最长上升子序列。(\(1 \le n \le 2 \times 10^5\))
题解¶
cdq 分治，设 \(f_i\) 为以 \(i\) 为关键字结尾的最长子序列长度，先递归左区间，再将左右区间按第一维排序，双指针 + 树状数组维护第二维来更新右区间的值，最后再递归按原顺序的右区间，总时间复杂度为 \(O(n \log^2 n)\)。
D¶
upsolved by 2sozx
题意¶
\(t\) 组数据，每组给定 \(n, a\) ，对于 \(i\) 可以选择的区间为 \([\max(1, i - n + a + 1), \min(i + a - 1, n)]\) ，问有多少种取法使得构成一个排列。\(t \le 10, n \le 10 ^ 6, a \le 200\)
题解¶
对于前 \(n - a\) 个数区间范围为 \([1, i + a - 1]\) ，对于 \(n - a + 1 \sim n\) 的数区间范围为 \([i - n + a + 1, n]\)，后面区间只有 \(a\) 个，考虑从后面入手。
考虑容斥，假设所有的数左端点均从 \(1\) 开始，后 \(a\) 个区间的违法区间为 \([1, i - n + a]\) 。设 \(f_s\) 为后 \(a\) 个区间有 \(s\) 个区间违法的违法方案数，因此前 \(n - a\) 个区间的方案数为 \((a - s) ^ {n - a}\)，后 \(a\) 个区间的方案数为 \((a - s)!\)，因此这种情况对答案的贡献为 \((-1)^{s}\times f_s \times (a - s) ^{n - a} \times (a - s) !\)
容易发现无论后面 \(a\) 个区间如何选取前 \(n - a\) 个区间都有一种取法构成一个排列，因此容斥的正确性能够保证。
现在考虑求 \(f_s\) ，对于每一个 \(s\) ，我们维护一个 \(C_{ij}\) 表示从最后一个区间往前取到第 \(i\) 个区间，\(j\) 个区间违法的方案数，\(f_s = C_{1, s}\)。考虑转移，由于第 \(1\sim i - 1\) 还要取 \(s - j\) 个数，因此第 \(i\) 个区间只能取 \(i - (s - j)\) 个值，因此转移即为 \(C_{ij} = (i - s + j) * C_{i+1,j - 1} + C_{i + 1, j}\)，单次查询总复杂度即为 \(O(a^3)\)。
\(f_s\) 还可以用第二类斯特林数计算，然而太垃圾了想不出
E¶
upsolved by JJLeo
题意¶
给定 \(m\) 个长度为 \(n\) 的不同的 \(01\) 串，对方会随机选一个，每次可以问一个位置是啥，最坏情况需要问多少次才能确定所选串。(\(1 \le n \le 13\))
题解¶
状压，状态由三进制表示，对于每一位，已经确定为 \(0\)，已经确定为 \(1\)，或没有确定，记为 \(2\)。
设 \(f_i\) 为当前处于状态 \(i\)，最坏情况下，采取最优策略还需要问问多少次。
转移即为，枚举每个为 \(2\) 的位，询问这一位，取将其变为 \(0,1\) 对应值的最大值 \(+1\)，对每个位置得到的结果取最小值。
如果某个状态下只对应一个串，显然此时 \(f_i=0\)，每个状态对应多少个串可以用高维前缀和求出（对于每一位，只从 \(0,1\) 转移到该位为 \(2\)）
最终答案即为 \(f_{3^n-1}\)，时间复杂度为 \(O(n3^n)\)。
F¶
solved by Bazoka13
题意¶
给一个球和一个平面，问球映射到平面的最大面积。
题解¶
输出球的大圆面积即可。
G¶
upsolved by JJLeo
题意¶
给定 \(n\) 个点，每个点有一个权值 \(a_i\)，任意两点的权值不同，任意两点 \(i,j\) 间有一条边，权值为 \(\operatorname{bitcount}(a_i \oplus a_j)\)，求最小生成树的权值。(\(1 \le a_i < 2^{20}\))
题解¶
考虑 \([0,2^{20}-1]\) 每个整数代表一个点，向所有变化一位的数连边权为 \(1\) 的边，那么原题中两点间边权转化为在这个图上对应两个点间最短路的距离。
进行多源 bfs，得到每个点距离最近的特殊点 \(p_i\) 以及距离 \(d_i\)，枚举所有图中的边 \((u,v)\)，将 \((p_u,p_v,d_u+d_v+1)\) 当作需要考虑的边，跑 Kruskal 算法，即可得到最小生成树。
考虑为什么这样是对的，是否任意两点间的最短路都会被算上，显然不是，假设特殊点 \(i,j\) 间的最短路没有被算上，那么必然存在另一个特殊点 \(k\) 使得 \(i,j\) 间最短路距离大于等于 \(i,k\) 和 \(j,k\) 间的最短路距离（可以画图感性理解，相当于中间叉出去一个更短的），根据 Kruskal 算法，\((i,j)\) 这条边永远也用不上，因为会先连 \((i,k)\) 和 \((j,k)\)，所以这个算法是正确的。
取 \(m=20\)，如果对所有边排序，复杂度即为 \(O(m^22^m)\)，但是注意到边权很小，可以用桶排，复杂度降为 \(O(m2^m)\)，当然不用也能过。
H¶
solved by 2sozx Bazoka13
题意¶
一个 \(n \times n\) 的方格图，一个人从左上走到右下，再走回去，前者只能向右向下，后者只能向上向左，路过的所有格子都会被标黑。给定每行每列有多少个格子被标黑，问有多少种走法满足这个条件。(\(1 \le n \le 10^5\))
题解¶
考虑两个人一起从左上走到右下，显然方案是唯一的，一步步依据给定条件进行模拟：两人在一起时，不能分开时才接着一起走，否则一下一右分开；两人分开时，只会有一种选择。出现不符合给定条件的情况即为不合法。
设除了终点有 \(x\) 个分叉点，则答案为 \(2^x\)。
J¶
solved by 2sozx Bazoka13 JJLeo
题意¶
给定一个正整数 \(X\) 的质因子分解，由 \(t\) 个质数 \(p_i\) 组成，又给定 \(m\)，问是否存在 \(0 \le k \le n \le m\) 使得 \(\dbinom{n}{k} = X\)。(\(1 \le t \le m \le 1.5 \times 10^5\)，\(2 \le p_i \le m\))
题解¶
枚举 \(n\)，\(\dbinom{n}{k}\) 随着 \(k\) 在 \(\left[0, \left\lfloor \dfrac{n}{2} \right \rfloor \right]\) 的范围内单增，可以进行二分确定 \(k\)，但是直接算组合数进行二分值域会裂开，可以取 \(\lg\) 后再算，得到一个大致的范围，之后选取几个大质数，把周围几个 \(k\) 对应的 \(\dbinom{n}{k}\) 和 \(X\) 在对应模意义下进行验证即可，总时间复杂度 \(O(m \log m)\)。
K¶
upsolved by JJLeo
题意¶
给定一颗 \(n\) 个节点的树，问有多少个无序三元点对满足两两之间距离相等。(\(1 \le n \le 10^5\))
题解¶
记 \(d(i,j)\) 为点 \(i,j\) 之间的距离。
设 \(f_{i,j}\) 为以 \(i\) 为根的子树中，满足 \(d(i,x)=j\) 的 \(x\) 的点数；\(g_{i,j}\) 为以 \(i\) 为根的子树中满足 \(d(x,\operatorname{lca}(x,y))=d(y,\operatorname{lca}(x,y))=d(i,\operatorname{lca}(x,y))+j\) 的无序二元点对 \((x,y)\) 的个数。
对于每个节点 \(i\)，初始有 \(f_{i,0} = 1\)。下面的转移中，\(x\) 是 \(i\) 的子节点。
对于 \(f\) 和 \(g\) 有两个很显然的转移： $$ \begin{aligned} f_{x,j} \to f_{i,j+1} \newline g_{x,j} \to g_{i,j-1} \end{aligned} $$ 这一部分可以用长链剖分优化，利用指针很巧妙地继承长 (chang) 儿子的 dp 值，这里 \(g\) 因为是往小移动的，因此前后都需要开相同长度的空间。
同时，还有一个子树合并的转移，即选两个 \(\operatorname{lca}=i\) 的节点： $$ f_{i,j}f_{x,j-1} \to g_{i,j} $$ 以及，对答案的贡献，即为其中两个点在一个子树内，另外一个点在另一个子树或根节点，也是利用子树合并实现： $$ f_{i,j}g_{x,j+1} \to \textit{ans} $$ 上述两者因为也是以深度为下标，也可以用长链剖分优化，即在每个点只会在所在长链顶端进行合并。
总时间复杂度即为 \(O(n)\)。
L¶
solved by Bazoka13
题意¶
给定两个字符串 \(s,t\)，以及正整数 \(k\)，求最大的 \(n\) 使得可以从两个字符串各选一个长度为 \(n\) 的子串，满足这两个子串至多有 \(k\) 个对应位置不同。(\(1 \le |s|,|t| \le 4000\))
题解¶
枚举两个子串的下标差，之后双指针暴力扫即可，时间复杂度为平方级别。
记录¶
0min：分题
9min：CSK AC F
13min：CSK AC I
17min：ZYF AC B
50min：CSK RE1 后 AC，MJX CSK 崩 撤 卖 溜
81min：ZYF WA1 后 AC
131min：MJX 莫名其妙 AC A
220min：MJX AC H
272min：MJX CE1 WA1 TLE1 后 AC
till end：E是个啥玩意
afrer end：E又 ban 了正确的算法
总结¶
Dirt replay¶
L(+1)：
C(+1)：
J(+2)：写了mx 用成了 \(p_i\) ，乱搞次数搞多了，没算复杂度