A. I hate 1

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

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

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

Code
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

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

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

然后再考察插入 22。因为每一个 11 必须紧邻一个 00,因此 22 不能插入 1010 之间,只能插入 1111 之间。一共有 c0c_01111 可以插入。故得到第二个条件:c2c0\boxed{c_2\le c_0}

然后我们考虑 22 不足的情况,比如说 0022。我们可能得到这样一个情况:

101 101 101 10_ 101\ 101\ 101\ \dots 10\_

此时注意到第一个 11 其两边都是 00,而 11 又全部插入完毕,因此必须有一个 22 插入。所以若 c1=1(mod2)c_1=1\pmod 2,就必须有 c21c_2\ge 1;否则,若 c1=0(mod2)c_1=0\pmod 2,我们可以构造出这样的结构:01101101101100110110110110\dots 一定满足条件。所以第三个条件是:c1=0(mod2)c21c_1=0\pmod 2\lor c_2\ge 1

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

Code
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. Error Swap

看到将 AA 数列变成 BB 数列,我们考虑数列变换模型,考虑能否用题目的操作,操作出 ai1,aj+1a_i-1,a_j+1 的形式。

手推一下,发现可以用 44 步操作模拟。具体如下:

任意两个数之间一加一减都可以用 44 次操作完成
Prefix Dec-IncIndexijkA[Index]xyzswap(i,k)z1yx+1swap(i,j)y1zx+1swap(i,k)xzyswap(j,k)xy1z+1 \text{Prefix Dec-Inc}\\ \begin{array}{c|cccc} \text{Index}&i&j&k\\ \text{A[Index]}&x&y&z\\ \hline \texttt{swap(i,k)}&z-1&y&x+1\\ \texttt{swap(i,j)}&y-1&z&x+1\\ \texttt{swap(i,k)}&x&z&y\\ \texttt{swap(j,k)}&x&y-1&z+1\\ \end{array}
Prefix Inc-DecIndexijkA[Index]xyzswap(j,k)xz1y+1swap(i,k)yz1x+1swap(i,j)z2y+1x+1swap(i,k)xy+1z1 \text{Prefix Inc-Dec}\\ \begin{array}{c|cccc} \text{Index}&i&j&k\\ \text{A[Index]}&x&y&z\\ \hline \texttt{swap(j,k)}&x&z-1&y+1\\ \texttt{swap(i,k)}&y&z-1&x+1\\ \texttt{swap(i,j)}&z-2&y+1&x+1\\ \texttt{swap(i,k)}&x&y+1&z-1\\ \end{array}
Suffix Inc-DecIndexijkA[Index]xyzswap(i,j)y1x+1zswap(j,k)y1z1x+2swap(i,k)x+1z1yswap(j,k)x+1y1z \text{Suffix Inc-Dec}\\ \begin{array}{c|cccc} \text{Index}&i&j&k\\ \text{A[Index]}&x&y&z\\ \hline \texttt{swap(i,j)}&y-1&x+1&z\\ \texttt{swap(j,k)}&y-1&z-1&x+2\\ \texttt{swap(i,k)}&x+1&z-1&y\\ \texttt{swap(j,k)}&x+1&y-1&z\\ \end{array}
Suffix Dec-IncIndexijkA[Index]xyzswap(j,k)xz1y+1swap(i,k)yz1x+1swap(j,k)yxzswap(i,j)x1y+1z \text{Suffix Dec-Inc}\\ \begin{array}{c|cccc} \text{Index}&i&j&k\\ \text{A[Index]}&x&y&z\\ \hline \texttt{swap(j,k)}&x&z-1&y+1\\ \texttt{swap(i,k)}&y&z-1&x+1\\ \texttt{swap(j,k)}&y&x&z\\ \texttt{swap(i,j)}&x-1&y+1&z\\ \end{array}
Mid Dec-IncIndexijkA[Index]xyzswap(i,k)z1yx+1swap(j,k)z1xy+1swap(i,j)x1zy+1swap(j,k)x1yz+1 \text{Mid Dec-Inc}\\ \begin{array}{c|cccc} \text{Index}&i&j&k\\ \text{A[Index]}&x&y&z\\ \hline \texttt{swap(i,k)}&z-1&y&x+1\\ \texttt{swap(j,k)}&z-1&x&y+1\\ \texttt{swap(i,j)}&x-1&z&y+1\\ \texttt{swap(j,k)}&x-1&y&z+1\\ \end{array}
Mid Inc-DecIndexijkA[Index]xyzswap(i,j)y1x+1zswap(j,k)y1z1x+2swap(i,j)z2yx+2swap(i,k)x+1yz1 \text{Mid Inc-Dec}\\ \begin{array}{c|cccc} \text{Index}&i&j&k\\ \text{A[Index]}&x&y&z\\ \hline \texttt{swap(i,j)}&y-1&x+1&z\\ \texttt{swap(j,k)}&y-1&z-1&x+2\\ \texttt{swap(i,j)}&z-2&y&x+2\\ \texttt{swap(i,k)}&x+1&y&z-1\\ \end{array}

