呃呃这场签到一时半会没写出来就去睡觉了，睡醒已经结束，然后一题没开
更新至L,F,A,J…
(好无聊好无聊好无聊呜呜呜7.30)
题L
题意：给定一个 $n * m$ 排布的灯，有 $q$ 次操作，每次操作可以 $打开/关闭$ 某具体 $行/列$ , 问最后有多少灯是打开的（$1<=n,m,q<=1e6$）。
解：由于后面的操作会对当前操作有影响，所以不妨我们对操作倒着看，这时候第一次打开某一行或列必然是增加答案的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
int row[N], col[N];
struct S{
string x1, x2; int x;
}s[N];
int main(){
int n, m, k; cin >> n >> m >> k;
ll ans = 0;
for(int i = 1; i <= k; ++ i){
cin >> s[i].x1 >> s[i].x >> s[i].x2;
}
for(int i = k; i >= 1; -- i){
auto t = s[i];
if(t.x1 == "row"){
if(row[t.x] == 0){
row[t.x] = 1;
if(t.x2 == "on") ans += m;
n --;
}
}else {
if(col[t.x] == 0){
col[t.x] = 1;
if(t.x2 == "on") ans += n;;
m --;
}
}
}
cout << ans;
}
题F
题意：$n$ 个候选人每人都有一个 $a_i (political$ $tendencies)$，有 $n - 1$ 轮投票，每轮投票中未出局的候选人可以给一个人投票，票数最多者出局，其中对于 $i$ 这个候选人而言，他会投给 $j$ 候选人，当且仅当存在最大的 $|a_i - a_j|$, 如果同时存在了两个相同最大值的$|a_i - a_j|$ ， 那么优先投给$a_j$ 较大的人。问最后剩下来的是几号候选人。
解：由题意可得，每轮出局的必然是剩余候选人中 $a_i$ 值是 $最大/最小$， 那么我们可以对 $a_i$ 排完序后对两端用双指针，将两个指针与中间候选人的 $a_{mid}$ 进行比较。 最终复杂度为 $O(n)$
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
pair<int, int> p[N];
int main(){
int n; cin >> n;
for(int i = 1; i <= n; ++ i){
int x; cin >> x;
p[i] = {x, i};
}
sort(p + 1, p + 1 + n);
int l = 1, r = n;
while(l < r){
int mid = l + r >> 1;
if(2 * p[mid].first > p[l].first + p[r].first)
l ++;
else
r --;
}
cout << p[l].second;
}
题A
题意：已知一个消息字符串 $s$, 其加密字符串为 $t+s+t$，其中字符串 $t$ 为识别字符串，用于解码。但对于本题中读取加密字符串是一个个字符读取，当加密字符串 $0101101010$， 已知$t=010$, 其标准的消息字符串 $s=1101$, 但由于读取过程的问题，在计算机读取了加密字符到 $01011010$ 时就会停止并且获得消息字符串 $s=11$ 与需求不符，存在歧义。 题目给定消息字符串 $s$ 的长度和识别字符串 $t$，要求任意构造一个不存在歧义的消息字符串 $s$（$1<=|t|, n<=1000$, 本题中字符串由 $01$ 构成）。
解：由于可以任意构造且字符串的长度很小，而且我们是知道识别字符串 $t$的， 那么首先要使得 $s$中不存在 $t$，我们可以直接假设 $s$ 全为 $0$， 用 $find$ 函数查看是否存在歧义，存在则用全 $1$ 代替。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
void solve(){
int n, f = 0; string t; cin >> n >> t; string x = t;
for(int i = 1; i <= n; ++ i) x = x + "0"; x = x + t;
if(x.find(t, 1) != x.size() - t.size()) f = 1;
for(int i = 1; i <= n; ++ i) cout << f; cout << '\n';
}
int main(){
int T; cin >> T;
while(T --) solve();
}
题J
题意：给定整数 $n$ 和 $m$，要求构造长度为 $n$ 的数组 $a$，其中 $-m<=a_i<=m$, 对任意 $2<=k<=n$，满足连续 $k$ 个元素和 $>=0$，问存在多少种构造情况$(1<=n,m<=5000, 答案模998244252)$
解：用 $dp[i][j]$ 表示前 $i$ 个元素种包含第 $i$ 个元素最小和为 $j$ 的情况数。我们再用一个 $sum[i][j]$ 表示包含第 $i$ 个元素和为 $j$ 的情况数，这样我们对和从大到小枚举，就 $O(n*m)$ 跑过。
#include<iostream>
using namespace std;
const int N = 5010, MOD = 998244353;
int dp[N][N + N], sum[N][N + N];
int main(){
int n, m; cin >> n >> m;
for(int i = m; i >= -m; -- i) {
sum[1][i + N] = 1;
dp[1][i + N] = dp[1][i + N + 1] + sum[1][i + N];
}
for(int i = 2; i <= n; ++ i){
for(int j = m; j >= -m; -- j){
if(j >= 0) sum[i][j + N] = dp[i - 1][j + N - m];
else sum[i][j + N] = dp[i - 1][N - j];
dp[i][j + N] = (dp[i][j + N + 1] + sum[i][j + N]) % MOD;
}
}
cout << dp[n][N - m];
}