D
题目大意：给定一个整数序列 $a$，长度为 $n$，其中第 $i$ 个元素为 $a_i$。此外，还有两个整数 $x$ 和 $y$，且满足 $x \le y$。如果一对整数 $(i, j)$ 满足以下条件，则称其为有趣的： - $1 \le i < j \le n$； - 从序列 $a$ 中同时移除位置 $i$ 和 $j$ 的元素后，剩余元素的和在 $x$ 和 $y$ 之间。需要找出给定序列 $a$ 中有多少对这样的有趣整数组合。
数据范围：$1 \le t \le 10^4$，$3 \le n \le 2 \cdot 10^5$，$1 \le x \le y \le 2 \cdot 10^{14}$，$1 \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
| using i128 = __int128_t;
void solve() {
ll n, x, y;
cin >> n >> x >> y;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ranges::sort(a);
ll tot = 0;
rep(i, 0, n - 1) tot += a[i];
ll ans = 0;
rep(i, 0, n - 1) {
ll tem = tot - a[i];
int tem2 = lower_bound(a.begin(), a.begin() + i, tem - y) - a.begin();
int tem3 = upper_bound(a.begin(), a.begin() + i, tem - x) - a.begin();
ans += tem3 - tem2;
}
cout << ans << endl;
return;
}
|
E
题目大意：伯兰德最大的商店收到了一批圣诞树，并已有 $n$ 位顾客前来欲购这些树。在销售启动前，商店需要统一为每棵树定价。为了合理制定价格，商店掌握了关于每位顾客的一些信息。对于第 $i$ 位顾客，有两个已知整数 $a_i$ 和 $b_i$，它们定义了顾客的购物行为： - 如果价格不超过 $a_i$，顾客将购买一棵树并给定正面评价； - 如果价格超过 $a_i$ 但不超过 $b_i$，顾客仍会购买，但会留下负面评价； - 如果价格高于 $b_i$，则顾客将不会购买。在负面评价不超过 $k$ 条的前提下，需要帮助商店计算出最大的可能收益。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$0 \le k \le n$，$1 \le a_i \le 2 \cdot 10^9$，$1 \le b_i \le 2 \cdot 10^9$，$a_i < b_i$，$\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
| using i128 = __int128_t;
void solve() {
ll n, k;
cin >> n >> k;
vl a(n), b(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) cin >> b[i];
ranges::sort(a);
ranges::sort(b);
ll ans = 0;
rep(i, 0, n - 1) {
ll tem = a[i];
ll tem2 = ranges::lower_bound(a, tem) - a.begin();
ll tem3 = ranges::lower_bound(b, tem) - b.begin();
if (tem2 - tem3 <= k) ans = max(ans, (n - tem3) * tem);
}
rep(i, 0, n - 1) {
ll tem = b[i];
ll tem2 = ranges::lower_bound(a, tem) - a.begin();
ll tem3 = ranges::lower_bound(b, tem) - b.begin();
if (tem2 - tem3 <= k) ans = max(ans, (n - tem3) * tem);
}
cout << ans << endl;
return;
}
|
F
题目大意：考虑一副有 $n$ 张牌的情况。牌中的位置从上到下编号为 $1$ 到 $n$。小丑位于位置 $m$。$q$ 操作按顺序应用于牌组。在第 $i$ 次操作期间，您需要在位置 $a_i$ 处取出卡片并将其移动到牌堆的开头或末尾。您的任务是计算每次操作后小丑可以所处的不同位置的数量。
数据范围：$1 \le t \le 10^4$，$2 \le n \le 10^9$，$1 \le m \le n$，$1 \le q \le 2 \cdot 10^5$，$1 \le a_i \le n$，$\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
36
37
38
39
| using i128 = __int128_t;
void solve() {
ll n, m, q;
cin >> n >> m >> q;
vl a(q);
rep(i, 0, q - 1) cin >> a[i];
vl res(q);
vector<pll> tem;
tem.emplace_back(m, m);
rep(i, 0, q - 1) {
vector<pll> ntem;
for (auto& [x, y] : tem) {
if (y < a[i])
ntem.emplace_back(x, y + 1);
else if (x > a[i])
ntem.emplace_back(x - 1, y);
else {
ntem.emplace_back(1, 1);
ntem.emplace_back(n, n);
if (x < a[i]) ntem.emplace_back(x, a[i]);
if (a[i] < y) ntem.emplace_back(a[i], y);
}
}
sort(all(ntem), [&](const pll& x, const pll& y) { return x.first < y.first; });
tem.clear();
for (auto& [x, y] : ntem) {
if (tem.empty() || x > tem.back().second)
tem.emplace_back(x, y);
else
tem.back().second = max(tem.back().second, y);
}
ll ans = 0;
for (auto& [x, y] : tem) ans += y - x + 1;
res[i] = ans;
}
rep(i, 0, q - 1) cout << res[i] << ' ';
cout << endl;
return;
}
|
G
题目大意：设想一个游戏，场地是由 $1 \times 10^9$ 这样的方格组成的长条，每个方格用从 $1$ 到 $10^9$ 的编号表示。你要在这些方格中放置 $n$ 条蛇（编号为 $1$ 到 $n$）。起初，每条蛇仅占据一个方格，且每个方格不能被多条蛇同时占用。在完成初始放置之后，游戏正式开始。游戏会持续 $q$ 秒。在每一秒，有两种可能的事件： - 蛇 $s_i$ 变长：如果蛇 $s_i$ 占据了方格区间 $[l, r]$，它会向右扩展，变成占据区间 $[l, r+1]$； - 蛇 $s_i$ 缩短：如果蛇 $s_i$ 占据了方格区间 $[l, r]$，它会向左收缩，变成占据区间 $[l+1, r]$。每秒钟只会发生其中一种事件。
数据范围：$1 \le n \le 20$，$1 \le 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
36
37
38
39
40
41
| using i128 = __int128_t;
void solve() {
ll n, q, x;
char c;
cin >> n >> q;
int mask = (1LL << n);
vvl dp(mask, vl(n, LLONG_MAX / 3));
vl add(n), sub(n);
vl add2(n);
vvl dis(n, vl(n, 1));
rep(i, 0, q - 1) {
cin >> x >> c;
x--;
if (c == '+') {
add[x]++;
add2[x] = max(add2[x], add[x]);
rep(j, 0, n - 1) {
if (j == x) continue;
dis[x][j] = max(dis[x][j], add[x] - sub[j] + 1);
}
} else {
sub[x]++;
}
}
rep(i, 0, n - 1) dp[(1LL << i)][i] = 1;
dp[0][0] = 0;
rep(i, 1, mask - 1) {
rep(j, 0, n - 1) {
if (dp[i][j] == LLONG_MAX / 3) continue;
if (!((i >> j) & 1)) continue;
rep(v, 0, n - 1) {
if (i >> v & 1) continue;
dp[i | (1 << v)][v] = min(dp[i | (1 << v)][v], dp[i][j] + dis[j][v]);
}
}
}
ll ans = LLONG_MAX;
rep(i, 0, n - 1) ans = min(ans, dp[mask - 1][i] + add2[i]);
cout << ans << endl;
return;
}
|
