AtCoder Beginner Contest 337

做题顺序有点奇怪。

先做的 C。套路题。令 \(to_i\) 表示 \(i\) 的下一个点是什么。2min 过了。

再做的 B。智障题。令 \(now\) 表示现在在哪个字符（A 或 B 或 C），然后挨个字符跳。结果真成智障了，第一发没判断 A 跳到 C 的情况，罚时 + 1。

又做的 A。入门题。第 5min 过了。

回来做 B。弱智题。几秒切了。前三题总共用了 6min。

再来看 D。阅读题。看懂题后发现是简单二维前缀和。做了种花后这种题压根不慌。第 24min 一遍过。

瞅一眼 E。交互题。慌了，以前好像只做过一两道交互题。

下面是考场上的思路，但是都跟正解的二进制没有任何关系：

• 问 \([1, 2], [2,3],[3,4],\dots\) 。Result1。
• 询问次数 \(m = \lfloor \frac {n+2}2 \rfloor\)，每次问的长度 \(k = \lfloor \frac{n+1}2 \rfloor\)，然后输出 \(m\) 次连续的 \(k\) 个数。Result2 & Result3。
• 可以只问前 \(n - 1\) 个数。如果全回答 \(0\) 就是 \(n\)（其实这就是正解的最后一步）。Result4 & Result5。

最后四题遗憾离场。

C - Lining Up 2

Problem Statement

There are \(N\) people standing in a line: person \(1\), person \(2\), \(\ldots\), person \(N\).

You are given the arrangement of the people as a sequence \(A=(A _ 1,A _ 2,\ldots,A _ N)\) of length \(N\).

\(A _ i\ (1\leq i\leq N)\) represents the following information:

• if \(A _ i=-1\), person \(i\) is at the front of the line;
• if \(A _ i\neq -1\), person \(i\) is right behind person \(A _ i\).

Print the people's numbers in the line from front to back.

Solution

令 \(to_i\) 表示在答案中，\(i\) 的下一个数是多少。那么很显然有 \(to_{a_i} = i\)。

如果 \(a_i = -1\)，那么 \(i\) 是开头。额外定义 \(l\) 表示开头元素。

那么答案即为 \((l, to_l, to_{to_l}, to_{to_{to_l}}, \dots)\)。循环输出即可。

代码。

D - Cheating Gomoku Narabe

Problem Statement

There is a grid with \(H\) rows and \(W\) columns. Let \((i, j)\) denote the cell at the \(i\)-th row from the top and the \(j\)-th column from the left.

Each cell contains one of the characters o, x, and .. The characters written in each cell are represented by \(H\) strings \(S_1, S_2, \ldots, S_H\) of length \(W\); the character written in cell \((i, j)\) is the \(j\)-th character of the string \(S_i\).

For this grid, you may repeat the following operation any number of times, possibly zero:

• Choose one cell with the character . and change the character in that cell to o.

Determine if it is possible to have a sequence of \(K\) horizontally or vertically consecutive cells with o written in all cells (in other words, satisfy at least one of the following two conditions). If it is possible, print the minimum number of operations required to achieve this.

• There is an integer pair \((i, j)\) satisfying \(1 \leq i \leq H\) and \(1 \leq j \leq W-K+1\) such that the characters in cells \((i, j), (i, j+1), \ldots, (i, j+K-1)\) are all o.
• There is an integer pair \((i, j)\) satisfying \(1 \leq i \leq H-K+1\) and \(1 \leq j \leq W\) such that the characters in cells \((i, j), (i+1, j), \ldots, (i+K-1, j)\) are all o.

\(H \ge 1\), \(W \ge 1\), \(H \times W \le 2 \times 10^5\).

Solution

最终的 o 串一定是横着或竖着的。那么我们枚举这个横串的最左边的位置和竖串的最上面的位置。令其为 \((i, j)\)。

• 如果可以从 \((i, j)\) 开始，往右一个横串，就代表第 \(i\) 行中，第 \(j \sim j + k - 1\) 列都没有 x。如果确实一个 x 都没有，那么如果要填满这个横串，就需要把第 \(i\) 行第 \(j \sim j + k - 1\) 列中的所有 . 改为 o。那么代价即第 \(i\) 行第 \(j \sim j + k - 1\) 列中 . 的数量。
• 同理，如果可以从 \((i, j)\) 开始，往下一个竖串，就代表第 \(i\) 列中，第 \(j \sim j + k - 1\) 行都没有 x。如果确实一个 x 都没有，那么如果要填满这个竖串，就需要把第 \(i\) 列第 \(j \sim j + k - 1\) 行中的所有 . 改为 o。那么代价即第 \(i\) 列第 \(j \sim j + k - 1\) 行中 . 的数量。

因此需要预处理 x 和 . 的数量。直接二维前缀和解决。

代码中记录的是 x 和 o 的数量，那么 . 的数量就是 \(k\) 减 o 的数量。

最恶心的是不能开二维数组，得用二维 vector。

E - Bad Juice

Problem Statement

This is an interactive problem (a type of problem where your program interacts with the judge program through Standard Input and Output).

There are \(N\) bottles of juice, numbered \(1\) to \(N\). It has been discovered that exactly one of these bottles has gone bad. Even a small sip of the spoiled juice will cause stomach upset the next day.

Takahashi must identify the spoiled juice by the next day. To do this, he decides to call the minimum necessary number of friends and serve them some of the \(N\) bottles of juice. He can give any number of bottles to each friend, and each bottle of juice can be given to any number of friends.

Print the number of friends to call and how to distribute the juice, then receive information on whether each friend has an upset stomach the next day, and print the spoiled bottle's number.

Solution

二进制拆分。构造很好解释但不好想。

我们枚举每一个二进制位 \(i\)，然后将所有二进制第 \(i\) 位为 \(1\) 的菜品 \(j\) 喂给第 \(i\) 个人。也就是说第 \(i\) 个人吃的是所有二进制下第 \(i\) 位为 \(1\) 的菜品 \(j\)。

例如 \(n = 7\)：

• 第一个人吃菜品 \(1, 3, 5, 7\)。它们的二进制分别是 \((001)_2, (011)_2, (101)_2, (111)_2\)。这些二进制数的第一位都是 \(1\)。
• 第二个人吃菜品 \(2, 3, 6, 7\)。它们的二进制分别是 \((010)_2, (011)_2, (110)_2, (111)_2\)。这些二进制数的第二位都是 \(1\)。
• 第三个人吃菜品 \(4, 5, 6, 7\)，它们的二进制分别是 \((100)_2, (101)_2, (110)_2, (111)_2\)。这些二进制数的第三位都是 \(1\)。

那么如果第 \(i\) 个人死了，就代表那个有毒的菜品编号的第 \(i\) 位为 \(1\)。然后计算有毒的菜品的每一位是什么即可。

很显然这样计算会有 \(\log n + 1\) 个人来试毒，表示 \(n\) 在二进制下的位数。那么你会写出这份代码，然后 WA 了。

实际上，我们只需要对前 \(n - 1\) 盘菜来判断是否有毒。如果前 \(n - 1\) 盘菜都没毒，那么有毒的就在第 \(n\) 盘上。

所以最终代码是这样的。注意 endl。