B
题目大意：你打算购买 $n$ 个商品，价格分别为 $a_1, a_2, \ldots, a_n$。你可以选择以下两种方式购买每件商品： - 逐个购买商品 $i$，需支付 $a_i$ 个硬币； - 使用一张折扣券，将其作为团购的一部分购买。你有 $k$ 张面值分别为 $b_1, b_2, \ldots, b_k$ 的折扣券。面值为 $x$ 的折扣券可以让你选中恰好 $x$ 个商品，并且只需支付其中价格最高的 $x - 1$ 个商品，价格最低的那一个免费。你可以将其理解为团购中最便宜的一件商品免费。每个商品最多只能被纳入一个折扣团购组，无论它是否是免费那件。同一张折扣券最多只能用一次。需要计算，购买所有 $n$ 个商品的最小总花费是多少。
数据范围：$1 \le t \le 10^4$，$1 \le n, k \le 2 \cdot 10^5$，$1 \le a_i \le 10^9$，$1 \le b_i \le n$，$\sum n \le 2 \cdot 10^5$，$\sum k \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
| using i128 = __int128_t;
void solve() {
ll n, k;
cin >> n >> k;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ranges::sort(a);
vl b(k);
rep(i, 0, k - 1) cin >> b[i];
ranges::sort(b);
ll r = n - 1;
ll ans = 0;
rep(i, 0, k - 1) {
if (r + 1 < b[i]) break;
frep(j, r, r - b[i] + 2) { ans += a[j]; }
r -= b[i];
}
rep(i, 0, r) ans += a[i];
cout << ans << endl;
return;
}
|
C
题目大意：给定一棵 $n$ 点树，每条边 $(u,v)$ 关联两个权值 $x,y$。需要给每个点分配一个排列值 $p_i$，边的贡献取决于端点排列值大小关系，求任意一个使所有边贡献和最大的排列。
数据范围：$1 \le t \le 10^4$，$2 \le n \le 2 \cdot 10^5$，$1 \le u < v \le n$，$1 \le x, y \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
24
25
26
27
28
29
30
31
32
| using i128 = __int128_t;
void solve() {
ll n, x, y, u, v;
cin >> n;
vvl ma(n);
vl deg(n);
rep(i, 1, n - 1) {
cin >> u >> v >> x >> y;
if (x > y)
ma[v - 1].push_back(u - 1), deg[u - 1]++;
else
ma[u - 1].push_back(v - 1), deg[v - 1]++;
}
queue<int> q;
rep(i, 0, n - 1) {
if (!deg[i]) q.push(i);
}
vl tem;
vl res(n);
while (!q.empty()) {
auto node = q.front();
q.pop();
tem.push_back(node);
for (auto& p : ma[node]) {
if (--deg[p] == 0) q.push(p);
}
}
rep(i, 0, n - 1) res[tem[i]] = i + 1;
rep(i, 0, n - 1) cout << res[i] << ' ';
cout << endl;
return;
}
|
D1
题目大意：这是本题的简单版本。不同之处在于本版本中 $n \le 300$。只有在你解决了本题所有版本后，才能进行 Hack。一个序列 $b_1, b_2, \ldots, b_k$ 被称为“好”的，如果存在对每个下标 $i$ 的一种红色或蓝色染色方案，使得对于任意 $i < j$ 且 $b_i > b_j$ 的下标对，$i$ 和 $j$ 的颜色不同。给定一个序列 $a_1, a_2, \ldots, a_n$。请计算该序列中“好”子序列（包括空子序列$^{\text{∗}}$）的个数。
数据范围：$1 \le t \le 100$，$1 \leq n \leq 300$，$1 \le a_i \le n$，$\sum n \le 300$。
思路：
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
| using i128 = __int128_t;
const ll MOD = 1e9 + 7;
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;
tree[i] %= MOD;
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
tree[nxt] %= MOD;
}
}
}
// 构造函数：使用给定的 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
tree[i] %= MOD;
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
tree[nxt] %= MOD;
}
}
}
// 单点修改：将 0-based 下标 i 处的元素增加 val
void add(int i, T val = 1) {
val = (val % MOD + MOD) % MOD;
for (++i; i < tree.size(); i += i & (-i)) {
tree[i] += val;
tree[i] %= MOD;
}
}
// 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
T pre(int i) const {
if (i < 0) return 0;
T res = 0;
for (++i; i > 0; i &= i - 1) {
res += tree[i];
res %= MOD;
}
return res;
}
// 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
T query(int l, int r) const {
if (r < l) {
return 0;
}
return (pre(r) - pre(l - 1) + MOD) % MOD; // 当 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() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vector<Tree<ll>> tree1;
vector<Tree<ll>> tree2;
rep(i, 0, n) tree1.push_back(Tree<ll>(n + 1));
rep(i, 0, n) tree2.push_back(Tree<ll>(n + 1));
tree1[0].add(0, 1);
tree2[0].add(0, 1);
ll ans = 1;
rep(i, 0, n - 1) {
vl tem1(n + 1);
vl tem2(n + 1);
rep(j, 0, a[i]) tem1[j] = tree1[j].query(j, a[i]);
rep(j, a[i] + 1, n) tem2[j] = tree2[j].query(0, a[i]);
rep(j, 0, a[i]) {
tree1[j].add(a[i], tem1[j]);
tree2[a[i]].add(j, tem1[j]);
ans = (ans + tem1[j]) % MOD;
}
rep(j, a[i] + 1, n) {
tree1[a[i]].add(j, tem2[j]);
tree2[j].add(a[i], tem2[j]);
ans = (ans + tem2[j]) % MOD;
}
}
cout << ans << endl;
return;
}
|
D2
题目大意：这是该问题的困难版本。与其它版本的区别在于本版本中 $n \leq 2000$。只有在你解出了所有版本之后才可以进行 Hack。我们称一个序列 $b_1, b_2, \ldots, b_k$ 是“好”的，如果存在一种对每个下标 $i$ 染为红色或蓝色的方式，使得对于每对满足 $i < j$ 且 $b_i > b_j$ 的下标 $i,j$，$i$ 和 $j$ 的颜色不同。给定一个序列 $a_1, a_2, \ldots, a_n$，需要计算它的“好”子序列的数量，包括空子序列 $^\ast$。
数据范围：$1 \leq t \leq 100$，$1 \leq n \leq 2000$，$1 \leq a_i \leq n$，$\sum n \le 2000$。
思路：
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
| using i128 = __int128_t;
const ll MOD = 1e9 + 7;
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;
tree[i] %= MOD;
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
tree[nxt] %= MOD;
}
}
}
// 构造函数：使用给定的 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
tree[i] %= MOD;
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
tree[nxt] %= MOD;
}
}
}
// 单点修改：将 0-based 下标 i 处的元素增加 val
void add(int i, T val = 1) {
val = (val % MOD + MOD) % MOD;
for (++i; i < tree.size(); i += i & (-i)) {
tree[i] += val;
tree[i] %= MOD;
}
}
// 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
T pre(int i) const {
if (i < 0) return 0;
T res = 0;
for (++i; i > 0; i &= i - 1) {
res += tree[i];
res %= MOD;
}
return res;
}
// 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
T query(int l, int r) const {
if (r < l) {
return 0;
}
return (pre(r) - pre(l - 1) + MOD) % MOD; // 当 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() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vector<Tree<ll>> tree1;
vector<Tree<ll>> tree2;
rep(i, 0, n) tree1.push_back(Tree<ll>(n + 1));
rep(i, 0, n) tree2.push_back(Tree<ll>(n + 1));
tree1[0].add(0, 1);
tree2[0].add(0, 1);
ll ans = 1;
rep(i, 0, n - 1) {
vl tem1(n + 1);
vl tem2(n + 1);
rep(j, 0, a[i]) tem1[j] = tree1[j].query(j, a[i]);
rep(j, a[i] + 1, n) tem2[j] = tree2[j].query(0, a[i]);
rep(j, 0, a[i]) {
tree1[j].add(a[i], tem1[j]);
tree2[a[i]].add(j, tem1[j]);
ans = (ans + tem1[j]) % MOD;
}
rep(j, a[i] + 1, n) {
tree1[a[i]].add(j, tem2[j]);
tree2[j].add(a[i], tem2[j]);
ans = (ans + tem2[j]) % MOD;
}
}
cout << ans << endl;
return;
}
|
