Codeforces Round 1040 (Div. 2) A

本文为Codeforces Round 1040 (Div. 2) A - D题的详细题解, 觉得有帮助或者写的不错可以点个赞！

题目A:

题目大意:

解题思路:

代码(C++):

题目B:

题目大意:

解题思路:

代码(C++):

题目C:

题目大意:

解题思路:

代码(C++):

题目D:

题目大意:

解题思路:

代码(C++):

题目A:

Problem - A - Codeforces

题目大意:

现在定义，a是数组，sum(a)即为数组a中所有元素的和。

mex(a)即为数组a的最小排除数，也就是不在数组a中的最小非负整数

现在给出你一个数组S，并且刚开始你的得分为0。

每次操作你可以从数组中取出一个一部分元素（也就是原数组会少一部分元素），把这部分元素组成的数组设置成b。

你可以对你的分数加上sum(b)或者mex(b)。

在你进行任意次操作后，求出得分的最大值。

解题思路:

感性的分析，取出来的数字要使得mex值很大，那肯定要求很苛刻，要包含从0开始连续的数字才行。

理性的分析，

mex{0} > sum{0}

mex{0, 1} > sum{0, 1}

mex{0, 1, 2} == sum{0, 1, 2}

mex{0, 1, 2, 3} < sum(0, 1, 2, 3)

很容易分析出，接下来的mex都是小于sum的

也就是得出结论，数组中有0和1的时候，取出0，1，并且把分数加上mex。

其他时候再加上sum。

更深层次的思考，mex{1} < sum{1}, mex{0} > sum{0}。

那么得出最终结论：

我们把数组中的每一个0单独取出来，加上mex{0}，也就是1，也就是0的个数。

然后把其他的数字取出来，直接加到分数上。

代码(C++):

