比赛链接
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\)。
推荐阅读
- Div. 2 Codeforces Round #823 A-D
- [题解] Codeforces Global Round 22 1738 A B C D E F 题解
- round函数怎么用 python的round函数怎么用
- turn around英语怎么读 round英语怎么读
- apple round什么意思 apple round是什么食物
- background什么意思 Background什么意思?
- gym是什么意思中文翻译playground gym是什么意思中文
- playground是什么意思英语翻译 playground是什么意思