Contest Info

date: 2019.03.05 16:45-21:45

practice link

Solutions

A. XOR

题目大意：给定 \(n\) 个数，让你把这些数分成两个集合 \(A, B\)。最小化 \(|\text{xor}(A)-\text{xor}(B)|\)。

题解：将两个集合的 \(\text{xor}\) 分别记为 \(A,B(A\ge B)\)。最后的答案即为 \(\sum_{i}(A_i-B_i)\cdot 2^i\)。所以对于异或为 \(0\) 的位，我们不用考虑。

因为 \(A\ge B\)。所以 \(A\) 的最高位为 \(1\)，\(B\) 的最高位为 \(0\)。我们将这些数高消（消元的时候对所有的行都要消），第一个基放入集合 \(A\)。剩下的基放入集合 \(B\)。可以看到所有基的和，等于所有基的异或和，等于初始所有数的异或和。那么我们这样就最大化了 \(B\)。

B. Tribute

某年多校原题。

C. Boardroom Meeting

裸三维偏序。

D. Secret Santa

题目大意：要求你数满足下列要求的 \(1\sim n\) 的排列数量：\(i-n+a+1\le p_{i}\le i+a-1\)，其中 \(a\) 给出。

题解：考虑对于 \(i\in[n-a+1,n]\) 范围内的数容斥。这样所有的区间都变成了一个前缀，可以用一个简单的 \(\mathcal{O}(a^{2})\) dp 计算。当然这个 dp 似乎类似于第二类斯特林数，可以用 FFT 优化到 \(\mathcal{O}(a\log a)\)，但是没什么意思。

E. Guessing Game

题目大意：有 \(n(\le 2^k)\) 张卡放在桌上，每张卡上面写了一个长为 \(k\) 的 \(0/1\) 串，它们互不相同。对方选一张卡拿在手上，你可以问多次每个位的值。要猜出这张卡上的串。最坏情况最少问多少次。

题解：用 \(3^k\) 个状态记录当前状态已经知道 \(0/1\)，或者不知道的状态。然后枚举转移 dp 即可。注意处理初值。复杂度 \(\mathcal{O}(k\times 3^k)\)。

F. Flat Earth

签到题。

G. We Need More Managers!

题目大意：给出 \(1\le m\le 2^{n}\) 个不同的 \(1\le n\le 20\) 位的 01 串，定义两个串的距离为不同的位置数量，求最小生成树。

题解：考虑 Prim 算法，任意选择一个点当根，然后每次需要找到连通块内和块外的最小边。

考虑每个串向其只有一位不同的邻居（无论是否存在）连一条无向边，维护增加一个起点和求从任意一个起点出发的最短路径，这个最短路径的最小值等价于最小边。

一开始令所有点的距离为 \(n+1\) ，新增起点的时候将其距离设置为 \(0\)，然后 bfs，仅将能更新最短路径的点入队松弛，这样总的时间复杂度为 \(\mathcal{O}(n^22^n)\)。因为每个点的距离最大是 \(n\)，所以最多被更新 \(n\) 次。实现的时候，可以对每个 dis 建立一个 vector。找最小边的时候枚举最小值。

coldwater’s comment:

有一个 Kruskal 的做法。对所有的 \(2^n\) 个点建图，每个点跟只相差一位的 \(n\) 个点连边。我们要求的等价于：对给定的点求最小生成树，它们两两的边权为它们在图上的最段路。我们从给定点出发（初始距离设为 \(0\)）去 dfs，对于每个点 \(u\)，求出 \(p_u\) 和 \(d_u\) 分别表示到 \(u\) 最近的给定点下标和距离。

我们再枚举图中所有的边 \((u,v)\)，把 \((p_u, p_v, d_u+d_v+1)\) 拿来做 Kruskal 即可。复杂度 \(\mathcal{O}(n2^n(n+\alpha(m))\)。

H. Masterpiece

题目大意：有一个 \(n\times n\) 的网格，一个人两次从 \((0,0)\) 走到 \((n-1,n-1)\)，只能往右或往下走。走过的格子会被染成黑色。现在给出每行和每列黑色格子的数量，问走法的方案数。

题解：如果合法，被染的格子是唯一的，且很容易用 \(\mathcal{O}(n)\) 模拟出来。会出现多种方案的情况在于，每两个相邻的重合格子之间的路径会有两种分配方法。

I. Don’t Split The Atom!

签到题。

J. Bobby Tables

题目大意：给出若干个 \([2,m]\) 中的质数，问是否存在 \(0\le k\le n\le m\) 使得 \({n\choose k}\) 的质因数分解为之前给出的质数。

题解：朴素的想法是枚举所有的 \(n,k\) 来 check，但是这样复杂度过高。我们可以取 \(\ln\) 大致估计一下范围，对于每个 \(n\)，二分出 \(k\)，之后在一个较小的 \(\text{eps}\) 内 check 即可。

鬼知道复杂度是多少。

K. Triples

题目大意：给出一棵 \(n\le10^5\) 点的树，求有多少个三元组 \((x,y,z)\)，满足 \(x<y<z\) 且距离两两相等。

题解：这样的三个点一定满足三条路径有且仅有一个交点，令 \(f[u][i]\) 表示 \(u\) 子树中到 \(u\) 的距离为 \(i\) 的点的方案数，\(g[u][i]\) 表示 \(u\) 子树选了两个点，还需要第三个点到 \(u\) 的距离为 \(i\) 的方案数。

枚举 \(u\) 的儿子 \(v\)，可得：\(\text{ans} += f[u][i - 1] * g[v][i] + g[u][i + 1] * f[v][i]\) 对 \(i\in [0, \text{len}(v)]\)。

\[ \begin{aligned} &g[u][i] += g[v][i + 1]\\ &g[u][i] += f[u][i] * f[v][i - 1]\\ &f[u][i] += f[v][i - 1]\\ \end{aligned} \]

长链剖分，继承长儿子，枚举每个轻儿子（长链头）的长度，长链不重叠。可以做到时空复杂度 \(\mathcal{O}(n)\)，若使用轻重链剖分，继承重儿子，则是时空复杂度 \(\mathcal{O}(n\log{n})\)，均可以通过。

实现的时候，继承可以用一个 int tag[] 来记录偏移量，以及 unordered_map 来作用无限长的数组。因为这题偏移量每次只有 \(\pm 1\)，所以也可以用 deque 来做（可以直接访问下标）。

L. Related Languages

签到题。