A.Bobo String Construction题意:
给定一个01串t，构造一个长度为n的01串s，时的t + s + t中t只在首和尾出现。
分析：
结论，s取全0或者全1。
①t全0或者全1，那我s和t取相反的即可。
②t既包含0又包含1，首先t不可能是s的子串，那我们只需考虑t是否可以由t的后缀加上s再加上t的前缀得到。假设对于当前的串s全0且存在t的后缀加上s加上t的前缀等于t，那么我们将s变为全1则一定不等于t，当前串s全为1同理。
综上，我们只需要分别判断s全为0和全为1即可。
代码：
#include using namespace std;int check(string &s, string &s2) { int cnt = 0; for (int i = 0; i > t; while (t --) { int n; string s, s0, s1; cin >> n >> s; for (int i = 0; i < n; i ++) { s0 += '0'; s1 += '1'; } string s3 = s + s0 + s; if (check(s3, s) == 2) cout << s0 << endl; else cout << s1 << endl; } return 0;}F.Election of the King题意：
有n个人竞选国王，\(a_i\)表示第i个人的从政理念，每轮通过投票淘汰一位竞选者，每个人将投给与自己从政理念相差最大的人。
票数最多的将被淘汰，如果票数相同淘汰值最大的，如果值相同则淘汰编号最大的。
分析：
由于每个人投的是与自己执政理念相差最大的人，因此每个人要么投给值最大的要么投给值最小的，最终的决定权将落在值中间的那个人。可以将所有人优先按值从小到大排序，若值相同则按编号从小到大排序，最后不断让中间那个来决定淘汰谁即可。
代码：
#include using namespace std;const int N = 1e6 + 5;struct P { int a, id;}p[N];bool cmp(P &A, P &B) { if (A.a != B.a) return A.a < B.a; else return A.id > n; for (int i = 1; i > p[i].a; p[i].id = i; } sort(p + 1, p + 1 + n, cmp); int l = 1, r = n; while (l > 1; if (abs(p[mid].a - p[l].a) > abs(p[mid].a - p[r].a)) l ++; else if (abs(p[mid].a - p[l].a) < abs(p[mid].a - p[r].a)) r --; else { r --; } } cout << p[l].id; return 0;}J.Qu’est-ce Que C’est?题意:
给定n和m，求能构造出满足下面条件的序列的数量。
①每个数在[-m, m]的范围内
②任意长度大于等于2的区间和>=0
分析:
考虑dp。
状态定义：f[i][j]表示前i个数中后缀最小值为j的方案数。
状态转移：
①j >= 0，能够转移过来的前一个状态后缀最小值的下限为j – m，因此f[i][j] = \(\sum_{k = j – m}^m f[i – 1][k]\)
②j =0，所以最小后缀只有可能是第i个数自己，能够转移过来的前一个状态后缀最小值的下限即为-j， 因此f[i][j] = \(\sum_{k = -j}^m f[i – 1][k]\)
答案即为：\(\sum_{j = -m}^m f[n][j]\)
代码：
#include using namespace std;const int N = 5010, M = 10010, mod = 998244353;int f[N][M], s[N][M]; // s优化求和部分int main() { std::ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n, m; cin >> n >> m; for (int i = 2 * m; i >= 0; i --) { f[1][i] = 1; s[1][i] = s[1][i + 1] + 1; } for (int i = 2; i <= n; i ++) { for (int j = -m; j <= m; j ++) { if (j = -m; j --) { s[i][j + m] = (s[i][j + m] + s[i][j + m + 1] + f[i][j + m]) % mod; } } cout << s[n][0]; return 0;}L.We are the Lights题意：
n × m的灯阵，初始全灭。每次操作可将某一行或者某一列的灯全开/全关。问q次操作过后有多少台灯亮着。
分析：
可以发现只有最后一步才决定灯的状态，因此我们可以倒着去维护亮着灯的数量。
代码：
#include using namespace std;const int N = 1e6 + 5;typedef long long LL;bool row[N], col[N];struct Q { string s, op; int idx;}q[N], q2[N];LL cnt, cntr, cntc;int main() { std::ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n, m, t; cin >> n >> m >> t; for (int i = 0; i > s >> idx >> op; q[i] = {s, op, idx}; } for (int i = t - 1; i >= 0; i --) { string s = q[i].s, op = q[i].op; int idx = q[i].idx; if (s == "row" && !row[idx]) { row[idx] = true; q2[cnt ++] = {s, op, idx}; } else if (s == "column" && !col[idx]) { col[idx] = true; q2[cnt ++] = {s, op, idx}; } } LL res = 0; for (int i = cnt - 1; i >= 0; i --) { string s = q2[i].s, op = q2[i].op; int idx = q2[i].idx; if (s == "row") { if (op == "on") { res += (m - cntc); cntr ++; } else { if (res > 0) res -= cntc; } } else if (s == "column") { if (op == "on") { res += (n - cntr); cntc ++; } else { if (res > 0) res -= cntr; } } } cout << res; return 0;}