Messager in MAC
出处：CF1935C(Div.2)
题目大意：给定 $a_1,\ldots a_n$ 和 $b_1,\ldots,b_n$ ，要选出 $p_1,\ldots,p_k$ ，所有的 $p_i$ 是独立的，要使 $\sum\limits_{i=1}^{k}a_{p_i}+\sum\limits_{i=1}^{k-1}|b_{p_i}-b_{p_{i+1}}| \leq l$ ，求 $k$ 的最大值，注意当 $k=1$ 时，上述式子的取值为 $a_i$ 。
数据范围： $1 \leq n \leq 2000, 1 \leq n^2 \leq 4 \cdot 10^6,1 \leq a_i,b_i \leq 10^9$
思路：易见对于同样的数，当 $b_1,\ldots,b_k$ 单调时，原式的值取得最小，即 $|b_{k}-b_1|$ 。
然后观察到这个数据范围，应该是 $O(N^2)$ 或者 $O(N^2 \log n)$ 的。
考虑枚举首尾两个元素，然后对中间的进行归并，但这样最差复杂度是 $O(n^3 \log n)$ ，不可行。
因此，考虑贪心地优化，首先按照 $b$ 排序，然后考虑滑动窗口的思路，枚举左端点逐步往右扩展，使用mset自动排序，然后弹出的之后也不可能用到，因为后续枚举的尾值肯定比这个大，能接受的 $a$ 只会小于等于这里能接受的 $a$ ，时间复杂度 $O(n^2 \log n)$ 。
这道题没有独立做出，说明贪心和ds功底比较差。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
void solve() {
int n, l;
cin >> n >> l;
vector<pii> a(n);
rep(i, 0, n - 1) cin >> a[i].first >> a[i].second;
sort(all(a), [&](const pii &x, const pii &y) { return x.second < y.second; });
int ans = 0;
rep(i, 0, n - 1) {
multiset<int> s;
ll cur = 0;
rep(j, i, n - 1) {
s.insert(a[j].first);
cur += a[j].first;
while (!s.empty() && cur + 1LL * a[j].second - a[i].second > l) {
int tem = *s.rbegin();
cur -= 1LL * tem;
s.erase(--s.end());
}
ans = max(ans, sz(s));
}
}
cout << ans << endl;
return;
}
|
Unfair Game
出处：CF1955F(Div.3)
题目大意：Alice和Bob在对着一堆不超过4的数玩游戏，每次若它们的异或和为0则Bob获胜，反之Alice获胜，现在Eve负责每次删除一个数字（空的时候不会进行游戏），问Bob最多能赢几局？
数据范围： $0 \leq p_i \leq 200, 1 \leq i \leq 4$
思路：简单的贪心，思路这里不讲了，可以达到 $O(1)$ ，注意到 $4$ 是独立的，且 $1,2,3$ 必须同奇偶即可。
还有一种DP思路，就是先把4单独考虑，然后枚举状态 $dp_{i,j,k}$ ，这里 $i,j,k$ 分别是 $1 \sim 3$ 的个数，它们可以从 $dp_{i-1,j,k},dp_{i,j-1,k},dp_{i,j,k-1}$ 转移过来，于是有答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void solve() {
vi p(4);
rep(i, 0, 3) cin >> p[i];
int ans = 0;
if (p[0] > 0 && p[1] > 0 && p[2] > 0) {
sort(p.begin(), p.begin() + 3);
int tem = 0;
tem += p[0];
tem += (p[1] - (p[1] - p[0]) % 2 - p[0]) / 2 + (p[2] - (p[2] - p[0]) % 2 - p[0]) / 2 + p[3] / 2;
ans = max(ans, tem);
tem = 0;
if (p[0] % 2 == 1 && p[1] % 2 == 1 && p[2] % 2 == 1) tem++;
tem += p[0] / 2 + p[1] / 2 + p[2] / 2 + p[3] / 2;
ans = max(ans, tem);
} else
ans = p[0] / 2 + p[1] / 2 + p[2] / 2 + p[3] / 2;
cout << ans << endl;
}
|
Magic Will Save the World
出处：CF1862F(Div.3)
题目大意：每秒可以产生 $w$ 的火能量和 $f$ 的水能量，每个怪物需要 $s_i$ 个火能量或者水能量来杀死（不能混用），问最少需要多少秒（假设杀死怪物不需要时间）。
数据范围： $1 \leq n \leq 100, 1 \leq w,f \leq 10^9, 1 \leq s_i \leq 10^4$
思路：首先考虑二分答案，然后观察到这好像是一个两个背包的模型，因此只需要让遍历的其中一个背包塞得最多，再考虑另一个背包塞不塞得下即可。
同时，这里上界的取法很有意思，可以尽量减少复杂度。
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
|
void solve() {
int w, f;
cin >> w >> f;
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
ll tot = 0;
rep(i, 0, n - 1) tot += 1LL * a[i];
int l = 1, r = tot / max(w, f) + 1, mid;
int ans = 0;
auto check = [&](int mid) -> bool {
vector<bool> dp(min(1LL * tot, 1LL * mid * w) + 1, false);
dp[0] = true;
int m = sz(dp);
rep(i, 0, n - 1) {
if (a[i] > m - 1) continue;
frep(j, m - 1, a[i]) dp[j] = dp[j] | dp[j - a[i]];
}
ll tem = 1LL * mid * f;
ll tem2 = 0;
frep(i, m - 1, 0) {
if (dp[i]) {
tem2 = i;
break;
}
}
return 1LL * tot - tem2 <= tem;
};
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) {
r = mid - 1;
ans = mid;
} else
l = mid + 1;
}
cout << ans << endl;
return;
}
|
Inversion Value of a Permulation
出处： CF2145D(Edu)
题目大意： 给定一个长度为 $n$ 的排列，定义它的反转值为至少包含一个逆序对的子段的数量，请构造出反转值为 $k$ 的排列，或者报告这样的排列不存在。
数据范围： $2 \leq n \leq 30, 0 \leq k \leq \frac{n(n-1)}{2}$
思路：考虑正难则反，首先考虑构造没有逆序对的子段数量为 $\frac{n(n+1)}{2}-k$ ，然后观察到每段单调递增的子段的贡献是 $\frac{l(l+1)}{2}$ ，而所有单调递增的子段长度之和为 $n$ （只有一个元素也是），因此考虑采用可行式背包求解。
接着，再用原来的子段，贪心还原即可。
这题参考了题解。
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
|
void solve() {
int n, k;
cin >> n >> k;
int nn = n;
k = n * (n + 1) / 2 - k;
vvi dp(n + 1, vi(n * (n + 1) / 2 + 1));
dp[0][0] = 1;
vi res;
rep(i, 1, n) {
rep(j, i, n) {
rep(v, i * (i + 1) / 2, n * (n + 1) / 2) { dp[j][v] = dp[j][v] | dp[j - i][v - i * (i + 1) / 2]; }
}
}
if (!dp[n][k]) {
cout << 0 << endl;
return;
}
while (k > 0) {
rep(i, 1, n) {
if (dp[n - i][k - i * (i + 1) / 2]) {
rep(j, n - i + 1, n) res.push_back(j);
n -= i, k -= i * (i + 1) / 2;
break;
}
}
}
for (int& p : res) cout << p << ' ';
cout << endl;
return;
}
|
Andrey and Escape from Capygrad
出处：CF1859D(Div.2)
题目大意：有 $n$ 个传送门，每个传送门分布在 $[l_i,r_i]$ ，且可以传送到 $[a_i,b_i],l_i \leq a_i \leq b_i \leq r_i$ ， 所有传送门都可以被任意次使用，现在给出 $q$ 个查询，请输出从 $x$ 出发，可以到达的最大坐标是多少。
数据范围： $1 \leq l_i \leq a_i \leq b_i \leq r_i \leq 10^9, 1 \leq n \leq 2 \cdot 10^5, 1 \leq q \leq 2 \cdot 10^5,1 \leq x \leq 10^9$
思路：首先考虑区间合并，这道题是LC56的典题，如果没有复习的可以去复习一下。
考察合并 $[l_i,b_i]$ ，即这之间的点可以任意到达右边界，为什么不考察 $(b_i,r_i]$ ？因为如果 $[l_i,b_i]$ 合并的结果到不了 $r_i$ ，那此时往回走是完全不划算的事情，反之自然会包括这一段，因此只需要考察前面的。
最后，用二分查找搜索当前查询在哪个区间即可。
这题参考了题解。
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
|
void solve() {
int n, a, b, c, d, q;
cin >> n;
vector<pii> ma;
rep(i, 0, n - 1) {
cin >> a >> b >> c >> d;
ma.emplace_back(a, d);
}
ranges::sort(ma);
vector<pii> res;
for (auto& p : ma) {
if (!res.empty() && res.back().second >= p.first) {
res.back().second = max(res.back().second, p.second);
} else
res.push_back(p);
}
cin >> q;
rep(i, 0, q - 1) {
cin >> a;
auto x = ranges::upper_bound(res, make_pair(a, INT_MAX));
if (x == res.begin())
cout << a << ' ';
else {
if ((--x)->second >= a)
cout << x->second << ' ';
else
cout << a << ' ';
}
}
cout << endl;
return;
}
|
Rating System
出处：CF1845D(Edu)
题目大意：现在正在开发评级系统，一开始的评级为 $0$ ，每次会变化 $a_i$ 的评级，对于固定整数 $k$ ，若已经达到过 $k$ ，则后续不会降到 $k$ 以下，现在要求确定 $k$ 的值，使得最后的值最大。
数据范围： $1 \leq n \leq 3 \cdot 10^5, -10^9 \leq a_i \leq 10^9, a_i \not ={0}$
思路：首先贪心地考虑，如果一段使得已经达到的评级降下来，那么它会被抵消成0，如果后续还有一段使得它降下来，那么这整段都要被抵消掉（由于前缀和的原因，可以思考一下）。
于是，为了使最后的值最多，需要抵消掉最多的部分，也就是总数减去最小子段和（注意这个子段和必须要是负数），然后再还原方案即可。
其实1600-1800的题，基本都是一个小trick/一个小思维就能转到学过的东西。
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
|
void solve() {
int n;
cin >> n;
vi 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] + 1LL * a[i];
vl dp(n, LLONG_MAX / 3);
dp[0] = a[0];
ll ans = LLONG_MAX;
int idx = -1;
rep(i, 1, n - 1) {
dp[i] = min(dp[i], 1LL * a[i]);
dp[i] = min(dp[i], dp[i - 1] + 1LL * a[i]);
}
rep(i, 0, n - 1) {
if (dp[i] < ans) {
ans = dp[i];
idx = i;
}
}
if (ans >= 0) {
cout << 0 << endl;
return;
}
int cur = idx;
while (cur >= 0) {
if (dp[cur] == 1LL * a[cur]) {
if (cur != 0)
cout << pre[cur - 1] << endl;
else
cout << 0 << endl;
return;
}
cur--;
}
return;
}
|
Colored Balls
出处：CF1954D(Edu)
题目大意：给定 $n$ 个颜色，每个颜色有 $a_i$ 个球，定义一个颜色组的值为，这些颜色的球能分配到的最小组数，每组最多包含两个球，且这两个球不能是同一个颜色的，现在要求求出所有 $2^n$ 个颜色组的值总和，由于结果太大，需要模998244353。
数据范围： $1 \leq n \leq 5000, \sum\limits_{i=1}^{n}a_i \leq 5000$
思路：这里注意到，所有 $a_i$ 的值之和不超过5000，所以大概率是在这里做文章。
接着，看到这个条件非常明显是绝对众数，那么只需要枚举是绝对众数的数，以及它不作为绝对众数的情况。
考虑先排序再递推，记录之前子集能构成的和及其数量，计数如果当前颜色被选了，它作为绝对众数和非绝对众数的情况，时间复杂度 $O(n \cdot 5000)$ 。
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
|
const int MOD = 998244353;
void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
ranges::sort(a);
ll ans = 0;
vl dp(5001, 0);
dp[0] = 1;
rep(i, 0, n - 1) {
rep(j, 0, a[i]) {
ans += 1LL * dp[j] * a[i] % MOD;
ans %= MOD;
}
rep(j, a[i] + 1, 5000) {
ans += 1LL * (j + a[i] + 1) / 2 * dp[j] % MOD;
ans %= MOD;
}
auto ndp = dp;
rep(j, 0, 5000 - a[i]) {
dp[j + a[i]] += ndp[j] % MOD;
dp[j + a[i]] %= MOD;
}
}
cout << ans << endl;
return;
}
|