本文主要是介绍Educational Codeforces Round 165 (Div. 2) A~E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A.Two Friends (思维)
题意：
小 A A A想开一个派对。他有 n n n个朋友，他希望至少有 2 2 2个朋友参加他的派对。
i i i 这个朋友最好的朋友是 p i p_i pi 。所有的 p i p_i pi 都是不同的，对于每一个 i ∈ [ 1 , n ] i \in [1, n] i∈[1,n] ， p i ≠ i p_i \ne i pi=i 都是不同的。
小 A A A可以向朋友发出邀请。如果第 i i i 个朋友和第 p i p_i pi 个朋友都收到了邀请，那么第 i i i 个朋友就会来参加聚会（注意，第 p i p_i pi 个朋友不必真的来参加聚会）。每份邀请函都恰好发给其中一位朋友。
计算至少要发出多少份邀请函，才能让朋友来参加聚会？
分析：
如果有两人互为最好朋友则发两张，否则三张必定能解决。
代码：
#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 01 01的二进制序列，每次可选择一段序列将其尾元素移至首位，代价为序列长度，问最少用多少代价可以构造一个非降序序列。
分析：
问题等价于将所有的 0 0 0移到 1 1 1前面，一次最多把一个 0 0 0移到 1 1 1前面对。并且对于一个 0 0 0，最少的操作数一定是前面 1 1 1的个数 + 1 +1 +1。只需要统计前缀的 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 n n 的整数数组 a a a。可以执行以下操作：选择数组中的一个元素 a i a_i ai，使得 a i + 1 = a i a_{i+1}=a_i ai+1=ai或者 a i − 1 = a i a_{i-1}=a_i ai−1=ai。
你的任务是计算执行最多 k k k 次上述操作数组的最小总和。
分析：
d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i个数，执行了 j j j次操作的最小和。从左到右枚举当前最小值的位置 i i i，枚举操作数 x x x，操作是把一个区间的值都变成最小值 a i a_i ai，区间长度是 x + 1 x+1 x+1，可以直接枚举区间的左边界 l l l ，区间右边界就是 r = l + x r=l+x r=l+x。有转移方程： d p [ r ] [ t + x ] = m i n ( d p [ r ] [ t + x ] , d p [ l − 1 ] [ t ] + ( a [ i ] ∗ ( x + 1 ) ) ) ; dp[r][t+x]=min(dp[r][t+x],dp[l-1][t]+(a[i]*(x+1))); dp[r][t+x]=min(dp[r][t+x],dp[l−1][t]+(a[i]∗(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 n n件商品， A l i c e Alice Alice可以用 a i a_i ai的价格购入， B o b Bob Bob可用 b i b_i bi的价格从 A l i c e Alice Alice处购买，并且 B o b Bob Bob可以不花钱获得额外的 k k k件物品，询问双方在最优策略下， A l i c e Alice Alice可获得的收益最大为多少。
分析：
我们按照 b i b_i bi的值从大到小排序。枚举边界 i i i，从 1 − i 1-i 1−i的部分选 k k k个， i + 1 − n i+1-n i+1−n部分任意选择。 1 − i 1-i 1−i部分选的 k k k个一定是这次选择里最大的 k k k个 b b b，这部分选的某个位置对答案的贡献是 − a i -a_i −ai，将问题转化成选择 k k k个最小的 a i a_i ai，因此维护一个 a i a_i ai单调队列。
考虑到 i + 1 − n i+1-n i+1−n部分任意选，由于最大的 k k k个 b b b已经选了，这部分选的某个位置对答案的贡献是 b i − a i b_i-a_i bi−ai。因为这部分是任意选的，为了让答案更大，对答案的贡献就是 b i − a i b_i-a_i bi−ai结果为正值的和。
代码：
#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 n n 的整数数组 a a a 。 如果有一个整数在 a a a的子段中恰好出现一次，那么这个子段就是唯一的。
现在可以执行以下任意次数（可能为零）的操作：从数组中选择一个元素，然后用任意整数替换它。
你的任务是计算上述操作的最少次数，以使数组 a a a 的所有子段都是唯一的。
分析：
首先对于每个位置 a i a_i ai，找到其前面和后面第一个与之相同的位置记为 p r e i pre_i prei和 n x t i nxt_i nxti，那么对于 a i a_i ai，能使得所有 l ∈ [ p r e i + 1 , i ] , r ∈ [ i , n x t i − 1 ] l \in [pre_i+1,i],r \in [i,nxt_i-1] l∈[prei+1,i],r∈[i,nxti−1]的区间都变得符合要求。
这符合二维数点，通过用扫描线找到不满足要求的区间。假设对于每个点 i i i作为右端点时,其最大的不满足要求的左端点为 l i l_i li。我们可以按照 l i l_i li排序，然后每次贪心地修改最大的 l i l_i li，然后记录修改过的最小的为 l i l_i li为 m i n v a l minval minval，可以发现如果某些 i ≥ m i n v a l i \ge minval i≥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，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。
这篇关于Educational Codeforces Round 165 (Div. 2) A~E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
