B
题目大意：在学习了艺术平衡树之后，Lizhous 遇到了如下问题。给定一个由 $n$ 个整数组成的数组 $a$。需要对 $a$ 顺序执行恰好 $m$ 次操作。每次操作包含两个步骤。具体来说，在第 $i$ 次操作中，给定一个整数 $x_i$，你将： - 首先，选择一个中心下标 $u$ 和一个非负长度 $y$，使得区间 $[u-y, u+y]$ 完全包含在 $[1, n]$ 内（即 $u-y \ge 1$ 且 $u+y \le n$）。对于每个 $1 \le i \le y$，交换 $a_{u-i}$ 和 $a_{u+i}$ 的元素。- 然后，标记下标为 $x_i$ 的元素。如果该元素已被标记，则不做任何操作。注意，标记是加在元素上的，而不是下标上。
数据范围：$1 \le t \le 10^4$，$1 \le n, m \le 10^5$，$-10^9 \le a_i \le 10^9$，$1 \le x_i \le n$，$\sum n \le 10^5$，$\sum m \le 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
| void solve() {
int n, m;
cin >> n >> m;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl b(m);
rep(i, 0, m - 1) {
cin >> b[i];
b[i]--;
}
ll ans2 = 0;
rep(i, 0, n - 1) ans2 += a[i];
vl tem1;
vl tem2;
rep(i, 0, n - 1) {
if (i % 2 == 0)
tem1.push_back(a[i]);
else
tem2.push_back(a[i]);
}
sort(all2(tem1));
sort(all2(tem2));
int l = 0, r = 0;
ll ans = 0;
rep(i, 0, m - 1) {
if (b[i] % 2 == 0) {
if (l < sz(tem1) && tem1[l] >= 0) {
ans += tem1[l];
l++;
} else if (l == 0 && sz(tem1) > 0) {
ans += tem1[l];
l++;
}
} else {
if (r < sz(tem2) && tem2[r] >= 0) {
ans += tem2[r];
r++;
} else if (r == 0 && sz(tem2) > 0) {
ans += tem2[r];
r++;
}
}
}
cout << ans2 - ans << endl;
return;
}
|
C
题目大意：给定一个长度为奇数 $n$ 的正整数数组 $a$。需要将该序列划分为若干长度为奇数且中位数相同的子数组。需要找到最多能划分出多少个这样的子数组。更正式地说，需要找到一个长度为 $(p+1)$ 的严格递增序列 $k$，满足 $k_1=1$ 且 $k_{p+1}=n+1$，并且对于每个 $1 \le i \le p$，序列 $[a_{k_i}, a_{k_i+1}, \ldots, a_{k_{i+1}-1}]$ 的中位数都相同。同时，$k_i$ 与 $k_{i+1}$ 的奇偶性需要不同。需要求出 $p$ 的最大可能值。
数据范围：$1 \le t \le 1000$，$1 \le n < 5000$，$1 \le a_i \le 10^9$，$\sum n^2 \le 5000^2$。
思路：
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
| struct Mid {
vi cnt;
int res = 0;
int cnt2 = 0;
int l = 0;
Mid(int x) : cnt(x, 0) {}
void insert(int x) {
l++;
cnt[x]++;
if (l == 1) {
res = x;
cnt2 = 1;
return;
}
if (x <= res) cnt2++;
int tem = (l + 1) / 2;
while (res > 0 && cnt2 - cnt[res] >= tem) {
cnt2 -= cnt[res];
res--;
}
while (res < sz(cnt) - 1 && cnt2 < tem) {
res++;
cnt2 += cnt[res];
}
}
int get() { return res; }
};
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
int ans = 1;
auto sorted = a;
ranges::sort(sorted);
sorted.erase(unique(all(sorted)), sorted.end());
rep(i, 0, n - 1) {
auto x = ranges::lower_bound(sorted, a[i]);
a[i] = x - sorted.begin();
}
int m = sz(sorted);
vvi dp(n + 1, vi(m, -1));
rep(i, 0, m - 1) dp[0][i] = 0;
rep(i, 0, n - 1) {
Mid tem(m);
rep(j, i, n - 1) {
tem.insert(a[j]);
if ((j - i + 1) % 2 == 0) continue;
int mid = tem.get();
if (dp[i][mid] != -1) dp[j + 1][mid] = max(dp[j + 1][mid], dp[i][mid] + 1);
}
}
rep(i, 0, m - 1) { ans = max(ans, dp[n][i]); }
cout << ans << endl;
return;
}
|
D
题目大意：给定一个长度为 $n$ 的整数数组 $a$。对于一个排列 $p$，其一个逆序对 $(i, j)$ 的「值」被定义为 $\sum\limits_{k=i}^{j-1} a_k$。一个排列的美丽值等于其所有逆序对值的总和。需要构造一个长度为 $n$ 的排列 $p$，使其美丽值最大。注： ∗ 在长度为 $n$ 的排列 $p$ 中，一个逆序对定义为一对下标 $(i, j)$，满足 $1 \leq i < j \leq n$ 且 $p_i > p_j$。$p = [1]$ 时没有逆序对。
数据范围：$1\le t\le 10^4$，$1\le n\le 2\times 10^5$，$-10^9\leq a_i\leq 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
| void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vector<pll> pre(n);
vi res(n);
rep(i, 1, n - 1) {
pre[i].first = pre[i - 1].first + a[i - 1];
pre[i].second = i;
}
sort(all(pre), [&](const pll& x, const pll& y) { return x.first < y.first; });
rep(i, 0, n - 1) { res[pre[i].second] = n - i; }
rep(i, 0, n - 1) cout << res[i] << ' ';
cout << endl;
return;
}
|
E
题目大意：这是一个交互题。有两个隐藏的整数 $k$ 和 $c$，其中 $k\in \{1,2,3\}$，$1\le c\le 2^n-1$。注意 $c\ne 0$。在任何交互之前，需要向评测器给定一个不超过 $2^n-1$ 的非负整数 $a$。评测器会用 $a$ 作为集合 $S$ 的初始元素，也就是说，初始时 $S=\{a\}$。接下来，你最多可以进行 $n+3$ 次如下两种类型的查询： 1. 选择一个整数 $x$，$0\leq x\le 2^n-1$。
数据范围：$1\le t\le 10^4$，$2\leq n\leq 60$，$\sum n \le 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
| void init(ll a) {
cout << a << '\n';
cout.flush();
return;
}
ll insert(ll l) {
cout << "I " << l << '\n';
cout.flush();
ll op;
cin >> op;
return op;
}
ll query(ll l) {
cout << "Q " << l << '\n';
cout.flush();
ll op;
cin >> op;
return op;
}
void report(ll a, ll b) {
cout << "A " << a << ' ' << b << '\n';
cout.flush();
}
void solve() {
int n;
cin >> n;
ll k = 0, c = 0;
init((1LL << n) - 1);
int tem = insert(0);
if (tem == 1) {
c = (1LL << n) - 1;
int tem2 = insert((1LL << n) - 1);
if (tem2 == 1)
k = 2;
else
k = 3;
report(k, c);
return;
} else {
int tem2 = query(1);
if (tem2 == 1) {
k = 1;
if (n == 1)
c = 1;
else {
int tem3 = tem;
rep(i, 0, n - 1) {
int tem4 = insert(1LL << i);
if (tem4 == tem3 + 1) c += (1LL << i);
tem3 = tem4;
}
}
report(k, c);
return;
} else {
ll l = 1, r = (1LL << n) - 2;
while (l < r) {
ll mid = (l + r + 1) / 2;
ll tem3 = query(mid);
if (tem3 == 2)
l = mid;
else
r = mid - 1;
}
ll tem3 = insert(l);
if (tem3 == 2)
k = 2;
else
k = 3;
report(k, l);
return;
}
}
return;
}
|
