比赛链接
A题解知识点：KMP，构造。
考虑构造全 \(0,1\) 串，至少有一个可行。
(相关资料图)
我们只需要考虑到 \(t\) 的border \(t"\) ，即 \(t"+s+t"\) ：
当 \(t"+s+t"\) 总长小于等于 \(t\) ，显然成立。否则， 若 \(t"+s+t"\) 中有子串等于 \(t\) ，那么这个子串不会完整包含前后两端的 \(t"\) ，这时border就会相交，产生连锁反应，可以证得 \(t\) 是全 \(0,1\) 串，此时显然成立。若没有子串等于 \(t\) ，则直接可行。因此，我们只需要构造两次检查一下即可，检查方式有KMP、Z函数、哈希等等。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include using namespace std;using ll = long long;class KMP { int m; string p; vector nxt;public: KMP() {} KMP(const string &_p) { init(_p); } void init(const string &_p) { m = _p.size() - 1; p = _p; nxt.assign(m + 1, 0); for (int i = 2;i <= m;i++) { nxt[i] = nxt[i - 1]; while (nxt[i] && p[i] != p[nxt[i] + 1]) nxt[i] = nxt[nxt[i]]; nxt[i] += p[i] == p[nxt[i] + 1]; } } vector find(const string &s) { int n = s.size() - 1; vector pos; for (int i = 1, j = 0;i <= n;i++) { while (j && s[i] != p[j + 1]) j = nxt[j]; j += s[i] == p[j + 1]; if (j == m) { pos.push_back(i - j + 1); j = nxt[j]; } } return pos; } vector get_cycle_time() { vector res; int pos = m; while (pos) { pos = nxt[pos]; res.push_back(m - pos); } return res; } vector get_cycle_loop() { vector res; for (auto val : get_cycle_time()) if (!(m % val)) res.push_back(val); return res; } int min_cycle_loop() { return get_cycle_loop()[0]; } void debug() { for (int i = 1;i <= m;i++) cout << nxt[i] << " \n"[i == m]; }};/// KMP，前缀函数O(|P|)、查找O(|S|+|P|)、循环相关O(|P|)，维护字符串前缀函数bool solve() { int n; cin >> n; string t; cin >> t; KMP kmp("?" + t); if (kmp.find("?" + t + string(n, "0") + t).size() <= 2) cout << string(n, "0") << "\n"; else cout << string(n, "1") << "\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;} 知识点：二分，贪心。
显然每次只有最小值和最大值会被票出。
具体来说，我们统计最大值和最小值中点左右两侧的人数，左侧一定给最大值票，右侧一定给最小值票。当左大于等于右时，最大值会被票出，否则最小值会被票出。
因此，我们排序后，用二分找到中点的位置，用双指针表示当前剩余区间。
时间复杂度 \(O(n\log n)\)
空间复杂度 \(O(n)\)
代码#include using namespace std;using ll = long long;int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; vector> a(n + 1); for (int i = 1;i <= n;i++) { int x; cin >> x; a[i] = { x,i }; } sort(a.begin() + 1, a.end()); int l = 1, r = n; for (int i = 1;i <= n - 1;i++) { int mid = a[l].first + a[r].first >> 1; int it = upper_bound(a.begin() + l, a.begin() + r + 1, pair{ mid, 2e9 }) - a.begin(); int lval = it - l; int rval = r - it + 1; if (lval >= rval) r--; else l++; } cout << a[l].second << "\n"; return 0;} 知识点：构造。
尝试在正方形对角线上选择一点，将正方形分为左上正方形，右下正方形和两个对称的长方形。
然后，按照类似gcd的方式，对长方形进行划分正方形。
可以统计得到一定存在一点，使得长方形划分后的正方形数量不超过 \(24\) ，即总和不超过 \(50\) 。
因此，我们递归执行两种操作即可。
时间复杂度 \(O(n^2)\)
空间复杂度 \(O(n^2)\)
代码#include using namespace std;using ll = long long;int gcd(int a, int b, int &cnt) { if (b) { cnt += a / b; return gcd(b, a % b, cnt); } else return a;}vector> ans;void dfs_rec(int x, int y, int a, int b);void dfs_sqr(int x, int y, int a);void dfs_rec(int x, int y, int a, int b) { bool sw = a < b; if (sw) swap(x, y), swap(a, b); if (!b) return; for (int i = b;i <= a;i += b) { if (sw) dfs_sqr(y, x + i - b, b); else dfs_sqr(x + i - b, y, b); } if (sw) dfs_rec(y, x + a / b * b, b, a % b); else dfs_rec(x + a / b * b, y, a % b, b);}void dfs_sqr(int x, int y, int a) { if (a == 1) return; if (a <= 7) { ans.push_back({ x,y,a }); return; } bool ok = 0; for (int i = 1;i <= a - 1;i++) { int cnt = 0; gcd(i, a - i, cnt); if (cnt >= 25) continue; ok = 1; dfs_sqr(x, y, i); dfs_rec(x + i, y, a - i, i); dfs_rec(x, y + i, i, a - i); dfs_sqr(x + i, y + i, a - i); break; } assert(ok); ans.push_back({ x,y,a });}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; dfs_sqr(1, 1, n); cout << ans.size() << "\n"; for (auto [x, y, a] : ans) cout << x << " " << y << " " << a << "\n"; return 0;} 知识点：线性dp，前缀和。
考虑设 \(f_{i,j}\) 为考虑了前 \(i\) 个数的后缀（不可为空）最小值为 \(j\) 时的方案数。显然， \(j \in [-m,m]\) 中。
在 \(f_{i-1,j}\) 时，\([-j,m]\) 的数字可以被使用，进一步分类讨论转移方程：
当 \(j\geq 0\) 时，后缀最小值更新为 \(a_i\) 本身：
\[f_{i-1,j} \to f_{i,[-j,m]}\]当 \(j < 0\) 时，后缀最小值更新为 \(a_i + j\) ：
\[f_{i-1,j} \to f_{i,[0,m+j]}\]用前缀和优化转移即可。
时间复杂度 \(O(nm)\)
空间复杂度 \(O(m)\)
代码#include using namespace std;using ll = long long;const int P = 998244353;int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m; cin >> n >> m; vector f(2 * m + 1); f[2 * m] = 1; for (int i = 0;i < n;i++) { vector g(2 * m + 1); for (int j = -m;j <= m;j++) { if (j >= 0) (g[-j + m] += f[j + m]) %= P; else { (g[0 + m] += f[j + m]) %= P; (g[j + m + m + 1] -= f[j + m] - P) %= P; } } for (int j = -m + 1;j <= m;j++) (g[j + m] += g[j - 1 + m]) %= P; swap(f, g); } int ans = 0; for (int i = -m;i <= m;i++) (ans += f[i + m]) %= P; cout << ans << "\n"; return 0;} 知识点：离线，枚举。
考虑离线后倒着操作，并统计行的个数。
显然每行每列只关心最后一次操作的类型，之后的操作不需要考虑。
记录列开、列关的列数分别为 \(cnt_{on},cnt_{off}\) 。若行操作为打开，答案增加 \(m - cnt_{off}\) ，否则增加 \(cnt_{on}\) 。
最后统计没被操作的行，对于每行答案增加 \(cnt_{on}\) 。
时间复杂度 \(O(n+q)\)
空间复杂度 \(O(n+m+q)\)
代码#include using namespace std;using ll = long long;struct Query { bool row; int id; bool on;}Q[1000007];bool row_vis[1000007];bool col_vis[1000007];int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m, q; cin >> n >> m >> q; for (int i = 1;i <= q;i++) { string row; int id; string on; cin >> row >> id >> on; Q[i] = { row == "row",id,on == "on" }; } ll ans = 0; int cnt_on = 0, cnt_off = 0; for (int i = q;i >= 1;i--) { if (Q[i].row) { if (row_vis[Q[i].id]) continue; ans += Q[i].on ? m - cnt_off : cnt_on; row_vis[Q[i].id] = 1; } else { if (col_vis[Q[i].id]) continue; if (Q[i].on) cnt_on++; else cnt_off++; col_vis[Q[i].id] = 1; } } for (int i = 1;i <= n;i++) if (!row_vis[i]) ans += cnt_on; cout << ans << "\n"; return 0;} 
