B
题目大意：给定两个长度为 $n$ 的正整数数组 $a,b$ ，可以执行任意次数的以下操作：选择一个整数 $i$ 并交换 $a_i$ 和 $b_i$ ，请确认 $\max(a)+\sum\limits_{i=1}^{n}b_i$ 的最大值
数据范围： $1 \leq n \leq 10^5, 1 \leq a_i,b_i \leq 10^9$
思路：首先可以将式子化简为 $\sum\limits_{i=1}^{n}a_i+b_i-\sum\limits_{i=1}^{n-1}c_i$ ，这里 $c$ 是排序后的 $a$ 数组，从而可以发现，只需让 $a$ 的最小 $n-1$ 项最小，从而考虑到，对于 $a_i$ ，如果换能让它最小，那么必然是要换的，从而得出结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl b(n);
rep(i, 0, n - 1) cin >> b[i];
ll tem = 0, tem2 = 0;
rep(i, 0, n - 1) tem += a[i];
rep(i, 0, n - 1) tem2 += b[i];
ll maxx = LLONG_MIN;
ll tem3 = 0;
rep(i, 0, n - 1) {
maxx = max(maxx, min(a[i], b[i]));
tem3 += max(a[i], b[i]);
}
cout << tem3 + maxx << endl;
return;
}
|
C1
题目大意：给定一个长度为 $n$ 的非零数组 $a$ ，最多可以执行 $n$ 次以下操作，每次操作选择一个 $a_i,a_i>0$ ，然后对于 $1 \leq j \leq i$ ，使得 $a_j=-a_j$ ，请给出使 $a$ 的和最小的操作序列。
数据范围： $2 \leq n \leq 2 \cdot 10^5, -10^9 \leq a_i \leq 10^9$
思路：首先不难想到，要使 $a$ 的和最小，那么最优情况当然是让所有的 $a$ 都是负数，又由于操作对右边的数没有影响，因此考虑从右边倒着遍历，如果碰到 $a_i>0$ 就操作即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl res;
int tem = 0;
frep(i, n - 1, 0) {
int tem2 = (a[i] < 0);
if ((tem + tem2) % 2 == 0) {
tem++;
res.push_back(i + 1);
} else
continue;
}
cout << sz(res) << endl;
rep(i, 0, sz(res) - 1) cout << res[i] << ' ';
cout << endl;
return;
}
|
C2
题目大意：跟上题相同，但是要操作得出最大和。
数据范围：跟上题相同。
思路：这题赛时卡了非常久，我能说是做完DE再来做这个的吗哈哈哈。
思路跟上题有点像，受到样例启发，发现无法将全部的数都转化为正的，同时样例的操作顺序不一定是倒序，于是想到枚举某个分割点，这个点右侧的数都不变，左侧的数全部改成正的，当然，这个点自己因为操作了会变成负的。
于是可以枚举得到分割点的位置，下面的任务就是构造一种对应的操作顺序，使得左边全部变成正的。
然后，可以枚举一下每个数需要被反转次数的奇偶性，如果它跟它相邻的不相同，显然就是这个数要被操作了，然后再次考虑怎么构造这些要被操作的数的顺序。
观察到，很多时候想执行操作，但是如果朴素地从右往左操作，可能当前的数无法被翻，因此稍微思考一下，对被操作数的数目分奇偶考虑，两两配对，再微调即可。
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
|
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl res;
ll mixx = LLONG_MAX;
vl pre(n + 1);
vl suf(n + 2);
rep(i, 1, n) pre[i] = pre[i - 1] + abs(a[i - 1]);
frep(i, n, 1) suf[i] = suf[i + 1] + a[i - 1];
ll maxx = suf[1];
int idx = -1;
rep(i, 1, n) {
if (a[i - 1] > 0) {
if (pre[i - 1] - a[i - 1] + suf[i + 1] > maxx) {
maxx = pre[i - 1] - a[i - 1] + suf[i + 1];
idx = i;
}
}
}
if (idx == -1) {
cout << 0 << endl;
cout << endl;
return;
}
vl dp(n + 2);
rep(i, 1, idx - 1) dp[i] = (a[i - 1] < 0);
dp[idx] = 1;
vi tem;
rep(i, 1, n) {
if (dp[i] != dp[i + 1]) tem.push_back(i);
}
if (sz(tem) % 2 == 1) {
for (int i = 0; i <= sz(tem) - 2; i += 2) {
res.push_back(tem[i + 1]);
res.push_back(tem[i]);
}
} else {
res.push_back(tem[0]);
for (int i = 1; i <= sz(tem) - 2; i += 2) {
res.push_back(tem[i + 1]);
res.push_back(tem[i]);
}
}
res.push_back(tem[sz(tem) - 1]);
cout << sz(res) << endl;
rep(i, 0, sz(res) - 1) cout << res[i] << ' ';
cout << endl;
return;
}
|
D
题目大意：给定两个长度为 $n$ 的数组 $a$ 跟 $b$ ，每次可以选择小于当前数组长度的 $i$ ，取出 $a_i,a_{i+1},b_i,b_{i+1}$ ，排序后得到 $s_1,s_2,s_3,s_4$ ，将 $s_2$ 填回原来 $a_i,a_{i+1}$ 的位置， $s_3$ 填回原来 $b_i,b_{i+1}$ 的位置，请求出最后 $min(a_1,b_1)$ 的最大可能值。
数据范围： $1 \leq n \leq 10^5, 1 \leq a_i,b_i \leq 2 \cdot n$
思路：看到这个形式，显然会想到是二分答案。
那么，最后两个数都要大于等于 $mid$ ，说明他们经过消除后，都能大于等于 $mid$ ，而看到邻项消除题不难想到栈，于是考虑四个数消除后的结果。
不难想到，如果四个数中至多一个数大于等于 $mid$ ，那么最后得到的 $s_2,s_3$ ，还是小于等于 $mid$ ，而如果有两个数大于等于 $mid$ ，最后得到的是 $s_3>=mid, s_2<mid$ ，而如果三个或者四个数大于等于 $mid$ ，则消除后的两个数都大于等于 $mid$ 。
于是，可以把它抽象为三种状态，邻项枚举状态的转化，而观察到，如果是两个数大于等于 $mid$ 的情况，跟其他一个情况结合，转移后还是原来的情况，所以只需要考虑两种情况，不妨记为正号跟负号，列列状态机转移即可。
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
|
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl b(n);
rep(i, 0, n - 1) cin >> b[i];
auto check = [&](int mid) -> bool {
string res = "";
auto upd = [&](char x) {
res.push_back(x);
if (res == "--" || res == "+++" || res == "++-" || res == "+--")
res.pop_back();
else if (res == "-+")
res.clear();
else if (res == "+-+") {
res.pop_back();
res.pop_back();
}
};
rep(i, 0, n - 1) {
int tem = (a[i] >= mid) + (b[i] >= mid);
if (tem == 1) continue;
if (tem == 0)
upd('-');
else
upd('+');
}
return res == "+" || res == "++";
};
ll l = 1, r = 2 * n, mid, ans;
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else
r = mid - 1;
}
cout << ans << endl;
return;
}
|
E
题目大意：给定一棵无根树和一个空集 $S$ ，需要对数操作 $n-1$ 次，每次操作首先从树中找出最大编号的叶子，然后把这个叶子加到 $S$ 里，如果已经在里面了就无事发生，最后从树中移除一个不是这个叶子的叶子，请求出最后得到的 $S$ 可能数目，并模 $998244353$ 。
数据范围： $2 \leq n \leq 2 \cdot 10^5$
思路：首先，不难观察到 $n-1$ 必然会作为最后被加入 $S$ 的叶子，而且它无论如何都会被加入 $S$ ，因此不妨考虑以 $n-1$ 为根进行建树。
随后，考虑一个 $u$ 被放进 $S$ ，而放进的上一个叶子是 $v$ 的情况，我们可以发现，必然有 $v<u$ ，同时，由于 $u$ 需要能被自己的子树暴露出来，因此需要有 $\text{u子树内除u的最大编号} < v < u$ （因为此处假设 $v$ 直接转移到 $u$ ，如果不满足前一个不等号，那么就不是从 $v$ 直接转移到 $u$ 了），这样就是一个预处理然后沿着编号DP的形式，同时还需要前缀和优化。
至于初始化，由于第一个被取的点是固定的，就初始化这个点的方案数是1即可。
最后，对于根，也就是 $n-1$ 来说，要让它暴露成为叶子，那么假设是从 $v$ 转移过来的，必须有 $\text{除了v所在子树的其他子树中编号最大值} < v$ ，所以需要对每个点维护一下第二大的编号。
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
|
const ll MOD = 998244353;
void solve() {
int n, x, y;
cin >> n;
vvi ma(n);
rep(i, 1, n - 1) {
cin >> x >> y;
ma[x - 1].push_back(y - 1);
ma[y - 1].push_back(x - 1);
}
int idx = -1;
rep(i, 0, n - 1) {
if (sz(ma[i]) == 1) idx = max(idx, i);
}
if (idx == n - 1) {
cout << 1 << endl;
return;
}
vi pa(n, -1);
pa[n - 1] = n - 1;
queue<int> q;
q.push(n - 1);
vi tem;
while (!q.empty()) {
auto node = q.front();
q.pop();
tem.push_back(node);
for (int& p : ma[node]) {
if (pa[p] >= 0) continue;
pa[p] = node;
q.push(p);
}
}
vi maxx(n, -1), maxx2(n, -1);
frep(i, n - 1, 0) {
int tem2 = tem[i];
maxx[tem2] = tem2;
for (int& p : ma[tem2]) {
if (pa[p] == tem2) {
maxx[tem2] = max(maxx[tem2], maxx[p]);
maxx2[tem2] = max(maxx2[tem2], maxx[p]);
}
}
}
vl dp(n), pre(n);
rep(i, 0, n - 2) {
ll tem2 = 0;
if (maxx2[i] < i) {
ll r = (i >= 1 ? pre[i - 1] : 0);
ll l = (maxx2[i] >= 0 ? pre[maxx2[i]] : 0);
tem2 = (r - l + MOD) % MOD;
}
if (i == idx) tem2 = (tem2 + 1) % MOD;
dp[i] = tem2;
if (i == 0)
pre[i] = dp[i];
else
pre[i] = (pre[i - 1] + dp[i]) % MOD;
}
int pm1 = -1, pm2 = -1;
for (int& p : ma[n - 1]) {
if (pa[p] == n - 1) {
if (maxx[p] > pm1) {
pm2 = pm1;
pm1 = maxx[p];
} else if (maxx[p] > pm2) {
pm2 = maxx[p];
}
}
}
ll tem2 = (pm2 >= 0 ? pre[pm2] : 0);
cout << (pre[n - 2] - tem2 + MOD) % MOD << endl;
return;
}
|
F
题目大意：给定长度为 $n$ 的数组 $a$ ，和长度为 $k$ 的数组 $b$ ， $b$初始化为0。现在可以任意重排 $a$ ，然后按照顺序，每次将 $a_i$ 加入到 $b$ 中的最小值上，取 $f(a)$ 为最后 $b$ 的最大值，请求出所有 $f(a)$ 中的最大值。
数据范围： $1 \leq k \leq n \leq 18, 1 \leq a_i \leq 10^9$
思路：首先，这里的数据范围，看不出状压DP的建议回去补知识点了。
然后对于求出最大值，想到如果能满足大的，那么必然存在排列能满足小的，也就是存在单调性，那么很显然的可以使用二分答案。
但是这里需要发现一个性质，就是打表可以发现， $a$ 中的最大值（或者最大值之一），必然会在最后被加入 $b$ 。
然后，问题就转化为，用除了最大值的所有 $a_i$ ，是否存在一个顺序，使得它能按照题中所述放进 $b$ 中，使得每个桶都能达到 $mid$ 。
同时，还有一个观察，就是如果每个桶都能达到 $mid$ ，那么必然存在一个操作序列，使得能按照题中所述的操作方式得到结果。
因此考虑 $dp_i$ 为已经放了 $i$ 作为状压掩码时，已经达到至少 $mid$ 的桶数， $fdp_i$ 为已经放了 $i$ 作为状压掩码时，当前剩下的桶已经装进的元素之和。
从而有贪心的转移方程，也就是放入当前的数，如果能更新 $dp_{i \mid mask}$ ，那么就更新，如果是相等的，那就尽可能使当前剩下的比较多，也就是更新 $fdp_{i \mid mask}$ ，时间复杂度 $O(\log V n \cdot 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
void solve() {
ll n, k;
cin >> n >> k;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ranges::sort(a);
ll tem = a[n - 1];
ll tot = 0;
rep(i, 0, n - 2) tot += a[i];
n--;
auto check = [&](ll mid) -> bool {
int mask = (1 << n);
vl dp(mask, -1);
vl fdp(mask, -1);
dp[0] = 0, fdp[0] = 0;
rep(i, 0, mask - 1) {
if (dp[i] == -1) continue;
rep(j, 0, n - 1) {
if ((i >> j) & 1) continue;
ll tem = dp[i], tem2 = fdp[i];
if (tem2 + a[j] >= mid) {
tem++, tem2 = 0;
} else
tem2 += a[j];
if (tem > dp[(i | (1 << j))]) {
dp[(i | (1 << j))] = tem;
fdp[(i | (1 << j))] = tem2;
} else if (tem == dp[(i | (1 << j))] && tem2 > fdp[(i | (1 << j))]) {
fdp[(i | (1 << j))] = tem2;
}
if (dp[(i | (1 << j))] >= k) return true;
}
}
return dp[mask - 1] >= k;
};
ll l = 0, r = tot / k, ans = 0, mid;
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else
r = mid - 1;
}
cout << tem + ans << endl;
return;
}
|
