本文為AtCoder Beginner Contest 409 的詳細題解

目錄

題目A:

題目大意:

解題思路:

代碼(C++):

題目B:

題目大意:

解題思路:

代碼(C++):

題目C:

題目大意:

解題思路:

代碼(C++):

題目D:

題目大意:

解題思路:

代碼(C++):

題目E:

題目大意:

解題思路:

代碼(C++):

---

題目A:

A - Conflict

題目大意:

給你兩個長度為n的字符串s和t，都只包含小寫字母‘x’,'o'。

現在要找出是否有一個下標i滿足s[i] == t[i] == 'o'

解題思路:

直接可以題目意思進行代碼實現即可。

遍歷一遍，找到滿足條件的輸出Yes即可

具體看代碼實現。

代碼(C++):

void solve() {int n;std::string s, t;std::cin >> n >> s >> t;int ans = 0;for (int i = 0; i < n; i++) {if (s[i] == t[i] && s[i] == 'o') {std::cout << "Yes\n";return;}}std::cout << "No\n";
}

題目B:

B - Citation

題目大意:

現在給你一個數組a,你需要找出滿足下面條件的最大的整數x:

x滿足，在數組a中，大于或等于x的元素在數組中至少出現x次。

解題思路:

我們先從最小的開始看，從特殊到一般：

大于等于0的元素在數組中至少出現0次。

大于等于1的元素在數組中至少出現1次。

大于等于2的元素在數組中出現至少2次。

...

我們很明顯可以注意到一點：

隨著x的值增加，就表明我們需要在數組中找到更多的數字來滿足大于x。

每增加1就需要多找一個數字滿足a[i] > x。

那么總會有一個臨界點的x，使得數組中無法再找出x個數字來滿足大于它了。

那么思路就可以來了，我們直接從數組元素中最大的開始，可以先對數組排序，將x的初始值設置為0，從數組中最大的開始，如果能找到這樣一個x，就讓x++即可。

代碼(C++):

void solve() {int n;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; i++) {std::cin >> a[i];}std::sort(a.begin(), a.end(), std::greater<>());int x = 0;for (int i = 0; i < n; i++) {if (a[i] >= x + 1 && i >= x) {x++;}}std::cout << x << "\n";
}

題目C:

C - Equilateral Triangle

題目大意:

給你一個周長為L的圓，現在圓上有n個點。

給你n - 1個數字di, 其中di表示第i + 1個點位于第i個點沿著圓周順時針di的位置。

其中L和di都為整數。

現在你需要找出在圓上不同的三個點，使得這三個點組成的三角形為等邊三角形。

解題思路:

首先得明白關鍵點：

周長L和每一個點的距離d都是都是整數，那么我們要找到這樣一個等邊三角形的話，三個點一定是將圓平分成三等分的（這個可以通過連接點和圓心，進行簡單的證明）。

既然能三等分周長，那么周長必須是3的倍數。

距離d都是整數，周長為L，我們可以把圓劃分成L段，然后計算出每個整數位置的點的個數。

我們可以第0個點的位置設置成0，然后根據題目中給的d計算出每一個位置中點的個數。

假設構成等邊三角形的其中一個點的位置為i，那么根據上面的分析，剩下的兩個點的位置為i + L?/ 3, i + 2 * L?/ 3，也就是分別加上L?/ 3。

最后滿足這樣的三角形的三個不同點的個數，可以用乘法原理做，最后除以三即可。

具體看代碼實現。

代碼(C++):

void solve() {int n, l;std::cin >> n >> l;std::vector<int> cnt(l);cnt[0] = 1;int pos = 0;for (int i = 0; i < n - 1; i++) {int d;std::cin >> d;pos = (pos + d) % l;cnt[pos]++;}if (l % 3 != 0) {std::cout << "0\n";return;}i64 ans = 0;for (int i = 0; i < l; i++) {ans += 1LL * cnt[i] * cnt[(i + l / 3) % l] * cnt[(i + l * 2 / 3) % l];}std::cout << ans / 3 << "\n";
}

題目D:

D - String Rotation

題目大意:

給你一個長度為n的字符串s，現在你可以進行以下操作一次：

選擇一個下標i，將s[i]插入到字符串的任意位置，并且刪除s[i]。

你需要進行一次操作，使得字符串字典序最小，找出字典序最小的這個字符串。

解題思路:

兩個字符串的字典序有一個很常規的比較方法：

從最左邊的字符開始比較，逐一比較，當遇到兩個不同的字符的時候，比較這兩個字符的字典序即可，字符小的那個字符串，即為字典序小的字符串。

題目的意思其實就是把字符中的一個字符進行移動，然后使得字典序盡可能小。

也就是說，字符串的字符構成是不變的。

根據上述分析我們可以得出：

1.在所有的字符字符從小到大排列（也就是升序排列）的時候，此時字符串的字典序最小。

2.我們從前往后對比，當遇到字符不是按升序排列的那個字符的時候，把這個字符往后面放，使得字符串前部分按照升序排列即可。

代碼參考官方題解

代碼(C++):

void solve() {int n;std::string s;std::cin >> n >> s;int l = -1;for (int i = 0; i < n - 1; i++) {if (s[i] > s[i + 1]) {l = i;break;}}if (l == -1) {std::cout << s << "\n";return;}int r = n;for (int i = l + 1; i < n; i++) {if (s[l] < s[i]) {r = i;break;}}std::string ans = s.substr(0, l) + s.substr(l + 1, r - l - 1) + s[l] + s.substr(r);std::cout << ans << "\n";
}

題目E:

E - Pair Annihilation

題目大意:

現在有一顆包含n個節點的樹，并且給出你邊的連接關系和邊的權重:

節點ui和vi之間有一條權重為wi的邊。

現在這個樹的每一個節點上都有xi個正電子或者xi個電子。

你把一個正電子或者電子從節點ui移動到節點vi需要消耗wi個單位的能量，一個正電子和一個電子相遇會湮滅消失。

保證樹上的正電子的數目和電子數目相等。

現在你需要通過移動其中的正電子或者電子，是得所有的電子消失，輸出需要消耗的最小能量。

解題思路:

題目的關鍵點是，保證正電子數量和電子數量相等。

既然是一個樹，那么顯而易見的適合的移動方案：

把葉子節點的電子或者正電子，往根節點移動，全部移到根節點。

代碼參考官方題解

代碼(C++):

void solve() {int n;std::cin >> n;std::vector<i64> X(n);for (int i = 0; i < n; i++) {std::cin >> X[i];}std::vector<std::vector<std::pair<int, i64>>> Trees(n);for (int i = 0; i < n - 1; i++) {int u, v;i64 w;std::cin >> u >> v >> w;u--;v--;Trees[u].push_back({v, w});Trees[v].push_back({u, w});}i64 ans = 0;std::function<void(int, int)> dfs;dfs = [&](int v, int fa) -> void {for (auto& [c, w] : Trees[v]) {if (c == fa) {continue;}//往下搜子節點dfs(c, v);//加上此時下面所有的子節點移動到此時這個根節點所需要的能量ans += w * abs(X[c]);//移動,并且進行消耗(正負抵消)X[v] += X[c];}};dfs(0, -1);std::cout << ans << "\n";
}