Contest Info

date: 2019.03.08 13:01-18:01

practice link

Solutions

A. Vacant Seat

题目大意：交互题。给你 \(n(n<10^5)\) 个位置，他们形成了一个环，其中 \(n\) 是奇数。每个位置要么没有人坐，要么有一个男/女生坐。相邻两个位置不会有相同性别的人。显然至少有一个位置是空的，让你找到这个位置。你可以问最多 \(20\) 次，每次问一个位置，会得到这个位置的信息。

题解：第一次问直径的两个点，假设左右被分为偶数和奇数。如果两点同色，那么偶数部分一定有空位，我们把这两个点合并为一个，递归询问左边。否则右边一定有空位，把这两个点连起来递归问右边。实现的时候显然每次暴力删除另一边的点就可以了。

B. Colorful Doors

题目大意：有 \(n\) 对传送门，它们被排成了一个长度为 \(2n\) 的序列。一个人从最左边的传送门的左边开始，一直向右走，如果碰到传送门就传送到与之对应的传送门的右侧一点点。可以证明这个人一定能走到最右侧的传送门的右边，这时他就会停止。对于中间的 \(2n-1\) 段路，我们可以得到一个长为 \(2n-1\) 的 \(0-1\) 序列，表示每一段路是否被经过。现在给了你这个 \(0-1\) 序列，要你构造一个传送门序列。

题解：我们把第一个和最后一个传送门连接起来，形成一个环，这条新增的路是必走的。那么显然我们从任何一个传送门开始走，都会在一段时间后循环；由于我们反过来走恰好就是把行走序列反向，因此这个序列是纯循环的。这也就证明了我们一定能走到最右侧的传送门。所以我们可以把 \(2n\) 段路分为若干个循环。

我们首先证明一个引理：\(n\) 的奇偶性与环的数量的奇偶性相反。\(n=1\) 时显然。假设 \(n=i\) 时成立，\(n=i+1\) 时，我们考虑新加的两个传送门在哪个位置。

• 若它们在同一个环中，那么它会分裂成两个环。
• 若它们不在同一个环中，那么它们会合并成一个环。

另外还需要注意一个性质，一对传送门的左右两边的路的经过情况应当反过来，例如 \(01\) 配 \(10\)，\(11\) 配 \(11\)。

这样一来，我们就需要这个 \(0-1\) 序列组成唯一一个环。下面开始解决原问题。

• 若所有路都是必须经过的，\(n\) 为偶数时 1 2 1 2 3 4 3 4 ... 是一个解；而由刚才的引理，\(n\) 为奇数时无解。
• 若有奇数个 \(11\)，按照刚刚的性质，这样无解。
• 若有 \(4k\) 个 \(11\)，我们顺次把 \(10\) 和 \(01\) 配对，这样我们每次走过一个 \(10\)，就会被传送到对应的 \(01\)，接着走连续的 \(1\)。这样在走连续的 \(1\) 时的行为就与第一种情况完全相同了。
• 若有 \(4k+2\) 个 \(11\)，如果只有一段有两个以上的 \(1\)，那么这种情况可以归约到第一种情况，无解。否则我们可以找出连续的两个有两个以上 \(1\) 的段，把第一段的最后一个 \(11\) 和第二段的第一个 \(11\) 配对，把第一段后的 \(10\) 和第一段前的 \(01\) 配对，把第一段前的 \(10\) 和第二段前的 \(01\) 配对，其它和上一种情况相同。

C. Construct Point

题目大意：找出一个整点三角形严格内部的整点。

题解：假设端点按照 \(x\) 排序之后为 \((x_1, y_1), (x_2, y_2), (x_3, y_3)\)，其中 \(x_1<x_2<x_3\)（\(x_1=x_2\) 或者 \(x_2=x_3\) 的情况较为简单）。那么我们就是要求区间 \((x_1, x_2]\) 和 \([x_2, x_3)\) 两个区间的整点个数（转成求取整函数的和，用类欧做）。我们二分到一个位置 \(x_0\)，然后找到一个点即可。

D. Knapsack and Queries

题目大意：强制在线，每次加一个体积为\(W\)，价值为\(V\)的物品，或者删掉当前没有被删除的最早加入的物品，然后问体积和在\(\mod{MOD}\)后在区间\([l,r]\)内的最大价值集合。（\(Q\le10^5\)，\(MOD\le500\)）

题解：用两个栈来实现删除，维护两个栈的背包，回答的时候合并背包，可以单调队列\(O(MOD)\)也可以分治\(O(MOD\log{MOD})\)。

E. XorTree

题目大意：给定一棵 \(n\) 个点的树，每条边有一个权值 \(a_i(a_i\in[0, 16))\)。让你做最少的操作，每次选择两个点，和一个数 \(x\)。把路径上的边都异或上 \(x\)，使得最后每条边都是 \(0\)。

题解：定义每个点的权值是邻边的权值异或和。那么操作完全等价于，每次选择两个点，和一个数 \(x\)，把两个点的权值异或上 \(x\)。最后使得每个点的权值是 \(0\)。

