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;
}
|
Vus the Cossack and Strings
出处：CF1186C
题目大意：给定二进制字符串 $a$ 和 $b$ ，请求出 $a$ 中所有长度为 $|b|$ 的子串中，与 $b$ 不同位置数量为偶数的个数。
数据范围： $1 \leq |a| \leq 10^6$
思路：结论题，看到这里必须 $O(1)$ 比较因此考虑什么前缀和之类的奇怪解法。
两个长度为 $b$ 的子串，则不同位置数为 $b1_i=0 \wedge b2_i=1$ 的位置数加上 $b1_i=1 \wedge b2_i=0$ 的位置数，那么注意到不同位置为偶数当且仅当它们的 $1$ 数量差为偶数个，就可以用前缀和做了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
void solve() {
string a, b;
cin >> a >> b;
int n1 = sz(a), n2 = sz(b);
int tem = 0;
rep(i, 0, n2 - 1) tem ^= (b[i] - '0');
int ans = 0;
int tem2 = 0;
vi pre(n1 + 1);
rep(i, 0, n1 - 1) {
tem2 ^= (a[i] - '0');
pre[i + 1] = tem2;
if (i < n2 - 1) continue;
int tem3 = pre[i + 1] ^ pre[i - n2 + 1];
if (tem3 ^ tem == 0) ans++;
}
cout << ans << endl;
return;
}
|
Lisa and the Martians
出处：CF1851F
题目大意：称一个整数为火星数，当且仅当它是一个非负整数且严格小于 $2^k$ ，给定 $n$ 个火星数 $a_1,\ldots,a_n$ ，需要选择一对数 $a_i,a_j$ ，计算 $(a_i \bigoplus x) \ and \ (a_j \bigoplus x)$ ，请选择合适的 $i,j,x$ ，使得这个结果最大。
数据范围： $2 \leq n \leq 2 \cdot 10^5,1 \leq k \leq 30$
思路：按位考虑这个式子，由于 $x$ 是可以随机控制的，那么只要 $a_i$ 和 $a_j$ 在当前位置相等就可取得 $1$ ，否则是 $0$ 。
联想到异或，那么就是求任意两个数异或的最小值，根据结论，我们有异或最小值一定在排序后相邻两个数之间，因此可以求出来，再根据上述反推 $x$ 即可。
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() {
ll n, k;
cin >> n >> k;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
vector<pii> ma;
rep(i, 0, n - 1) ma.emplace_back(a[i], i + 1);
ranges::sort(ma);
int idx = -1;
int maxx = INT_MAX;
rep(i, 0, n - 2) {
int tem = ma[i].first ^ ma[i + 1].first;
if (tem < maxx) {
idx = i;
maxx = tem;
}
}
cout << ma[idx].second << ' ' << ma[idx + 1].second << ' ';
int x = 0;
frep(i, k - 1, 0) {
int tem = (ma[idx].first >> i) & 1;
int tem2 = (ma[idx + 1].first >> i) & 1;
if (tem == tem2)
x += (1 ^ tem) * (1 << i);
else
continue;
}
cout << x << endl;
return;
}
|
Cyclic Operations
出处：CF1867D
题目大意：有一个初始全为 $0$ ，长度为 $n$ 的数组 $a$ ，问是否能通过任意次以下操作将 $a$ 变为 $b$ ：
每次操作选择一个长度为 $k$ 的数组 $l$ ，然后将每个 $a_{l_i}$ 变为 $l_{(i \pmod{k})+1}$ 。
数据范围： $1 \leq k \leq n \leq 10^5,1 \leq b_i \leq n$
思路：看到这种题很容易想到建图，于是可以把 $i$ 和 $a_i$ 连接起来，手玩样例后发现只需要判断是否存在长度为 $k$ 的环，但是操作区间可以互相覆盖，形成一个基环树森林，基环的长度为 $k$ ，注意当 $k=1$ 的时候需要特判，而找环只需要使用拓扑排序即可。
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
|
void solve() {
int n, k;
cin >> n >> k;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
if (k == 1) {
bool flag = true;
rep(i, 0, n - 1) {
if (a[i] - 1 != i) {
flag = false;
break;
}
}
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
return;
}
vvi ma(n);
vi deg(n);
rep(i, 0, n - 1) {
ma[i].push_back(a[i] - 1);
deg[a[i] - 1]++;
}
queue<int> q;
rep(i, 0, n - 1) {
if (deg[i] == 0) q.push(i);
}
while (!q.empty()) {
auto node = q.front();
q.pop();
for (int& p : ma[node]) {
if (--deg[p] == 0) q.push(p);
}
}
rep(i, 0, n - 1) {
if (deg[i] == 0) continue;
int cur = i;
int cnt = 0;
while (deg[cur] > 0) {
deg[cur] = 0;
cur = ma[cur][0];
cnt++;
}
if (cnt != k) {
cout << "NO" << endl;
return ;
}
}
cout << "YES" << endl;
return;
}
|
Increasing Subsequences
出处：CF1922E
题目大意：给定一个正整数 $x$ ，请构造一个长度不超过 $200$ 的整数数组，使得它恰好有 $X$ 个递增子序列，或者报告不存在这样的数组。
数据范围： $2 \leq X \leq 10^{18}$
思路：一开始其实是想分段构造的，然后发现死活过不去，因为好像会被卡的样子。
这里考虑到，对于一个递增序列来说，新增一个数，如果这个数是最小的，那么相当于递增序列数加一，如果这个数是最大的，那么递增序列数乘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
|
void solve() {
ll x;
cin >> x;
bitset<64> d(x);
int l = 0, r = 1;
bool flag = false;
vi a;
frep(i, 63, 0) {
if (!flag && d[i] == 0) continue;
if (!flag) {
flag = true;
continue;
}
if (d[i] == 0) {
a.push_back(r);
r++;
} else {
a.push_back(r);
r++;
a.push_back(l);
l--;
}
}
cout << sz(a) << endl;
for (int& p : a) cout << p << ' ';
cout << endl;
return;
}
|
Exam in MAC
出处：CF1935D
题目大意：给定一个大小为 $n$ 的集合和 $c$ ，求满足以下条件的整数对 $(x,y)$ 数量： $0 \leq x \leq y \leq c,x+y$ 不在集合 $s$ 中，同时 $y-x$ 也不在集合 $s$ 中。
数据范围： $1 \leq n \leq 3 \cdot 10^5, 1 \leq c \leq 10^9$
思路：显然是一个容斥题目，因此直接算出 $x+y$在集合 $s$ 中， $y-x$ 在集合 $s$ 中，以及两者都满足的数目，进行容斥即可。
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
|
void solve() {
ll n, c;
cin >> n >> c;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ranges::sort(a);
ll ans = (c + 1) * (c + 2) / 2;
for (auto& p : a) {
ans -= p / 2 + 1;
}
for (auto& p : a) {
ans -= (c - p + 1);
}
ll tem1 = 0, tem2 = 0;
for (auto& p : a) {
int tem = p % 2;
if (tem == 1) {
tem1++;
ans += tem1;
} else {
tem2++;
ans += tem2;
}
}
cout << ans << endl;
return;
}
|
