A
题解
知识点：贪心。
注意到任意三根木棍的相等最优解是最长减最小，因此从小到大排序，三个三个取，取最小值。
时间复杂度 (O(nlog n))
空间复杂度 (O(n))
代码
#include <bits/stdc++.h> #define ll long long using 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 long using 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(nlog n))
空间复杂度 (O(n))
代码
#include <bits/stdc++.h> #define ll long long using 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 long using 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
题解
知识点：构造，数学。
注意到，
猜测一行元素具有线性关系，设 (i_1) 行线性系数为 (k_1) ，(i_2) 行线性系数为 (k_2) ，于是有：
根据定理：当 (k > 0) 时,若 (kx equiv ky pmod n) ，则 (x equiv ypmod {frac{n}{gcd(k,n)}}) 。
于是有：
因此，只要每行之间的线性系数在 (mod n) 意义下不同余，且在 ((i,i)) 处经过 (b_i) 即可。
显然，(i in [1,n]) 时即能保证互不同余，可以当作系数，因此有公式 (b_{i,j} = (i cdot (j-i) + b_i) mod n) 。
时间复杂度 (O(n^2))
空间复杂度 (O(n^2))
代码
#include <bits/stdc++.h> #define ll long long using namespace std; int a[357][357], b[357]; bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) cin >> b[i]; for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) { a[i][j] = ((i * (j - i) + b[i]) % n + n) % n; } } for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) { cout << a[i][j] << ' '; } 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; } F
题解
知识点：记忆化搜索，线性dp，数学，位运算。
先是一个结论：定义函数 (parity(a)) 表示 (a) 二进制位 (1) 的个数的奇偶性（奇数返回 (1) ，偶数返回 (0)），那么 (S_i = parity(i)) 。
证明非常简单：
- 由于 (S) 的生成方法是每次都从原来的一份取反得到 (S') 放到 (S) 末尾，所以第 (k(kgeq 1)) 次扩展后 (S) 的编号一定是 ([0,2^{k-1}]) 。
- 对于第 (k+1) 次新生成的 (S') 中的每一位编号 (i') ，满足 (i’ = i + 2^k) ，因为编号 (i) 的第 (k) 位之前一定是 (0)，所以这次变换实际上是将编号 (i) 的第 (k) 位变为 (1) 作为编号 (i')。
- 显然，所有数字都是从编号 (0) 开始数次变换得到的，每次变换都会将编号的一位 (0) 变为 (1) ，因此我们记录二进制 (1) 的数量就能得知这个编号从 (0) 变换了多少次。
- (S_0 = 0) ，所以编号 (i) 有偶数个 (1) 就是变了偶数次，故 (S_i=0) ，否则 (S_i = 1) 。即 (S_i = parity(i)) 。
有了这个结论，我们就可以对问题进行量化。记原问题答案为 (f(n,m)) ，有 (f(n,m) = sum_{i = 0}^{m-1} [parity(i) neq parity(n+i)]) 。
当 (m = 0) 时，显然有 (f(n,0) = 0) 。
当 (m) 为奇数时，先对末尾判断再对 (m-1) 讨论（偶数讨论方便一点），有 (f(n,m) = f(n,m-1) + [parity(i) neq parity(n+i)]) 。
当 (m) 为偶数时：
-
(n) 为偶数，有如下关系：
[begin{aligned} && &parity(2k) neq parity(n+2k) \ &Leftrightarrow& &parity(2k+1) neq parity(n+2k+1)\ end{aligned} ]因为偶数末尾总是 (0) ，加 (1) 不会影响其余的二进制位，所以 (1) 的数量明确加 (1) ，奇偶性一定同时改变。
[begin{aligned} && &parity(2k) neq parity(n+2k) \ &Leftrightarrow& &parity(k) neq parity(frac{n}{2}+k) end{aligned} ]因为偶数末尾总是 (0) ，删去这个 (0) 后，数字奇偶性不变。
那么有如下公式：
[begin{aligned} f(n,m) &= sum_{i = 0}^{m-1} [parity(i) neq parity(n+i)]\ &= 2sum_{k = 0}^{frac{m}{2}-1} [parity(2k) neq parity(n+2k)]\ &= 2sum_{k = 0}^{frac{m}{2}-1} [parity(k) neq parity(frac{n}{2}+k)]\ &= 2f(frac{n}{2},frac{m}{2}) end{aligned} ] -
(n) 为奇数，有如下关系：
[begin{aligned} && &parity(2k) neq parity(n+2k) \ &Leftrightarrow& &parity(2k) = parity(n+2k-1)\ &Leftrightarrow& &parity(k) = parity(frac{n-1}{2}+k)\ end{aligned} ]以及，
[begin{aligned} && &parity(2k+1) neq parity(n+2k+1) \ &Leftrightarrow& &parity(2k) = parity(n+2k+1)\ &Leftrightarrow& &parity(k) = parity(frac{n+1}{2}+k)\ end{aligned} ]证明同上。
[begin{aligned} f(n,m) &= sum_{i = 0}^{m-1} [parity(i) neq parity(n+i)]\ &= sum_{k = 0}^{frac{m}{2}-1} ([parity(2k) = parity(n+2k-1)] + [parity(2k) = parity(n+2k+1)])\ &= sum_{k = 0}^{frac{m}{2}-1} ([parity(k) = parity(frac{n-1}{2}+k)] + [parity(k) = parity(frac{n+1}{2}+k)])\ &= m - f(frac{n-1}{2},frac{m}{2}) - f(frac{n+1}{2},frac{m}{2}) end{aligned} ]
至此，我们就可以通过记忆化搜索进行求解了。
时间复杂度 (O(log n log m))
空间复杂度 (O(log n log m))
代码
#include <bits/stdc++.h> #define ll long long using namespace std; bool check(ll a, ll b) { return __builtin_parityll(a) != __builtin_parityll(b); } map<pair<ll, ll>, ll> mp; ll f(ll n, ll m) { if (m == 0) return 0; if (mp.count({ n,m })) return mp[{n, m}]; if (m & 1) return mp[{n, m}] = f(n, m - 1) + check(m - 1, n + m - 1); if (n & 1) return mp[{n, m}] = m - f(n / 2, m / 2) - f((n + 1) / 2, m / 2); else return mp[{n, m}] = 2 * f(n / 2, m / 2); } bool solve() { ll n, m; cin >> n >> m; cout << f(n, m) << '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; } 
