B
题目大意：给定一个包含 $n$ 个正整数的数组 $a_1, a_2, \ldots, a_n$ 和一个正整数 $k$。在一次操作中，你可以对每个 $a_i$ 加上 $0$ 或 $k$，即选择另一个数组 $b_1, b_2, \ldots, b_n$，其中每个 $b_i$ 要么是 $0$，要么是 $k$，然后将 $a_i$ 更新为 $a_i + b_i$，对于所有 $1 \le i \le n$。注意，对于数组 $b$ 的每一个元素，你可以选择不同的值。需要在不超过 $k$ 次操作内，使得 $\gcd(a_1, a_2, \ldots, a_n) > 1$ $^{\text{∗}}$。可以证明，永远存在合法解。请输出经过操作后的最终数组。
数据范围：$1 \le t \le 1000$，$1 \le n \le 10^5$，$1 \leq k \leq 10^9$，$1 \le a_i \le 10^9$，$\sum n \le 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| using i128 = __int128_t;
void solve() {
ll n, k;
cin >> n >> k;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl b(n);
rep(i, 0, n - 1) {
ll tem = a[i] % (k + 1);
b[i] = a[i] + tem * k;
}
rep(i, 0, n - 1) cout << b[i] << ' ';
cout << endl;
return;
}
|
C
题目大意：一个数组被称为“好数组”，如果对于其任意长度不少于 $2$ 的子数组，位于原数组偶数下标（下标从 $1$ 开始计数）的元素之和大于等于位于原数组奇数下标的元素之和。数组 $[0,2,4,1]$ 不是好数组，因为在其子数组 $[2,4,1]$ 中，原数组的偶数下标元素是 $2$（下标 $2$）和 $1$（下标 $4$），唯一的奇数下标元素是 $4$（下标 $3$）。由于 $2 + 1 < 4$，因此该子数组不满足条件。给定一个长度为 $n$ 的非负整数数组 $a_1,a_2,\ldots,a_n$。每次操作，你可以将数组中的任意一个元素减 $1$，但所有元素必须保持非负。需要求出使得数组 $a$ 变成“好数组”所需的最少操作次数。
数据范围：$1 \le t \le 10^4$，$2 \le n \le 2 \cdot 10^5$，$0 \le a_i \le 10^9$，$\sum n \le 2 \cdot 10^5$。
思路：
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
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
if (n == 2) {
cout << max(0LL, a[0] - a[1]) << endl;
return;
}
ll ans = 0;
for (ll i = 2; i <= n - 1; i += 2) {
ll tem = a[i - 2] + a[i];
if (tem > a[i - 1]) {
ll tem2 = tem - a[i - 1];
ans += tem2;
ll tem3 = min(tem2, a[i]);
a[i] -= tem3;
a[i - 2] -= tem2 - tem3;
}
}
if (n % 2 == 0 && a[n - 2] > a[n - 1]) ans += a[n - 2] - a[n - 1];
cout << ans << endl;
return;
}
|
E
题目大意：这是一个交互题。你有 $n$ 个盒子，编号从 $1$ 到 $n$。这些盒子外观完全相同，但每个盒子有一个隐藏的力量值 $a_i$，其取值为 $1$ 或 $2$。需要确定每个盒子的力量值。为此，你可以进行如下实验：最初，第 $i$ 个盒子被放置在数轴上的坐标 $i$ 处（$1 \le i \le n$）。你可以进行以下两种类型的操作： - “swap $x$” （$1 \le x \le n - 1$）：交换当前位于坐标 $x$ 和 $x + 1$ 的两个盒子。注意，这个变化是永久的，会影响之后所有的操作。- “throw $x$” （$1 \le x \le n$）：向当前位于坐标 $x$ 的盒子扔一个球。
数据范围：$1 \le t \le 500$，$2 \le n \le 1000$，$\sum n \le 1000$。
思路：
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
| using i128 = __int128_t;
void swap(ll r) {
cout << "swap " << r << '\n';
cout.flush();
return;
}
ll th(ll r) {
cout << "throw " << r << '\n';
cout.flush();
ll op;
cin >> op;
return op;
}
void report(vl& res) {
cout << "! ";
rep(i, 1, sz(res) - 1) cout << res[i] << ' ';
cout << '\n';
cout.flush();
}
void solve() {
ll n;
cin >> n;
vl res(n + 1);
vl dp(n + 3);
ll op;
op = th(n - 1);
res[n - 1] = (op == 2 ? 1 : 2);
swap(n - 1);
op = th(n - 1);
res[n] = (op == 2 ? 1 : 2);
dp[n] = 1, dp[n - 1] = op;
for (ll i = n - 2; i >= 1;) {
if (dp[i + 1] != dp[i + 2]) {
op = th(i);
if (op == dp[i + 1] + 1)
res[i] = 1;
else
res[i] = 2;
dp[i] = op;
i--;
} else {
if (i == 1) {
swap(1);
op = th(2);
if (op == dp[3] + 1)
res[1] = 1;
else
res[1] = 2;
break;
} else {
op = th(i - 1);
if (op == dp[i + 1] + 2)
res[i - 1] = 1;
else
res[i - 1] = 2;
swap(i - 1);
op = th(i - 1);
if (op == dp[i + 1] + 2)
res[i] = 1;
else
res[i] = 2;
dp[i] = dp[i + 1] + 1;
dp[i - 1] = op;
i -= 2;
}
}
}
report(res);
return;
}
|
