Contest Info

date: 2018.08.23 12:00-17:00

practice link

Solutions

A. Prevent a Galactic War!

题目大意：给出一个 \(n\times n\) 的矩阵 \(\{c_{ij}\}\) 和一个 \(n\) 维向量 \(\{y_i\}\)。你可以通过 \(x_i=y_i+\sum_{j=1}^nc_{ij}\) 得到向量 \(\mathbf{X}\)。现在 \(\mathbf{C}\) 和 \(\mathbf{Y}\) 发生了变化，你不知道变化后的 \(\mathbf{C}'\)，但是你知道变化后的 \(\mathbf{Y}'\)。现在让你求 \(\mathbf{X}'\)，满足 \(\displaystyle \forall i,j, \frac{x_j}{c_{ij}}=\frac{x'_j}{c'_{ij}}\)。\(n\leq 3000,c_{ij}\leq 1000,y_i,y'_i\in[10^7, 10^9]\)。

题解：注意到 \(\sum c_{ij}\) 和 \(y_i\) 差了一个数量级，我们设初始解 \(\mathbf{X}'=\mathbf{Y}'\)，那么此时已经很接近答案，每次再用 \(\displaystyle \{y'_i+\sum_{j=1}^n \frac{c_{ij}*x'_j}{x_j}\}\) 来更新 \(\mathbf{X}'\)，迭代几次就可以出解。

B. Forcefield

签到题

C. Missing Part

题目大意：给你两个长度为 \(n\) 的串 \(s\) 和 \(t\)，\(s\) 由 A-E 组成，\(t\) 由 a-e 组成。现在你可以指定一个双射将 A-E 映射到 a-e，还可以将 \(s\) 或 \(t\) 循环移动。问所有的可能中失配位置最少有多少个。

题解：FFT 字符串匹配入门题。时间复杂度 \(\mathcal{O}(5^{2}n\log n+5!n)\)。

D. Handling a Spaceship

题目大意：交互题。给出 \(n(n\le100)\) 维空间中的一组基 \(\{X_{i}\}\)，以及一个 \(n\times m\) 的矩阵 \(K\)。\(K\) 满足每一行的元素严格递增，且每行至少有一个位置是 \(0\)。现在 \(X_{i}\) 和 \(K\) 都是未知的，但是每次询问你可以问一个 \(n\) 维向量 \(g\)，交互程序会回答 \(\sum_{i=1}^{n}K_{i,g_{i}}X_{i}\)。在 \(120\) 次询问以内，找出一个 \(g\)，使得 \(\sum_{i=1}^{n}K_{i,g_{i}}X_{i}=\mathbf{0}\)。

题解：因为 \(\{X_{i}\}\) 是一组基，因此满足条件的 \(K_{i,g_{i}}\) 必须等于 \(0\)，也即我们要找到 \(K\) 中每一行的 \(0\) 的位置。由于 \(K\) 的每一行都是递增的，因此我们可以考虑 \(n\) 行一起二分求解。我们可以很容易地用 \(n+1\) 次询问来得到 \((K_{i,2}-K_{i,1})X_{i}\)，将它们作为一组新的基。因为 \(K\) 中每一行严格递增，所以 \(K_{i,2}-K_{i,1}\neq 0\)。

这样，每次我们询问后，都可以通过高消解出 \(\sum_{i=1}^{n}K_{i,g_{i}}X_{i}\) 在这组新基下的坐标。容易发现 \(\displaystyle K'_{i,g_{i}}=\frac{K_{i,g_{i}}}{K_{i,2}-K_{i,1}}\)，因此 \(\text{signal}(K'_{i,g_{i}})=\text{signal}(K_{i,g_{i}})\)。也就是说，我们利用 \(K'_{i,g_{i}}\) 的正负来进行二分效果是一样的。这样总的询问次数是 \(n+1+\lceil\log n\rceil\)，时间复杂度 \(\mathcal{O}(n^{3}\log n)\)。

E. Cryptographic Argument

题目大意：一个纸带上均匀地写着 \(0\sim n-1\) 的整数（其中 \(n=2^{k},k\le30\)）。现在将纸带对折 \(k\) 次，每次将右边一半折到左边一半的下面。设对折后的纸带从上到下的数依次是 \(a_{0}\) 到 \(a_{n-1}\)。有 \(m\) 次询问，每次给出一个区间 \([l,r]\)，问 \(a_{l}+a_{l+1}\oplus a_{l+2}+a_{l+3}\oplus\cdots a_{r}\) 的值。若 \(l\) 是偶数，那么加法优先级高；若 \(l\) 是奇数，那么异或优先级高。

题解：容易注意到，若 \(l\) 是偶数，那么 \(a_{l}+a_{l+1}=a_{l}\oplus a_{l+1}=n-1\)。这样一来，我们每次就只需要询问一个或两个单点的值。容易证明，若 \(l\) 是偶数，那么 \(a_{l}=\text{rev}(\frac{l}{2},k)\)，其中 \(\text{rev}(n,k)\) 表示把 \(n\) 看作 \(k\) 位二进制数按位翻转；若 \(l\) 是奇数，那么 \(a_{l}=\text{rev}(n-1-\frac{l-1}{2},k)\)。实现时只需要把 \(n\) 拆成两个 \(2^{15}\) 以内的数的拼接分别翻转即可。 \(\mathcal{O}(1)\) 查询。

时间复杂度 \(\mathcal{O}(m)\)。

F. The Jedi Killer

签到几何题，注意仔细读题和分析清楚 case。

G. Youngling Tournament

题目大意：给出一个长度为 \(n\le10^5\) 的数列 \(1\le a_i\le10^{12}\) ，定义胜者为将 \(a_i\) 从小到大排序后的数组 \(b_i\) 中满足 \(\sum_{j<i}b_j \le b_i\) 的位置 \(i\) 的数量，求胜者数量。然后 \(m\le50000\) 次单点修改，每次修改后求胜者数量。

题解：每次胜者的数量显然不会超过 \(\mathcal{O}(\log(\max A))\)个，我们可以暴力去 check。用 multiset 维护偏序，离散化树状数组维护前缀和即可。注意最小的数中可以出现两个胜者，其它相同的数最多只会出现一个胜者。

时间复杂度 \(\mathcal{O}(n\log{n}\log(\max A))\)。

H. Garland Checking

题目大意：交互题。jury 有一棵树（你只知道点数 \(n\)），给出若干次询问和修改。修改是断开一条边或者连接一条边，每条边只会被连接/断开一次，询问两个点的连通性，一开始树没有边。

题解：LCT 裸题。

coldwater’s fake solution:

每个点存 \(f[x]\) 表示父亲，每次修改询问 \(a,b\)，先顺着 \(a\) 的 \(f\)，把这一条链的父子关系翻转，把 \(a\) 提起来做根。连接则 \(f[a]=b\)，断开则 \(f[b]=0\)，询问则把 \(b\) 往上跳看是否能到 \(a\)。很容易被卡掉，但是过了。

I. Equipment Assembling

题目大意：给出 \(n\le20\) 个点，\(m\le1000\) 条边的边带权无向图。每花 \(1\) 的代价可以将一条边的边权增加或减少 \(1\)（但是要非负），求最小的代价，使得最小生成森林唯一，输出方案。

题解：顺着 kruskal 的过程来思考，每次考虑权值相同的一组边同时加入，忽略对连通性没有贡献的边（边两端点已经同属一个连通块）。之后，最小生成森林唯一的充要条件是：不存在一个环，包含大于等于两条现在考虑的边。

如果存在这样的环，我们有两种方式处理，将当前考虑的一些边的边权减小 \(1\) ，或是将当前考虑的一些边的边权增大 \(1\)。

将连通块缩点，对这些点重标号，dp 求出每个集合内部的边数 \(\text{cnt}[S]\) 。

如果存在一个集合 \(S\) 满足：\(\text{cnt}[S] - (|S|-1)>|S|-1\)，这样集合 \(S\) 内部的边使用减小 \(|S|-1\) 条边的方式处理最优，我们选 \(|S|\) 最小的 \(S\) 来做。处理完之后，使用集合内部的边更新连通性，然后再重新计算所有的 \(\text{cnt}[S]\)，继续找这样的 \(|S|\)。

如果不存在这样的 \(S\) ，我们就使用增大边权的方式处理所有冲突，更新连通性，并枚举权值更大的边处理。

每次 dp 的复杂度是 \(\mathcal{O}(k\times2^k)\)，\(k\) 为发生冲突的连通块数量，因为每做一次 dp 后 \(k\) 至少减少 \(1\) ，时间复杂度 \(\mathcal{O}(n\cdot2^n+nm )\)，实际上这个上界也远不会达到。

coldwater’s comment:

选取 \(|S|\) 最小的 \(S\) 来做，是为了保证这个 \(S\) 一定连通。考虑如果有一个不连通的 \(S\)，满足 \(\text{cnt}[S]>2(|S|-1)\)，那么 \(S\) 中一定存在一个连通子图 \(S'\) 也满足上述不等式，且 \(|S'|<|S|\)。

Dirt Replay

B: -1 set 找前驱的时候用 –lower_bound，如果没有前驱，lower_bound 是 begin，自减还是 begin，是个假前驱

D: -1 Z 的高斯消元写错了

F: -3 读错题意；三点共线；还有一个情况

G: -1 没套函数

H: -2 启发式合并错算法；忘记 fflush（最后假算法过了）