1. 首頁 > 生活百科 > >

Div. 2 Codeforces Round #822 A-F

生活百科

比賽鏈接
A題解知識點：貪心 。
注意到任意三根木棍的相等最優解是最長減最小，因此從小到大排序，三個三個??，取最小?。
時間復雜度 \(O(n\log n)\)
空間復雜度 \(O(n)\)
代碼#include <bits/stdc++.h>#define ll long longusing namespace std;ll a[307];bool solve() {int n;cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];sort(a + 1, a + n + 1);ll ans = a[3] - a[1];for (int i = 3;i <= n;i++) {ans = min(ans, a[i] - a[i - 2]);}cout << ans << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}B題解知識點：構造 。
注意到第 \(i\) 行的房間最多明亮值為 \(i\)，又發現只需要兩側房間安排火把已經滿足一行最大值，因此直接兩側房間 \(1\) 其他都是 \(0\)。
時間復雜度 \(O(n^2)\)
空間復雜度 \(O(1)\)
代碼#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n;cin >> n;for (int i = 1;i <= n;i++) {for (int j = 1;j <= i;j++) {if (j == 1 || j == i) cout << 1 << ' ';else cout << 0 << ' ';}cout << '\n';}return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}C題解【Div. 2 Codeforces Round #822A-F】知識點：貪心，數學 。
從小到大，把每一個要刪除的數當作 \(k\) 枚舉倍數，如果是要刪除的數花費一次 \(k\) 刪掉，如果已經刪過則無視，如果不是要刪除的數則停止換下一個 \(k\)。
時間復雜度 \(O(n\log n)\)
空間復雜度 \(O(n)\)
代碼#include <bits/stdc++.h>#define ll long longusing namespace std;int vis[1000007];bool solve() {int n;cin >> n;for (int i = 1;i <= n;i++) {char c;cin >> c;vis[i] = c == '1';}ll sum = 0;for (int i = 1;i <= n;i++) {if (vis[i] == 1) continue;for (int j = i;j <= n;j += i) {if (vis[j] == 1) break;if (vis[j] == 0) {vis[j] = 2;sum += i;}}}cout << sum << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}D題解知識點：貪心 ， 枚舉 。
先選擇一個方向直走 ， 比如先走左側 ， 走到不能再走為止，把盡頭的生命值 \(lnw\) 記錄下 。
此時考慮回頭，但顯然在左側盡頭回頭不是一定最優的，應該在走左側過程中生命值和最大處回頭才是最優的，因為這樣在走右側時可以走最多的路，因此在走左側的過程中也要記錄左側的生命和最大值 \(lmx\)。
同理從 \(lmx\) 回頭走右側時 ， 也是走到盡頭記錄右側最大生命值 \(rmx\) 和盡頭生命值 \(rnw\)。此時從 \(rmx\) 回頭走左側，應該直接從上一次的左側盡頭位置 \(lnw\) 繼續走 。
如此來回往復，直到兩側不能繼續走或者到達兩端為止 。
時間復雜度 \(O(n)\)
空間復雜度 \(O(n)\)
代碼#include <bits/stdc++.h>#define ll long longusing namespace std;int a[200007];bool solve() {int n, k;cin >> n >> k;for (int i = 1;i <= n;i++) cin >> a[i];int i = k - 1, j = k + 1;ll lmx = 0, lnw = 0, rmx = 0, rnw = 0;while (1 <= i && j <= n) {bool ok = false;while (1 <= i) {if (a[k] + lnw + rmx + a[i] < 0) break;ok = true;lnw += a[i--];lmx = max(lmx, lnw);}while (j <= n) {if (a[k] + lmx + rnw + a[j] < 0) break;ok = true;rnw += a[j++];rmx = max(rmx, rnw);}if (!ok) break;}if (i == 0 || j == n + 1) cout << "YES" << '\n';else cout << "NO" << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}E題解知識點：構造，數學 。
注意到，
\[\begin{aligned} & & a_{i_1,j_1} + a_{i_2,j_2} \not \equiv a_{i_1,j_2} + a_{i_2,j_1} \pmod n\\ &\Leftrightarrow & a_{i_2,j_2} - a_{i_2,j_1} \not \equiv a_{i_1,j_2} - a_{i_1,j_1} \pmod n\end{aligned}\]猜測一行元素具有線性關系，設 \(i_1\) 行線性系數為 \(k_1\) ，\(i_2\) 行線性系數為 \(k_2\)，于是有：
\[\begin{aligned} &\Leftrightarrow & (j_2-j_1)\cdot k_2 \not \equiv (j_2-j_1)\cdot k_1 \pmod n\end{aligned}\]根據定理：當 \(k > 0\) 時,若 \(kx \equiv ky \pmod n\) ，則 \(x \equiv y\pmod {\frac{n}{gcd(k,n)}}\)。
于是有：
\[\begin{aligned} &\Leftrightarrow & k_2 \not \equivk_1 \pmod n\end{aligned}\]因此 ， 只要每行之間的線性系數在 \(\mod n\) 意義下不同余，且在 \((i,i)\) 處經過 \(b_i\) 即可 。
顯然，\(i \in [1,n]\) 時即能保證互不同余，可以當作系數 ， 因此有公式 \(b_{i,j} = (i \cdot (j-i) + b_i) \mod n\)。

推薦閱讀