B
题目大意：定义任意数组 $b$ 的分数为 $b$ 的长度减去其中不同元素的数量。- 数组 $[1, 1, 1]$ 的分数为 $2$，因为它长度为 $3$ 且只有 $1$ 个不同元素（$1$）。- 空数组的分数为 $0$。给定一个数组 $a$。需要最多一次移除一个非空的连续子数组。更正式地说，你最多可以执行以下操作一次： - 选择两个整数 $l$ 和 $r$（$1 \le l \le r \le n$） - 从 $a$ 中删除连续子数组 $[a_l,\ldots,a_r]$（即将 $a$ 替换为 $[a_1,\ldots,a_{l - 1},a_{r + 1},\ldots,a_n]$） 请输出一个操作，使得操作后 $a$ 的分数最大。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$1 \le a_i \le 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
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
map<ll, ll> ma;
rep(i, 0, n - 1) { ma[a[i]]++; }
ll ans = n - sz(ma);
ll l = -1, r = -1;
ll ans2 = 0;
int i = 0;
int res = -1;
while (i <= n - 1) {
if (ma[a[i]] != 1) i++;
int j = i;
while (j <= n - 1 && ma[a[j]] == 1) j++;
if (j - i > ans2) {
ans2 = j - i;
res = i;
}
i = j;
}
if (ans2 == 0)
cout << 0 << endl;
else
cout << res + 1 << ' ' << res + ans2 << endl;
return;
}
|
C
题目大意：你有一个长度为 $n$ 的数组 $a$，其中元素均为非零整数。初始时你有 $0$ 枚硬币，你将重复以下操作直到 $a$ 变为空： - 设当前数组 $a$ 的大小为 $m$。选择一个整数 $i$（$1 \le i \le m$），获得 $|a_i|$ $^{\text{∗}}$ 枚硬币，然后： - 如果 $a_i < 0$，则将 $a$ 替换为 $[a_1,a_2,\ldots,a_{i - 1}]$（即删除从 $a_i$ 开始的后缀）； - 否则，将 $a$ 替换为 $[a_{i + 1},a_{i + 2},\ldots,a_m]$（即删除以 $a_i$ 结尾的前缀）。请计算最终你能获得的最大硬币数量。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$-10^9 \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
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
if (n == 1) {
cout << abs(a[0]) << endl;
return;
}
vl pre(n);
vl suf(n);
pre[0] = (a[0] >= 0 ? a[0] : 0);
rep(i, 1, n - 1) pre[i] = pre[i - 1] + (a[i] >= 0 ? a[i] : 0);
suf[n - 1] = (a[n - 1] < 0 ? -a[n - 1] : 0);
frep(i, n - 2, 0) suf[i] = suf[i + 1] + (a[i] < 0 ? -a[i] : 0);
ll ans = 0;
rep(i, 0, n - 2) { ans = max(ans, pre[i] + suf[i + 1]); }
ans = max(ans, pre[n - 1]);
ans = max(ans, suf[0]);
cout << ans << endl;
return;
}
|
D
题目大意：有 $n$ 个史莱姆排成一行，第 $i$ 个史莱姆的体重为 $w_i$。当史莱姆 $i$ 满足 $w_i \geq w_j$ 时，它可以吃掉史莱姆 $j$；之后，史莱姆 $j$ 会消失，史莱姆 $i$ 的体重将变为 $w_i \oplus w_j$ $^{\text{∗}}$。史莱姆国王希望进行一个参数为 $x$ 的实验，步骤如下： - 在行的最右端（第 $n$ 个史莱姆之后）新增一个体重为 $x$ 的史莱姆。- 这个新史莱姆会不断尝试吃掉左侧相邻的史莱姆（如果可能的话），并移动到被吃掉的史莱姆的位置。当左侧没有史莱姆或其左侧史莱姆的体重大于自身时，该过程停止。（此过程中不会有其他史莱姆被吃掉） - 该实验的得分为被吃掉的史莱姆总数。
数据范围：$1 \le t \le 10^4$，$1 \le n, q \le 2 \cdot 10^5$，$1 \le w_i < 2^{30}$，$1 \le x < 2^{30}$，$\sum n \le 2 \cdot 10^5$，$\sum q \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
| using i128 = __int128_t;
void solve() {
ll n, q, x;
cin >> n >> q;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl pre(n);
pre[0] = a[0];
rep(i, 1, n - 1) pre[i] = pre[i - 1] ^ a[i];
vvl cnt(n + 1, vl(31, -1));
rep(i, 0, n - 1) {
rep(j, 0, 30) cnt[i + 1][j] = cnt[i][j];
int tem = 63 - __builtin_clzll(a[i]);
rep(j, 0, tem) { cnt[i + 1][j] = i; }
}
rep(i, 0, q - 1) {
cin >> x;
ll ans = 0;
ll cur = n;
while (cur > 0 && x > 0) {
int tem = 63 - __builtin_clzll(x);
ll tem2 = cnt[cur][tem];
x = x ^ pre[cur - 1];
x = x ^ (tem2 < 0 ? 0 : pre[tem2]);
ans += cur - tem2 - 1;
cur = tem2;
if (cur < 0 || a[cur] > x) break;
x = x ^ a[cur];
ans++;
}
cout << ans << ' ';
}
cout << endl;
return;
}
|
E
题目大意：Steve 有一个排列 $p$ 和一个数组 $c$，它们的长度均为 $n$。Steve 希望对排列 $p$ 进行排序。Steve 有无限多的彩色沙块，他用这些沙块发明了一种基于物理的排序方法，称为重力排序。具体来说，对 $p$ 进行重力排序的步骤如下： - 对于所有满足 $1 \le i \le n$ 的 $i$，在所有 $1 \le j \le p_i$ 的位置 $(i, j)$ 上放置一个颜色为 $c_i$ 的沙块。这里，位置 $(x, y)$ 表示从上往下第 $x$ 行、从左往右第 $y$ 列的格子。- 对整个数组施加向下的重力，使所有沙块尽可能下落。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$1 \le p_i \le n$，$1 \le c_i \le 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| using i128 = __int128_t;
const ll MOD = 998244353;
class UnionFind {
public:
int cc; // 连通块个数
vector<int> fa;
vector<int> siz; // 集合大小
UnionFind(int n) : fa(n), siz(n, 1), cc(n) { ranges::iota(fa, 0); }
int get(int x) {
if (fa[x] != x) fa[x] = get(fa[x]);
return fa[x];
}
bool is_same(int x, int y) { return get(x) == get(y); }
bool merge(int from, int to) {
int x = get(from), y = get(to);
if (x == y) return false;
fa[x] = y;
siz[y] += siz[x];
cc--;
return true;
}
int get_size(int x) { // 查询x所在集合大小
return siz[get(x)];
}
};
void solve() {
ll n;
cin >> n;
vl p(n), c(n);
rep(i, 0, n - 1) cin >> p[i], p[i]--;
rep(i, 0, n - 1) cin >> c[i];
vl id(n);
rep(i, 0, n - 1) id[p[i]] = i;
UnionFind u(n);
rep(i, 0, n - 2) {
if (c[i] == c[i + 1]) u.merge(i, i + 1);
}
ll ans = 1;
vl pre(n, -1), suf(n, -1);
rep(i, 0, n - 1) { pre[i] = i - 1, suf[i] = i + 1; }
suf[n - 1] = -1;
rep(i, 0, n - 1) {
ll tem = id[i];
ans = ans * u.get_size(tem) % MOD;
u.siz[u.get(tem)]--;
ll pre2 = pre[tem], suf2 = suf[tem];
if (pre2 != -1) suf[pre2] = suf2;
if (suf2 != -1) pre[suf2] = pre2;
if (pre2 != -1 && suf2 != -1 && c[pre2] == c[suf2]) u.merge(pre2, suf2);
}
cout << ans << endl;
return;
}
|
