A.Two Friends (思维)

题意：

小$A$想开一个派对。他有$n$个朋友，他希望至少有$2$个朋友参加他的派对。
$i$ 这个朋友最好的朋友是 $p_i$ 。所有的 $p_i$ 都是不同的，对于每一个 $i\in [1,n]$ ，$p_i\ne i$ 都是不同的。
小$A$可以向朋友发出邀请。如果第 $i$ 个朋友和第 $p_i$ 个朋友都收到了邀请，那么第 $i$ 个朋友就会来参加聚会（注意，第 $p_i$ 个朋友不必真的来参加聚会）。每份邀请函都恰好发给其中一位朋友。
计算至少要发出多少份邀请函，才能让朋友来参加聚会？

分析：

如果有两人互为最好朋友则发两张，否则三张必定能解决。

代码：

#include <bits/stdc++.h>using namespace std;
const int N = 1e6 + 5;
int a[N];int main() {int t;cin >> t;while (t--) {int flag = 0;int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n; i++) {if (a[a[i]] == i)flag = 1;}if (flag)cout << 2 << endl;elsecout << 3 << endl;}return 0;
}

B.Shifts and Sorting （思维）

题意：

给定一个只含$01$的二进制序列，每次可选择一段序列将其尾元素移至首位，代价为序列长度，问最少用多少代价可以构造一个非降序序列。

分析：

问题等价于将所有的$0$移到$1$前面，一次最多把一个$0$移到$1$前面对。并且对于一个$0$，最少的操作数一定是前面$1$的个数$+1$。只需要统计前缀的$1$的个数即可。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;int main() {int t;cin >> t;while (t--) {string s;cin >> s;LL num = 0;LL ans = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == '1')num++;else if (num)ans += num + 1;}cout << ans << endl;}return 0;
}

C.Minimizing the Sum (dp)

题意：

给你一个长度为 $n$ 的整数数组 $a$。可以执行以下操作：选择数组中的一个元素$a_i$，使得$a_{i+1}=a_i$或者$a_{i-1}=a_i$。
你的任务是计算执行最多 $k$ 次上述操作数组的最小总和。

分析：

$dp[i][j]$表示前$i$个数，执行了$j$次操作的最小和。从左到右枚举当前最小值的位置$i$，枚举操作数$x$，操作是把一个区间的值都变成最小值$a_i$，区间长度是$x+1$，可以直接枚举区间的左边界$l$ ，区间右边界就是$r=l+x$。有转移方程：$dp[r][t+x]=min(dp[r][t+x],dp[l-1][t]+(a[i]\ast (x+1)));$。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;int main() {int t;cin >> t;while (t--) {int n, k;cin >> n >> k;vector<LL> a(n + 1), s(n + 1);for (int i = 1; i <= n; i++)cin >> a[i];vector<vector<LL>> dp(n + 1, vector<LL>(k + 1, 1e16));dp[0][0] = 0;for (int i = 1; i <= n; i++) {for (int x = 0; x <= k; x++) {for (int l = i; l >= i - x && l >= 1; l--) {int r = l + x;if (r > n)continue;for (int t = 0; t <= k - x; t++) {dp[r][t + x] = min(dp[r][t + x], dp[l - 1][t] + (a[i] * (x + 1)));}}}}LL ans = 1e16;for (int i = 0; i <= k; i++) {ans = min(dp[n][i], ans);}cout << ans << endl;}return 0;
}

D. Shop Game (贪心)

题意：

总共有$n$件商品，$Alice$可以用$a_i$的价格购入，$Bob$可用$b_i$的价格从$Alice$处购买，并且$Bob$可以不花钱获得额外的$k$件物品，询问双方在最优策略下，$Alice$可获得的收益最大为多少。

分析：

我们按照$b_i$的值从大到小排序。枚举边界$i$，从$1-i$的部分选$k$个，$i+1-n$部分任意选择。$1-i$部分选的$k$个一定是这次选择里最大的$k$个$b$，这部分选的某个位置对答案的贡献是$-a_i$，将问题转化成选择$k$个最小的$a_i$，因此维护一个$a_i$单调队列。
考虑到$i+1-n$部分任意选，由于最大的$k$个$b$已经选了，这部分选的某个位置对答案的贡献是$b_i-a_i$。因为这部分是任意选的，为了让答案更大，对答案的贡献就是$b_i-a_i$结果为正值的和。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;int main() {int t;cin >> t;while (t--) {int n, k;cin >> n >> k;vector<int> a(n), b(n);for (int i = 0; i < n; i++)cin >> a[i];for (int i = 0; i < n; i++)cin >> b[i];vector<int> tmp(n);iota(tmp.begin(), tmp.end(), 0);sort(tmp.begin(), tmp.end(), [&](int x, int y) {if (b[x] == b[y]) return a[x] > a[y];return b[x] > b[y];});LL ans = 0;LL l = 0, r = 0;priority_queue<int> p;for (int i = 0; i < k; i++) {int j = tmp[i];p.push(a[j]);l -= a[j];}for (int i = k; i < n; i++) {int j = tmp[i];r += max(0, b[j] - a[j]);}ans = max(ans, l + r);for (int i = k; i < n; i++) {int j = tmp[i];p.push(a[j]);l -= a[j];l += p.top();p.pop();r -= max(0, b[j] - a[j]);ans = max(ans, l + r);}cout << ans << endl;}return 0;
}

