比赛链接
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题解知识点：贪心 ， 数学 。
从小到大 ， 把每一个要删除的数当作 \(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;}