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';
}