E. Unique Array (数据结构)

题意：

给你一个长度为 $n$ 的整数数组 $a$ 。 如果有一个整数在$a$的子段中恰好出现一次，那么这个子段就是唯一的。
现在可以执行以下任意次数（可能为零）的操作：从数组中选择一个元素，然后用任意整数替换它。
你的任务是计算上述操作的最少次数，以使数组 $a$ 的所有子段都是唯一的。

分析：

首先对于每个位置$a_i$，找到其前面和后面第一个与之相同的位置记为$pr{e}_i$和$nx{t}_i$，那么对于$a_i$，能使得所有$l\in [pr{e}_i+1,i],r\in [i,nx{t}_i-1]$的区间都变得符合要求。
这符合二维数点，通过用扫描线找到不满足要求的区间。假设对于每个点$i$作为右端点时,其最大的不满足要求的左端点为$l_i$。我们可以按照$l_i$排序，然后每次贪心地修改最大的$l_i$，然后记录修改过的最小的为$l_i$为$minval$，可以发现如果某些$i\ge minval$，那么这个位置也不再需要修改了,可以跳过。可以发现这样是最优的。

代码：

#include <bits/stdc++.h>using namespace std;
const int mod = 998244353;
const int INF = 1e9;
struct Info {int mn = INF, mnnow = 0;
};
using Tag = int;Info operator+(const Info &a, const Info &b) {return a.mn < b.mn ? a : b;
}void apply(Info &x, Tag &a, Tag f) {x.mn += f;a += f;
}template<class Info, class Tag>
struct LazySegmentTree {int n;vector<Info> info;vector<Tag> tag;LazySegmentTree() {}LazySegmentTree(int n, Info _init = Info()) {init(vector<Info>(n, _init));}LazySegmentTree(const vector<Info> &_init) {init(_init);}void init(const vector<Info> &_init) {n = (int) _init.size();info.assign((n << 2) + 1, Info());tag.assign((n << 2) + 1, Tag());function<void(int, int, int)> build = [&](int p, int l, int r) {if (l == r) {info[p] = _init[l - 1];return;}int m = (l + r) / 2;build(2 * p, l, m);build(2 * p + 1, m + 1, r);pull(p);};build(1, 1, n);}void pull(int p) {info[p] = info[2 * p] + info[2 * p + 1];}void apply(int p, const Tag &v) {::apply(info[p], tag[p], v);}void push(int p) {apply(2 * p, tag[p]);apply(2 * p + 1, tag[p]);tag[p] = Tag();}void change(int p, int l, int r, int x, const Info &v) {if (l == r) {info[p] = v;return;}int m = (l + r) / 2;push(p);if (x <= m) {change(2 * p, l, m, x, v);} else {change(2 * p + 1, m + 1, r, x, v);}pull(p);}void change(int p, const Info &v) {change(1, 1, n, p, v);}Info ask(int p, int l, int r, int x, int y) {if (l > y || r < x) {return Info();}if (l >= x && r <= y) {return info[p];}int m = (l + r) / 2;push(p);return ask(2 * p, l, m, x, y) + ask(2 * p + 1, m + 1, r, x, y);}Info ask(int l, int r) {return ask(1, 1, n, l, r);}void change(int p, int l, int r, int x, int y, const Tag &v) {if (l > y || r < x) {return;}if (l >= x && r <= y) {apply(p, v);return;}int m = (l + r) / 2;push(p);change(2 * p, l, m, x, y, v);change(2 * p + 1, m + 1, r, x, y, v);pull(p);}void change(int l, int r, const Tag &v) {return change(1, 1, n, l, r, v);}
};int main() {int T;cin >> T;while (T--) {int n;cin >> n;vector<int> pre(n + 1), nxt(n + 1);vector<int> a(n + 1);for (int i = 1; i <= n; i++)cin >> a[i];{vector<int> last(n + 1);for (int i = 1; i <= n; i++) {pre[i] = last[a[i]];last[a[i]] = i;}}{vector<int> last(n + 1, n + 1);for (int i = n; i >= 1; i--) {nxt[i] = last[a[i]];last[a[i]] = i;}}vector<vector<pair<int, int>>> now(n + 1);for (int i = 1; i <= n; i++) {now[nxt[i] - 1].push_back({i, 1});now[i - 1].push_back({i, 0});}vector<Info> init(n);for (int i = 0; i < n; i++) {init[i] = {0, i + 1};}LazySegmentTree<Info, Tag> seg(init);set<pair<int, int>> s;for (int i = n; i >= 1; i--) {for (auto [x, type]: now[i]) {if (type) {seg.change(pre[x] + 1, x, 1);} else {seg.change(pre[x] + 1, x, -1);}}auto [mn, mnnow] = seg.ask(1, i);if (mn == 0) {s.insert({mnnow, i});}}int ans = 0;int tmp = n + 1;while (!s.empty()) {if (prev(s.end())->second >= tmp) {s.erase(prev(s.end()));} else {ans += 1;tmp = prev(s.end())->first;s.erase(prev(s.end()));}}cout << ans << endl;}return 0;
}

赛后交流

在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。

群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。