Petrozavodsk Winter-2018. AtCoder Contest

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\),然后找到一个点即可。

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\) 个点在至少两颗树中,每棵树的根连一个不在这棵树中的点,最后两棵树的根相连即可。