AtCoder Regular Contest 198 (Div. 2)

A. I hate 1

首先 $1$ 不可能出现在 $S$ 里；其次，$k,k+1$ 不可能同时出现在 $S$ 中。所以 $|S|\le \lfloor\frac{n}{2}\rfloor$.

发现取偶数的时候刚好取到 $n/2$.

一个坑是 $n=1$ 时，$S=\{1\}$，因为此时无法组成任何 pair

1
2
3
4
5
6
7

n = int(input())
if n == 1:
  print(1)
  print(1)
else:
  print(n // 2)
  print(" ".join([str(i) for i in range(2, n + 1, 2)]))

B. Rivalry

我们考虑怎么构造一个合法解。我们先全部写上 $0$，因为在题目条件下，相当于 $0$ 可以任务放置。

然后放 $1$，由于每一个 $1$ 两边有且只有一个 $0$，我们先满足 $\ge 1$ 个 $0$：在每个 $0$ 的两侧各放一个 $1$。此时，我们可以推出第一个条件：如果 $c_1\gt 2c_0$，那么必定有一个 $1$ 夹在两个 $1$ 的中间，不符合条件，所以必然有 $\boxed{c_1\le 2c_0}$.

然后再考察插入 $2$。因为每一个 $1$ 必须紧邻一个 $0$，因此 $2$ 不能插入 $10$ 之间，只能插入 $11$ 之间。一共有 $c_0$ 个 $11$ 可以插入。故得到第二个条件：$\boxed{c_2\le c_0}$

然后我们考虑 $2$ 不足的情况，比如说 $0$ 个 $2$。我们可能得到这样一个情况：

此时注意到第一个 $1$ 其两边都是 $0$，而 $1$ 又全部插入完毕，因此必须有一个 $2$ 插入。所以若 $c_1=1\pmod 2$，就必须有 $c_2\ge 1$；否则，若 $c_1=0\pmod 2$，我们可以构造出这样的结构：$0110110110110\dots$ 一定满足条件。所以第三个条件是：$c_1=0\pmod 2\lor c_2\ge 1$

故总时间复杂度为 $O(T)$.

1
2
3
4
5
6
7
8
9
10
11

def solve():
  x, y, z = map(int, input().split())
  
  if y <= 2 * x and z <= x and (y % 2 == 0 or z >= 1):
    print("Yes")
  else:
    print("No")


for _ in range(int(input())):
  solve()

C.