void solve() {int n;std::cin >> n;int sum = 0, cnt0 = 0;for (int i = 0; i < n; i++) {int x;std::cin >> x;//求出这些数字的总和sum += x;//0可以单独拿出来作为一个集合{0},MEX{0} = 1//所以只需要求出1的数量即可if (x == 0) {cnt0++;}}std::cout << sum + cnt0 << "\n";
}

题目B:

Problem - B - Codeforces

题目大意:

现在给你一个数组，里面只包含元素0， 1， 2, 并且保证0，1，2的三个数字的数量至少为1。

现在玩家A，要从数组的第一个元素开始，走到最后一个元素，每次可以往左或者往右走一格。

每次经过的元素都会加在自己的得分上（每一个元素都可以重复的计算），玩家A的目标是在走到最后一个元素上并且加到那个元素的值后，得分恰好为S （不能超过也不能小于S）。

现在初始数组为a。

现在你是玩家B，你需要重新打乱数组，使得玩家A怎么都不能得到分数S。

输出打乱后的数组，如果玩家A怎么都能得到分数S，输出-1.

解题思路:

我们很容易注意到，玩家A直接从头走到尾，会加上数组a的所有元素，我们记作tot。

也就是说，玩家A能获得的分数最小值为tot，那么S < tot的时候，肯定是无法恰好获得S分的，此时怎么排列数组都可以。

当S == tot的时候，一遍走过去就恰好达到分数S了，此时无论怎么排列数组，都会产生S分。

当S > tot的时候，此时玩家A就可以通过”刷分“操作来获取更多的得分。

我们进行如下分析：

由于数组中只存在0， 1， 2。并且保证0，1，2的三个数字的数量至少为1。

当数组中有01相邻的时候，“左右横跳”，可以获得任意的得分。

从上面的结论可以知道，在S > tot的前提下，如果数组中有0，1相邻，玩家A肯定能获得恰好S分。

当数组中有02相邻的时候，每次左右横跳，都会获得得分2。

当数组中有11相邻的时候，每次左右横跳，都会获得得分3。

当数组中有12相邻的时候，每次左右很跳，都会获得得分4。

根据上述分析，我们现在把0和1分开摆放，可以类似于：

{0, 0, ..., 0, 2, 2, ..., 2, 1, ... ,1}，现在S > tot。

我们再进行如下的分析：

当S == tot + 1，玩家A无论怎么操作都得不到S。

当S == tot + 2，玩家A可以通过02横跳来得到。

当S == tot + 3, 11横跳。

当S == tot + 4, 21横跳。

...

也就是只有在S == tot + 1的时候，玩家A怎么操作都得不到S。

综合上述推理我们即可实现代码。

代码(C++):

void solve() {int n, s;std::cin >> n >> s;//分别计算出0,1,2的数量int cnt0 = 0, cnt1 = 0, cnt2 = 0;for (int i = 0; i < n; i++) {int x;std::cin >> x;if (x == 0) {cnt0++;} else if (x == 1) {cnt1++;} else {cnt2++;}}//根据数组中1,2的数量计算数组元素的总和int tot = cnt1 + cnt2 * 2;/*此部分分析看题解*/if (s < tot || s == tot + 1) {for (int i = 0; i < cnt0; i++) {std::cout << "0 ";}for (int i = 0; i < cnt2; i++) {std::cout << "2 ";}for (int i = 0; i < cnt1; i++) {std::cout << "1 ";}std::cout << "\n";} else {std::cout << "-1\n";}
}

题目C:

Problem - C - Codeforces

题目大意:

现在有m个数对(ai, bi)，我们定义集合S = {(a1, b1), (a2, b2), (a3, b3), ...,(am, bm)}。

现在定义两个值f(S)和g(S)。

1.把每个数对中的(a,b)表示一个区间[a, b]。

f(S)为集合S所包含的所有区间的并集长度

2.现在(a, b)为图中的一条无向边。

g(S)是一个长度至少为3的环的节点数量。

现在给你n个数对(a, b)，你需要从中取一部分数对组成集合S，你需要使得

f(S) - g(S)尽可能的大，输出此时你取的集合大小和集合里面包含的元素（原来数对的索引）。

解题思路:

感性的思考，定义t = f(S) - g(S)，要使得t越来越大，那么我们需要使得f(S)越大，g(S)越小。

取更多的数对只会让f(S)越大，但是如果出现环的话，g(S)会瞬间增大很多。

也就是说，我们尽可能的取更多的数对，但是尽可能的不让g(S)出现环，此时能让t尽可能的最大。

理想分析：对于一些数对，[x1, x2], [x2, x3], [x3, x4]...[x(k - 1), x(k)],他们两两相连组成了一个环，也就是x1 == xk。

很容易知道这段区间的并集大小就是{x1, x2, ..., xk}中的最大值减去最小值，因为两两相连，不用考虑空的部分。

我们如果删去其中的一个点[x1, x2]，那么环就不存在了, 但是很容易发现并集大小是不变的。

所以，我们可以无脑的删除所有可以连成环的点，这样就可以保证最终的值是最大的！

可以用并查集快速判断是否成环。实际操作看具体代码

代码(C++):

//https://leetcode.cn/discuss/post/3583665/fen-xiang-gun-ti-dan-chang-yong-shu-ju-j-bvmv/
class UnionFind {std::vector<int> fa;std::vector<int> sz;
public:int cc;UnionFind(int n) : fa(n), sz(n, 1), cc(n) {std::iota(fa.begin(), fa.end(), 0);}int find(int x) {if (fa[x] != x) {fa[x] = find(fa[x]);}return fa[x];}bool is_same(int x, int y) {return find(x) == find(y);}bool merge(int from, int to) {int x = find(from), y = find(to);if (x == y) {return false;}fa[x] = y;sz[y] += sz[x];cc--;return true;}int get_size(int x) {return sz[find(x)];}
};void solve() {int n;std::cin >> n;std::vector<std::pair<int, int>> a(n);for (int i = 0; i < n; i++) {std::cin >> a[i].first >> a[i].second;}int mx = 2 * n;UnionFind uf(mx + 1);std::vector<int> ans;for (int i = 0; i < n; i++) {int u = a[i].first;int v = a[i].second;if (uf.merge(u, v)) {ans.push_back(i + 1);}}std::cout << ans.size() << "\n";for (int x : ans) {std::cout << x << " ";}std::cout << "\n";
}

题目D:

Problem - D - Codeforces

题目大意:

现在有一个长度为n的排列P。

你需要构造一个长度为n的数组a，对于每一个ai，

你可以选择ai = pi 或者 ai = 2 * n - pi。

你的目的是使得数组a中的逆序对数目最少，输出这个最小数目。

解题思路:施工中

代码(C++):

//https://leetcode.cn/discuss/post/3583665/fen-xiang-gun-ti-dan-chang-yong-shu-ju-j-bvmv/
template<typename T>
class FenwickTree {std::vector<T> tree;public:FenwickTree(int n) : tree(n + 1, 0) {}void update(int i, T val) {for (; i < tree.size(); i += i & -i) {tree[i] += val;}}T pre(int i) const {T res = 0;for (; i > 0; i &= i - 1) {res += tree[i];}return res;}T query(int l, int r) const {if (r < l) {return 0;}return pre(r) - pre(l - 1);}T total(int n) const {return pre(n);}
};void solve() {int n;std::cin >> n;std::vector<int> p(n + 1);for (int i = 1; i <= n; i++) {std::cin >> p[i];}std::vector<int> l(n + 1), r(n + 1);FenwickTree<int> bit(n);i64 base = 0;for (int i = 1; i <= n; i++) {int x = i - 1 - bit.pre(p[i]);l[i] = x;base += x;bit.update(p[i], 1);}bit = FenwickTree<int> (n);for (int i = n; i >= 1; i--) {int x = bit.total(n) - bit.pre(p[i]);r[i] = x;bit.update(p[i], 1);}i64 ans = base;for (int i = 1; i <= n; ++i) {int x = r[i] - l[i];if (x < 0) {ans += x;}}std::cout << ans << '\n';
}