对于权值非 \(0\) 的点。我们先按权值相同两两配对，剩下最多 \(15\) 个点，可以发现如果一个集合 \(S\) 的异或和为 \(0\)，我们可以用 \(|S|-1\) 次操作处理这个集合。于是做一个集合 dp，求出最多被分割为多少个异或和为 \(0\) 的集合即可。

F. Antennas on Tree

题目大意：给出 \(n\) 个点的一棵树，让你选择最少的 \(k\) 个点 \(v_0, v_1, \dots, v_{k-1}\)，使得对 \(\forall u\) 有元组 \((d(v_0, u), d(v_1, u), \dots, d(v_{k-1}, u))\) 互不相同。

题解：考虑树上的两个点 \(s, t\)，我们如何区分这两个点。如果 \(d(s, t)\) 是奇数，那么只要至少有一个关键点就可以分辨他俩。否则，在 \(s, t\) 的中点上的关键点对区分 \(s, t\) 毫无作用，我们至少要有一个关键点更靠近 \(s\)，或者更靠近 \(t\)。也就是说，对于 \(\forall u\)，在我们删掉 \(u\) 点之后，假设有 \(k\) 个连通块，那么至少有 \(k-1\) 个连通块内要有关键点（否则假设有两个连通块没有关键点，那这两个连通块与 \(u\) 直接相连的那两个点就无法区分）。

如果给出的树是一条链，那么答案是 \(1\)，我们可以在叶子上放一个关键点。否则，一定有一个点的度至少是 \(3\)，我们以它为根。那现在我们要保证在这棵有根树中，如果一个点 \(u\) 有 \(k\) 个儿子，那么至少 \(k-1\) 个儿子的子树中有关键点（因为父亲那边一定有关键点）。接下来可以 dp，\(\text{dp}[v]\) 表示以 \(v\) 为根的子树至少有多少个关键点。

还有一个做法是从底往上，每个叶子给他祖先链上第一个度大于 \(2\) 的点贡献 \(1\)。那么最后的答案就是 \(\sum (\text{贡献}-1)\)。思路大概是，沿着度小于等于 \(2\) 的点往上走的时候，他们的路径是唯一的，只要能识别出其中的一个点即可。那么如果两个叶子的链有交，那么就必须放一个关键点在某个叶子，也就是给交点做贡献。

I. ADD, DIV, MAX

题目大意：给出一个长度为 \(n(n\le 2\times 10^5)\) 的序列，每个元素 \(a_i(0\le a_i\le 10^8)\)。若干次操作，操作有三种：将区间 \([l, r]\) 加上数字 \(x\)；将区间 \([l, r]\) 除以 \(x\) 向下取整；求区间 \([l, r]\) 的 \(\max\)。其中，\(1\le x\le 10^3\)。

题解：线段树上直接打标记做 add 和 max。维护 min 和 max，对于除法操作，我们一直递归，直到区间满足 \(\min - \lfloor \frac{\min}{x}\rfloor = \max - \lfloor \frac{\max}{x}\rfloor\)，那么这个区间的数除以 \(x\) 向下取整可以转换为减去这个 diff 值。

复杂度证明留坑。大概是两个 \(\log\) 吧？

J. Simple APSP Problem

题目大意：给你一个 \(n\times m\) 的四连通网格，\(n,m\le10^{6}\)，有 \(n\le30\) 个黑格子不能走，求每对白格子的距离之和。

题解：注意到黑格子非常少。对于相邻的两个全白行 \(i,i+1\)，容易证明只有从 \(\le i\) 的行走到 \(\ge i+1\) 的行，才会走这两行之间的边，且恰走一次。那么我们可以事先给答案加上这样的点对数，然后把这两行之间的边权置为 \(0\)（即把这两行缩成一行），对列同理。这样之后网格至多为 \(61\times61\)，直接 bfs 即可。

K. Forest Task

题目大意：给出一棵森林。每个点有一个权值 \(a_i\)。每次可以选择两个点 \(i, j\)，付出 \(a_i+a_j\) 的代价，将它们连上，并且这两个不可以再被选。求最小的代价将其连成一棵树，或者输出无解。

题解：假设一开始有 \(m(m<n-1)\) 条边，那么我们有 \(n-m\) 棵树。显然每棵树至少有一个点会被选择。又因为还需要 \(n-m-1\) 条边，所以一共有 \(2(n-m-1)\) 个点会被选择。我们先从每棵树中贪心的选一个最小的点作为根，再从剩下的点中选择最小的 \(n-m-2\) 个点。下面证明这样一定能连成一棵树：

如果这 \(n-m-2\) 个点全部在一棵树中，那么这棵树中选择的点就有 \(n-m-1\) 个，其余的 \(n-m-1\) 棵树分别连接这些点即可。否则这 \(n-m-2\) 个点在至少两颗树中，每棵树的根连一个不在这棵树中的点，最后两棵树的根相连即可。