D
题目大意：Yousef 给了你一个包含 $2n$ 个整数的数组 $a$。数组中每个整数 $x \in [0, n-1]$ 恰好出现两次。需要找到一个子数组 $a_l, a_{l+1}, \dots, a_r$，该子数组是一个回文串 $^{\text{∗}}$，并且其 $\operatorname{mex}(a_l, a_{l+1}, \dots, a_r)$ $^{\text{†}}$ 最大。请输出该最大可能的值。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 10^5$，$0 \le a_i \le n-1$，$\sum 2n \le 2 \cdot 10^5$。
思路：很明显，为了让 $mex$ 最大，这个子数组显然要包含原来的0。
如果是包含两个0，找出它们的位置，然后验证中间是不是回文的，再考虑向两侧拓展得到的最大 $mex$ 值。
如果是包含一个0，就要以它为中心向两侧拓展，然后比较最大的 $mex$ 值即可。
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
| void solve() {
int n;
cin >> n;
vl a(2 * n);
rep(i, 0, 2 * n - 1) cin >> a[i];
int idx = -1, idx2 = -1;
rep(i, 0, 2 * n - 1) {
if (a[i] == 0) {
if (idx == -1)
idx = i;
else
idx2 = i;
}
}
int l = idx + 1, r = idx2 - 1;
bool flag = true;
while (l <= r) {
if (a[l] != a[r]) {
flag = false;
break;
}
l++, r--;
}
map<int, int> ma;
l = idx - 1, r = idx2 + 1;
while (l >= 0 && r <= 2 * n - 1) {
if (a[l] == a[r]) {
ma[a[l]]++;
l--, r++;
} else
break;
}
rep(i, idx, idx2) { ma[a[i]]++; }
int ans = 0;
if (flag) {
while (ma.count(ans)) ans++;
}
int ans2 = 0;
ma.clear();
l = idx, r = idx;
while (l >= 0 && r <= 2 * n - 1) {
if (a[l] == a[r]) {
ma[a[l]]++;
l--, r++;
} else
break;
}
while (ma.count(ans2)) ans2++;
ma.clear();
int ans3 = 0;
l = idx2, r = idx2;
while (l >= 0 && r <= 2 * n - 1) {
if (a[l] == a[r]) {
ma[a[l]]++;
l--, r++;
} else
break;
}
while (ma.count(ans3)) ans3++;
cout << max({ans, ans2, ans3}) << endl;
return;
}
|
E
题目大意：Yousef 有 $n$ 列方块并排竖立。第 $i$ 列包含 $a_i$ 个完全相同的单元方块垂直堆叠而成。最初，重力向下作用，因此每一列 $i$ 恰好包含 $a_i$ 个方块，这些方块分别处于高度 $1, 2, \dots, a_i$。突然间，重力转向右侧。每个方块会在保持原有高度不变的前提下，尽可能水平向右滑动。方块不能穿过或重叠在其它方块上。最终配置将唯一由初始高度决定。
在重力转向之前，可以进行至多一次操作：选择一个 $a_i$ ，令 $a_i=a_i-1$ ，也可以不进行任何操作。
请找出该情况下，重力转向后可能移动的方块的最大数量。
数据范围：$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
| void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ll ans = 0;
ll tem = 0;
rep(i, 0, n - 1) tem += a[i];
vl suf(n + 1, INT_MAX);
frep(i, n - 1, 0) suf[i] = min(suf[i + 1], a[i]);
rep(i, 0, n - 1) ans += 1LL * suf[i];
ll ans2 = ans;
map<ll, ll> ma;
rep(i, 0, n - 1) {
if (ma.count(a[i])) ans2 = min(ans2, ans - ma[a[i]]);
ma[suf[i]]++;
}
cout << tem - min(ans, ans2) << endl;
return;
}
|
F
题目大意：Yousef 有 $n$ 列立方体并排竖立。第 $i$ 列包含 $a_i$ 个完全相同的单位立方体，垂直堆叠。起初重力作用向下，因此每一列 $i$ 中恰好有 $a_i$ 个立方体，分别位于高度 $1,2,\dots,a_i$。突然，重力方向转向右侧。每个立方体会在保持原有高度的前提下，朝右侧水平滑动至能到达的最右位置。立方体不能越过或重叠其它立方体。最终立方体的分布由初始高度唯一确定。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$1 \le a_i \le n$，$\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
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
| template <typename T = long long>
class Tree {
vector<T> tree;
public:
// 构造函数：初始化大小为 n 的树状数组，初始所有元素值为 val（外部表现为 0-based）
Tree(int n, T val = 0) : tree(n + 1) {
for (int i = 1; i <= n; i++) {
tree[i] += val;
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
}
}
}
// 构造函数：使用给定的 vector 在 O(N) 时间内快速初始化建树
Tree(const vector<T>& data) {
int n = data.size();
tree.resize(n + 1);
for (int i = 1; i <= n; i++) {
tree[i] += data[i - 1]; // data是 0-based
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
}
}
}
// 单点修改：将 0-based 下标 i 处的元素增加 val
void add(int i, T val = 1) {
for (++i; i < tree.size(); i += i & (-i)) {
tree[i] += val;
}
}
// 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
T pre(int i) const {
T res = 0;
for (++i; i > 0; i &= i - 1) {
res += tree[i];
}
return res;
}
// 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
T query(int l, int r) const {
if (r < l) {
return 0;
}
return pre(r) - pre(l - 1); // 当 l=0 时, pre(-1) 会合理地返回 0
}
// 树上二分查找：返回满足前缀和 >= val 的最小 0-based 下标
int lower_bound(T val) const {
int w = bit_width(tree.size() - 1);
int res = 0;
T s = 0;
for (int i = w - 1; i >= 0; i--) {
int nxt = res + (1 << i);
if (nxt < tree.size() && tree[nxt] + s < val) {
res += (1 << i);
s += tree[nxt];
}
}
return res; // 返回 0-based 下标：内部 1-based 下标为 res + 1，因此 0-based 为 res
}
};
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ll maxx = *max_element(all(a));
Tree<ll> tree(maxx + 1);
Tree<ll> tree2(maxx + 1);
ll ans = 0;
ll tem = 0;
rep(i, 0, n - 1) {
ll tem2 = tree2.query(a[i] + 1, maxx);
ll tem3 = tree.query(a[i] + 1, maxx);
ans += tem3 - tem2 * a[i];
tree.add(a[i], a[i]);
tree2.add(a[i], 1);
}
ll ans2 = ans;
Tree<ll> tree3(maxx + 1);
Tree<ll> tree4(maxx + 1);
rep(i, 0, n - 1) { tree4.add(a[i], 1); }
rep(i, 0, n - 1) {
ll tem2 = tree3.query(a[i], maxx);
ll tem3 = tree4.query(0, a[i] - 1);
ans2 = max(ans2, ans + tem2 - tem3);
tree3.add(a[i], 1);
tree4.add(a[i], -1);
}
cout << max(ans, ans2) << endl;
return;
}
|
G
题目大意：Yousef 有一个数组 $a$，里面装着 $n$ 个正整数。他定义了一个针对长度为 $|c| \ge 3$ 的数组 $c$ 的“缩减操作”： - 选一个下标 $i$（满足 $1 \lt i \lt |c|$），条件是 $c_{i-1} + c_{i+1} \gt c_i$。- 用一个整数 $x = c_{i-1} - c_i + c_{i+1}$ 替换掉三元组 $\{c_{i-1}, c_i, c_{i+1}\}$。新整数 $x$ 就占据原来三元组的位置，数组长度因此缩短了 $2$。如果一个数组能通过零次或多次这样的操作，最终缩减成只有一个元素，我们就称它是好数组。注意，长度为 $1$ 的数组永远是好数组。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^9$，$\sum n \le 2\times10^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
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
100
101
102
103
104
105
106
107
108
109
| template <typename T = long long>
class Tree {
vector<T> tree;
public:
// 构造函数：初始化大小为 n 的树状数组，初始所有元素值为 val（外部表现为 0-based）
Tree(int n, T val = 0) : tree(n + 1) {
for (int i = 1; i <= n; i++) {
tree[i] += val;
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
}
}
}
// 构造函数：使用给定的 vector 在 O(N) 时间内快速初始化建树
Tree(const vector<T>& data) {
int n = data.size();
tree.resize(n + 1);
for (int i = 1; i <= n; i++) {
tree[i] += data[i - 1]; // data是 0-based
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
}
}
}
// 单点修改：将 0-based 下标 i 处的元素增加 val
void add(int i, T val = 1) {
for (++i; i < tree.size(); i += i & (-i)) {
tree[i] += val;
}
}
// 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
T pre(int i) const {
T res = 0;
for (++i; i > 0; i &= i - 1) {
res += tree[i];
}
return res;
}
// 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
T query(int l, int r) const {
if (r < l) {
return 0;
}
return pre(r) - pre(l - 1); // 当 l=0 时, pre(-1) 会合理地返回 0
}
// 树上二分查找：返回满足前缀和 >= val 的最小 0-based 下标
int lower_bound(T val) const {
int w = bit_width(tree.size() - 1);
int res = 0;
T s = 0;
for (int i = w - 1; i >= 0; i--) {
int nxt = res + (1 << i);
if (nxt < tree.size() && tree[nxt] + s < val) {
res += (1 << i);
s += tree[nxt];
}
}
return res; // 返回 0-based 下标：内部 1-based 下标为 res + 1，因此 0-based 为 res
}
};
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl pre(n);
pre[0] = a[0];
rep(i, 1, n - 1) {
if (i % 2 == 1)
pre[i] = pre[i - 1] - a[i];
else
pre[i] = pre[i - 1] + a[i];
}
vl tem;
for (ll& p : pre) tem.push_back(p);
tem.push_back(0);
auto sorted = tem;
ranges::sort(sorted);
sorted.erase(unique(all(sorted)), sorted.end());
int m = sz(sorted);
Tree<ll> tree(m);
Tree<ll> tree2(m);
int tem2 = ranges::lower_bound(sorted, 0) - sorted.begin();
tree.add(tem2, 1);
ll ans = 0;
rep(i, 0, n - 1) {
if (i % 2 == 0) {
int tem2 = ranges::lower_bound(sorted, pre[i]) - sorted.begin();
ll tem3 = tree.query(0, tem2 - 1);
ans += tem3;
tree2.add(tem2, 1);
} else {
int tem2 = ranges::lower_bound(sorted, pre[i]) - sorted.begin();
ll tem3 = tree2.query(tem2 + 1, m - 1);
ans += tem3;
tree.add(tem2, 1);
}
}
cout << ans << endl;
return;
}
|
H
题目大意：Yousef 得到了一棵 $n$ 个顶点的树 $^{\text{∗}}$，顶点编号为 $1$ 到 $n$。设 $S$ 为给定树的所有叶子节点 $^{\text{†}}$ 的集合（该集合由原始树确定，不会变化）。Yousef 重复如下操作，直到未被选择的顶点数不超过 $1$： - 从 $S$ 中选出两个未被选择过的不同顶点 $u, v$。- 将 $d(u, v)$ 加入总代价，其中 $d(u, v)$ 表示 $u$ 和 $v$ 间的简单路径上的边数。- 将 $u$ 和 $v$ 标记为已选择。需要帮助 Yousef 计算在操作结束后，可能达到的最小总代价。
数据范围：$1 \le t \le 10^4$，$3 \le n \le 2 \cdot 10^5$，$1 \le u, v \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
54
55
56
57
58
59
60
61
62
63
64
65
| void solve() {
int n, x, y;
cin >> n;
vvi ma(n);
vi deg(n);
rep(i, 1, n - 1) {
cin >> x >> y;
ma[x - 1].push_back(y - 1);
ma[y - 1].push_back(x - 1);
}
int tem = 0;
vector<bool> vis(n, false);
rep(i, 0, n - 1) {
if (sz(ma[i]) == 1) vis[i] = true;
tem += vis[i];
}
vi cnt(n);
vi dep(n);
vi tem2(n);
vi tem3(n);
ll ans = 0;
int idx = -1;
rep(i, 0, n - 1) {
if (!vis[i]) {
idx = i;
break;
}
}
auto dfs = [&](this auto&& dfs, int x, int pa, int d) -> int {
dep[x] = d;
if (vis[x]) {
tem2[x] = 1;
ans++;
return 1;
}
int tem3 = 0;
for (int& p : ma[x]) {
if (p == pa) continue;
int tem4 = dfs(p, x, d + 1);
tem3 += tem4;
}
tem2[x] = tem3;
if (x != idx && tem2[x] % 2 == 1) ans++;
return tem3;
};
dfs(idx, -1, 0);
if (tem % 2 == 0) {
cout << ans << endl;
return;
}
auto dfs2 = [&](this auto&& dfs2, int x, int pa) -> void {
if (x != idx) tem3[x] = tem3[pa] + tem2[x] % 2;
for (int& p : ma[x]) {
if (p == pa) continue;
dfs2(p, x);
}
};
dfs2(idx, -1);
ll ans2 = LLONG_MAX;
rep(i, 0, n - 1) {
if (vis[i]) ans2 = min(ans2, ans + dep[i] - 2 * tem3[i]);
}
cout << ans2 << endl;
return;
}
|
