B
题目大意：本题与 G 题不同，在本题中您必须在最多一次的操作后输出前缀最小值的最小和。给定一个整数 $n$ 与一个长度为 $n$ 的数组 $a(0\leq a_i \leq n)$，可以执行以下操作： - 选择两个整数 $i,j(i 数据范围：$t(1\leq t\leq 10^4)$，$n(2\leq n\leq2\times10^5)$。 思路： 题目大意：Alice 有一个数组 $a$，包含 $n$ 个正整数。这个数组满足一个优美的性质：对于每个 $1\leq i\leq n-1$，$a_i$ 整除 $a_{i+1}$。Bob 看到 Alice 优美的数组，心生嫉妒。为了给她捣乱，Bob 先生成了一个长度为 $n$ 的数组 $b$，使得对于每个 $1\leq i\leq n$ 都有 $b_i=a_i$。然后，他会选择一个正整数 $x$，从 $b$ 中选出一些元素（可以不选，可以全选），给这些元素乘上 $x$。形式化地，他选择了一个（可空）子集 $S\subseteq \{1,2,\cdots,n\}$，对于每个 $i\in S$，令 $b_i:= b_i\cdot x$。 数据范围：$1\leq t\leq 2\cdot 10^5$，$2\leq n\leq 6\cdot 10^5$，$1\leq b_i\leq 10^9$，$\sum n \le 6\cdot 10^5$。 思路： 题目大意：你被给定了一个长度为 $n$ 的序列 $a$ 以及一个数 $k$，你可以进行如下操作任意次： - 选择两个整数 $l$ 和 $r$ $(1 \le l \le r \le |a|)$ 满足 $r-l+1 \geq k$。- 然后，选择一个整数 $i$ $(l\leq i \leq r)$ 使得 $a_i$ 是 $[a_l,a_{l+1},\ldots,a_r]$ 中第 $k$ 小的数。如果有多个满足条件 $i$，你可以任选其一。- 最后，从 $a$ 中删除 $a_i$，连接序列的剩余部分。求出原序列是否能在若干次操作后变为回文串 $^{\text{∗}}$。 数据范围：$1 \le t \le 10^4$，$1 \leq k \leq n \leq 2\cdot 10^5$，$1 \leq a_i \leq n$。 思路： 题目大意：给定一个由 $n$ 个正整数组成的数组 $a$。你可以进行如下操作： - 选择一个大小为 $n$ 的数组 $b$，满足以下条件： - 对于每个 $1 \leq i \leq n$，有 $0 \leq b_i \leq a_i$； - 存在某个下标 $1 \leq i < n$，使得 $b_1+b_2+\ldots+b_i = b_{i+1}+b_{i+2}+\ldots+b_n$，即前缀长度为 $i$ 的和等于后缀长度为 $n-i$ 的和。- 然后，对每个 $1 \leq i \leq n$，用 $a_i-b_i$ 替换 $a_i$。需要将所有元素都变为 $0$。需要求出最少需要多少次操作。 数据范围：$1 \le t \le 10^4$，$2 \leq n \leq 5\cdot 10^4$，$1 \leq a_i \leq 10^{12}$，$\sum n \le 5\cdot 10^4$。 思路： 题目大意：这是简单版本，$n \le 100$。从空数组开始，可以多次选择 $s,r$，把 $[r,r+1,\ldots,s,1,2,\ldots,r-1]$ 追加到末尾。给定 $n$ 和若干限制 $a_i \ne x$，统计满足所有限制的数组构造方案数。 数据范围：$1 \le t \le 100$，$1 \leq n \leq 100, 0 \leq m \leq \min(5000, n^2)$，$1 \leq i,x \leq n$，$\sum n \le 100$，$\sum m \le 5000$。 思路： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ll mixx = LLONG_MAX;
ll ans = 0;
rep(i, 0, n - 1) {
mixx = min(mixx, a[i]);
ans += mixx;
}
ll ans2 = ans;
if (a[0] < a[1])
cout << min(ans, 2 * a[0]) << endl;
else
cout << min(ans, a[0] + a[1]) << endl;
return;
}
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl res;
rep(i, 1, n - 1) {
if (a[i] % a[i - 1] == 0) continue;
ll tem = __gcd(a[i], a[i - 1]);
res.push_back(a[i - 1] / tem);
}
ll tem2 = 1;
auto lcm = [&](ll x, ll y) -> ll {
ll tem3 = __gcd(x, y);
return x / tem3 * y;
};
for (auto& p : res) {
tem2 = lcm(tem2, p);
}
cout << tem2 << endl;
return;
}
D
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
using i128 = __int128_t;
void solve() {
ll n, k;
cin >> n >> k;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
if (k == 1) {
cout << "YES" << endl;
return;
}
auto b = a;
ranges::sort(b);
ll tem = b[k - 2];
vl c;
rep(i, 0, n - 1) {
if (a[i] <= tem) c.push_back(a[i]);
}
int m = sz(c);
int tem2 = m - (k - 1);
int l = 0, r = m - 1;
while (l <= r) {
if (c[l] == c[r]) {
l++;
r--;
continue;
}
if (tem2 == 0 || (c[l] != tem && c[r] != tem)) {
cout << "NO" << endl;
return;
}
if (c[l] == tem)
l++;
else
r--;
tem2--;
}
cout << "YES" << endl;
return;
}
E
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
98
99
using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ll tot = 0;
rep(i, 0, n - 1) tot += a[i];
if (tot % 2 == 1) {
cout << -1 << endl;
return;
}
ll maxx = *max_element(all(a));
if (2 * maxx > tot) {
cout << -1 << endl;
return;
}
vvl res;
vl premax1(n), premax2(n);
vl preidx1(n), preidx2(n);
premax1[0] = a[0], premax2[0] = LLONG_MIN;
preidx1[0] = 0, preidx2[0] = -1;
rep(i, 1, n - 1) {
premax1[i] = premax1[i - 1], premax2[i] = premax2[i - 1];
preidx1[i] = preidx1[i - 1], preidx2[i] = preidx2[i - 1];
if (a[i] >= premax1[i]) {
premax2[i] = premax1[i], preidx2[i] = preidx1[i];
premax1[i] = a[i], preidx1[i] = i;
} else if (a[i] >= premax2[i]) {
premax2[i] = a[i], preidx2[i] = i;
}
}
vl sufmax1(n), sufmax2(n);
vl sufidx1(n), sufidx2(n);
sufmax1[n - 1] = a[n - 1], sufmax2[n - 1] = LLONG_MIN;
sufidx1[n - 1] = n - 1, sufidx2[n - 1] = -1;
frep(i, n - 2, 0) {
sufmax1[i] = sufmax1[i + 1], sufmax2[i] = sufmax2[i + 1];
sufidx1[i] = sufidx1[i + 1], sufidx2[i] = sufidx2[i + 1];
if (a[i] >= sufmax1[i]) {
sufmax2[i] = sufmax1[i], sufidx2[i] = sufidx1[i];
sufmax1[i] = a[i], sufidx1[i] = i;
} else if (a[i] >= sufmax2[i]) {
sufmax2[i] = a[i], sufidx2[i] = i;
}
}
ll pre2 = 0;
rep(i, 0, n - 2) {
pre2 += a[i];
ll tem = (pre2 - (tot - pre2));
if (tem == 0) {
cout << 1 << endl;
rep(i, 0, n - 1) cout << a[i] << ' ';
cout << endl;
return;
}
}
pre2 = 0;
rep(i, 0, n - 2) {
pre2 += a[i];
ll tem = (pre2 - (tot - pre2));
if (tem > 0 && tem % 2 == 0) {
vl tem2 = a;
int idx = -1;
ll tem3 = tem / 2;
vl tem4(n);
rep(j, 0, i) {
if (tem3 == 0) break;
ll te = min(tem2[j], tem3);
tem3 -= te;
tem2[j] -= te;
tem4[j] = te;
idx = j;
}
tem3 = tem / 2;
rep(j, idx + 1, i) {
if (tem3 == 0) break;
ll te = min(tem2[j], tem3);
tem3 -= te;
tem2[j] -= te;
tem4[j] = te;
idx = i;
}
res.push_back(tem2);
res.push_back(tem4);
break;
}
}
if (res.empty()) {
cout << -1 << endl;
return;
}
cout << sz(res) << endl;
rep(i, 0, sz(res) - 1) {
for (auto& p : res[i]) cout << p << ' ';
cout << endl;
}
return;
}
F1
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
using i128 = __int128_t;
const ll MOD = 998244353;
void solve() {
ll n, m, x, y;
cin >> n >> m;
vvl ma(n + 1, vl(n + 1));
rep(i, 0, m - 1) {
cin >> x >> y;
ma[x - 1][y] = 1;
}
vvl dp(n + 1, vl(n + 1));
dp[0][0] = 1;
rep(i, 1, n) {
rep(j, 0, i - 1) {
rep(v, 1, i - j) {
bool flag = true;
rep(l, 0, i - j - 1) {
if (ma[j + l][(v + l - 1) % (i - j) + 1]) {
flag = false;
break;
}
}
if (!flag) continue;
rep(l, 0, n) {
if (l > 0 && v == l + 1) continue;
int tem = (v == 1 ? (i - j) : 0);
dp[i][tem] = (dp[i][tem] + dp[j][l]) % MOD;
}
}
}
}
ll ans = 0;
rep(i, 0, n) { ans = (ans + dp[n][i]) % MOD; }
cout << ans << endl;
return;
}