有了这一点之后,我们考虑贪心算法:每次 aibia_i\ne b_i 时,都对 ai,ai+1a_i,a_{i+1} 进行加减操作,直到 ai=bia_i=b_i 为止。但是这样的话总操作次数可能来到 4N24N^2 可能会爆。因此一个优化是,对于 ai>bia_i\gt b_i,找一个 jj 使得 aj<bjj=arg maxk>iajbja_j\lt b_j\land j=\argmax_{k\gt i}|a_j-b_j|;对于 ai<bia_i\lt b_i 也是类似。这个剪枝就可以通过此题了。

另外值得注意的是要特殊考察 N=1,2N=1,2 时的情况。N=2N=2 时,b[]b[] 只有两种情况是 OK 的,(b0,b1)=(a0,a1)/(a11,a0+1)(b_0,b_1)=(a_0,a_1)/(a_1-1,a_0+1). 特判即可。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cassert>
#include <iostream>
#include <iterator>
#include <numeric>
#include <set>
#include <utility>
#include <vector>
#define all(x) (x).begin(), (x).end()
using vi = std::vector<int>;
using pii = std::pair<int, int>;

int main() {
int n;
std::cin >> n;

std::vector<int> a(n), b(n);
for (auto &x : a) std::cin >> x;
for (auto &x : b) std::cin >> x;

if (std::accumulate(all(a), 0) != std::accumulate(all(b), 0)) return std::cout << "No\n", 0;

if (n == 2) {
if (a[0] == b[0] && a[1] == b[1]) std::cout << "Yes\n0\n";
else if (a[1] - 1 == b[0] && a[0] + 1 == b[1]) std::cout << "Yes\n1\n1 2\n";
else std::cout << "No\n";
return 0;
}

// simulation
std::vector<pii> answer;
auto swap = [&](int i, int j) {
assert(0 <= i && i < j && j < n);
std::swap(a[i], a[j]);
a[i]--, a[j]++;
answer.emplace_back(i, j);
};

auto prefix_incdec = [&](int z, int x, int y) {
assert(0 <= z && z < x && x < y && y < n);
swap(x, y), swap(z, y), swap(z, x), swap(z, y);
};
auto prefix_decinc = [&](int z, int x, int y) {
assert(0 <= z && z < x && x < y && y < n);
swap(z, y), swap(z, x), swap(z, y), swap(x, y);
};
auto suffix_incdec = [&](int x, int y, int z) {
assert(0 <= x && x < y && y < z && z < n);
swap(x, y), swap(y, z), swap(x, z), swap(y, z);
};
auto suffix_decinc = [&](int x, int y, int z) {
assert(0 <= x && x < y && y < z && z < n);
swap(y, z), swap(x, z), swap(y, z), swap(x, y);
};
auto mid_incdec = [&](int x, int y, int z) {
assert(0 <= x && x < y && y < z && z < n);
swap(x, y), swap(y, z), swap(x, y), swap(x, z);
};
auto mid_decinc = [&](int x, int y, int z) {
assert(0 <= x && x < y && y < z && z < n);
swap(x, z), swap(y, z), swap(x, y), swap(y, z);
};
auto call = [&](int T, auto F, int x, int y, int z) {
assert(0 <= x && x < y && y < z && z < n);
for (int i = 0; i < T; i++) F(x, y, z);
};

for (int i = 0; i < n; i++) {
if (a[i] == b[i]) continue;

int j = i + 1, maxv = -1, rec = -1;
for (; j < n; j++)
if ((a[j] > b[j]) != (a[i] > b[i]) && abs(a[j] - b[j]) > maxv)
rec = j, maxv = abs(a[j] - b[j]);

j = rec;

if (a[i] > b[i]) {
int dec = a[i] - b[i];
if (i + 1 == j) {
if (i == 0) call(dec, suffix_decinc, i, j, n - 1);
else call(dec, prefix_decinc, 0, i, j);
} else call(dec, mid_decinc, i, j - 1, j);
} else {
int inc = b[i] - a[i];
if (i + 1 == j) {
if (i == 0) call(inc, suffix_incdec, i, j, n - 1);
else call(inc, prefix_incdec, 0, i, j);
} else call(inc, mid_incdec, i, j - 1, j);
}
}

if (answer.size() > 31000) std::cout << "No\n";
else {
std::cout << "Yes\n" << answer.size() << "\n";
for (auto [i, j] : answer) std::cout << i + 1 << " " << j + 1 << "\n";
}
}