D
题目大意：农夫 John 有一台割草机，最开始是关闭的。他还有 $n$ 块田地，第 $i$ 块田地上有 $a_i$ 朵蒲公英。他将以任意顺序访问所有田地，每块田地恰好访问一次。John 的割草机似乎有自己的想法。在访问每一块田地之前，割草机会检查该田地上的蒲公英数量是奇数还是偶数。
数据范围：$1 \leq t \leq 10^4$，$1 \leq n \leq 2 \times 10^5$，$1 \leq a_i \leq 10^9$，$\sum n \le 2 \times 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
| void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl cnt0;
vl cnt1;
rep(i, 0, n - 1) {
if (a[i] % 2 == 0)
cnt0.push_back(a[i]);
else
cnt1.push_back(a[i]);
}
if (cnt1.empty()) {
cout << 0 << endl;
return;
}
ll ans = 0;
for (auto& p : cnt0) ans += p;
sort(all(cnt1));
int m = sz(cnt1);
rep(i, m / 2, m - 1) ans += cnt1[i];
cout << ans << endl;
return;
}
|
E
题目大意：农夫 John 有一个包含 $n$ 个正整数的数组 $a$ 和一个整数 $k$。记 $a[l, r]$ 表示数组 $a$ 的一个子数组$^{\text{∗}}$。他执行如下过程来独立判断子数组 $a[l, r]$ 是否为“awesome”： - FJ 最初有 $k$ 个空的多重集，编号从 $1$ 到 $k$。
数据范围：$1 \leq t \leq 1000$，$2 \leq k \leq n \leq 2 \cdot 10^5$，$1 \leq a_i \leq n$，$\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
26
27
| void solve() {
ll n, k;
cin >> n >> k;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
map<ll, ll> ma;
rep(i, 0, n - 1) ma[a[i]]++;
for (auto& [x, y] : ma) {
if (y % k != 0) {
cout << 0 << endl;
return;
}
}
ll l = 0;
ll ans = 0;
map<ll, ll> ma2;
rep(r, 0, n - 1) {
ma2[a[r]]++;
while (ma2[a[r]] > ma[a[r]] / k) {
ma2[a[l]]--;
l++;
}
ans += 1LL * r - l + 1;
}
cout << ans << endl;
return;
}
|
F
题目大意：农夫约翰有 $n$ 个数组 $a_1, a_2, \ldots, a_n$，它们的长度可能不同。他将把这些数组堆叠在一起，形成一个有 $n$ 行的网格。数组按左对齐放置，可以按任意顺序叠放。接下来，重力会生效。任何不在最底行，且下方没有元素的单元格会向下掉落一行。这个过程会不断重复，直到没有符合条件的单元格为止。在所有可能的堆叠顺序中，输出经过重力作用后，字典序最小的底行。
数据范围：$1 \leq t \leq 1000$，$1 \leq n \leq 2 \cdot 10^5$，$1 \leq k_i \leq 2 \cdot 10^5$，$1 \leq a_{i_j} \leq 2 \cdot 10^5$，$\sum n \le 2 \cdot 10^5$，$\sum k_i \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
26
27
28
29
30
31
32
33
34
35
36
| void solve() {
ll n;
cin >> n;
vl l(n);
vvl ma(n);
rep(i, 0, n - 1) {
cin >> l[i];
ma[i].resize(l[i]);
rep(j, 0, l[i] - 1) cin >> ma[i][j];
}
ll maxx = *max_element(all(l));
vl ans(maxx);
ll tem = 0;
auto check = [&](ll x, ll y) -> bool {
ll tem2 = min(sz(ma[x]), sz(ma[y]));
rep(i, tem, tem2 - 1) {
if (ma[x][i] < ma[y][i]) return true;
if (ma[x][i] > ma[y][i]) return false;
}
return l[x] <= l[y];
};
while (tem < maxx) {
ll idx = -1;
rep(i, 0, n - 1) {
if (l[i] <= tem) continue;
if (idx == -1 || check(i, idx)) {
idx = i;
}
}
rep(i, tem, l[idx] - 1) ans[i] = ma[idx][i];
tem = l[idx];
}
rep(i, 0, maxx - 1) cout << ans[i] << ' ';
cout << endl;
return;
}
|
G
题目大意：Bessie 在地上发现了一个长度为 $n$ 的数组 $a$。在数组旁边似乎还有一张手写的便签，看起来是 Farmer John 写的。便签上写着： “亲爱的 Bessie，请帮帮我！设 $f(a)$ 表示在区间 $[1, n)$ 内使得 $\gcd(a_1, a_2, \ldots, a_k) > \gcd(a_1, a_2, \ldots, a_{k+1})$ 的最大的整数 $k$，如果不存在这样的 $k$，则为 $0$。” Bessie 决定帮助 FJ。她定义 $g(a)$ 表示所有 $a$ 的重排中 $f(a)$ 的最大值。Bessie 不仅打算找到 $g(a)$，还打算对于 $a$ 的每个前缀 $p$ 求出 $g(p)$ 的值。
数据范围：$1 \leq t \leq 10^4$，$1 \leq n \leq 2 \cdot 10^5$，$1 \leq a_i \leq n$，$\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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| constexpr int MX = 2e5 + 5;
vector<int> divisors[MX];
auto init = [] {
for (int i = 1; i < MX; i++) {
for (int j = i; j < MX; j += i) {
divisors[j].push_back(i);
}
}
return 0;
}();
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl ma(n + 1);
vl res(n);
int tem = 0;
rep(i, 0, n - 1) {
if (i > 0) res[i] = res[i - 1];
int tem2;
if (tem == 0) {
tem = a[i];
tem2 = a[i];
} else
tem2 = __gcd(1LL * tem, a[i]);
if (tem2 < tem) {
res[i] = max(res[i], 1LL * i);
}
tem = tem2;
for (auto& p : divisors[a[i]]) {
ma[p]++;
if (ma[p] < i + 1) res[i] = max(res[i], ma[p]);
}
}
rep(i, 0, n - 1) cout << res[i] << ' ';
cout << endl;
return;
}
|
