A. Legs
若只判断题，根据模4意义下分类即可。
B. Scale
模拟题，缩小同值矩阵即可。
C. Sort
对每个字母求前缀数量和，答案就是两端点的差。
const int N = 2e5 + 5;
int T, n, q; char a[N], b[N]; int c[N][26], d[N][26];
signed main(void) {
for (read(T); T; T--) {
read(n), read(q);
readstr(a + 1); readstr(b + 1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 26; j++) c[i][j] = c[i - 1][j], d[i][j] = d[i - 1][j];
c[i][a[i] - 'a']++; d[i][b[i] - 'a']++;
}
for (int l, r; q; q--) {
read(l), read(r); int ans = 0;
for (int i = 0; i < 26; i++) {
int cnt = (c[r][i] - c[l - 1][i]) - (d[r][i] - d[l - 1][i]);
if (cnt > 0) ans += cnt;
} writeln(ans);
}
}
// fwrite(pf, 1, o1 - pf, stdout);
return 0;
}
D. Fun
由两个不等式，在枚举 \(a\) 的时候可以限制 \(b\) 右端点，在确定两者的情况下可以直接算出 \(c = min((n - a * b) / (a + b), x - (a + b))\)
int T, n, x; ll ans;
signed main(void) {
for (read(T); T; T--) {
read(n), read(x); ans = 0;
int m = min(n, x);
for (int a = 1; a <= m; a++) {
for (int b = 1; b * a < n && a + b < x; b++) {
int c = min((n - a * b) / (a + b), x - (a + b));
ans += c;
}
} writeln(ans);
}
// fwrite(pf, 1, o1 - pf, stdout);
return 0;
}
E. Decode
如何有效地检查一个数组是否包含相同数量的 0 和 1？其实就是其中一个的数量是区间长度的一半，将这个式子移项并平移，可以得到类似计数端点相同值的等价表达。
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int T, n, b[N], ans, c[2 * N]; char a[N];
//inline void update(int pos, int val) {
// for ( ; pos <= 2 * n; pos += lowbit(pos)) c[pos] = (c[pos] + val) % mod;
//}
//
//inline int query(int pos) {
// int ret = 0;
// for (; pos; pos -= lowbit(pos)) ret = (ret + c[pos]) % mod;
// return ret;
//}
signed main(void) {
for (read(T); T; T--) {
readstr(a + 1); n = strlen(a + 1); ans = 0;
c[n + 1] = 1;
for (int i = 1; i <= n; i++) {
b[i] = b[i - 1] + (a[i] == '1');
int pos = 2 * b[i] - i + n + 1;
int x = c[pos];
ans = (ans + 1ll * x * (n - i + 1) % mod) % mod;
while (ans < 0) ans += mod;
c[pos] = (c[pos] + 1 + i) % mod;
}
for (int i = 0; i <= 2 * n + 1; i++) c[i] = 0;
writeln(ans);
}
// fwrite(pf, 1, o1 - pf, stdout);
return 0;
}
F. Bomb
由单调性考虑二分来求出 \(k\) 次操作是否能把所有数减到小于等于某个 \(x\)， 再由这个边界去计算答案。
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
#define int long long
int T, n, k, a[N], b[N];
inline bool check(int x) {
int cnt = 0;
for (int i = 1; i <= n; i++) if (a[i] >= x) {
cnt += (a[i] - x) / b[i] + 1;
}
return cnt >= k;
}
inline ll calc(int x) {
ll ret = 0; int cnt = 0;
for (int i = 1; i <= n; i++) if (a[i] >= x) {
int t = (a[i] - x) / b[i] + 1;
cnt += t;
ret += 1ll * t * a[i] - 1ll * t * (t - 1) / 2ll * b[i];
}
if (x > 0) ret += 1ll * (k - cnt) * x;
return ret;
}
signed main(void) {
for (read(T); T; T--) {
read(n), read(k); int x = 0;
for (int i = 1; i <= n; i++) read(a[i]), chkmax(x, a[i]);
for (int i = 1; i <= n; i++) read(b[i]);
int l = 1, r = x, ans = 0;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) ans = mid, l = mid + 1;
else r = mid - 1;
}
writeln(calc(ans));
}
// fwrite(pf, 1, o1 - pf, stdout);
return 0;
}
G. Penacony
两种做法：一个是常规的线段树扫描线，因为确定一种取法后，按顺序枚举删去的边，所有路径选法都确定了，再加上只要按顺序每条路径方向只变化两次，可以线段树维护区间加减和区间 \(0\) 的个数来做。另一种做法是 \(Xor-Hash\) ,我们发现，选择修改某一条路径的方向，就是翻转了全局对于这条路径的选择情况，容易想到差分异或。给每对点一个随机值，再求前缀。只要维护出现次数最多的数即可（将他们统统去除，维护他们的补集）。
mt19937_64 rnd((unsigned int)chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e5 + 5;
int T, n, m, mx; ll a[N];
unordered_map <ll, int> h;
signed main(void) {
for (read(T); T; T--) {
read(n), read(m); h.clear(); mx = 0;
for (int i = 1; i <= n; i++) a[i] = 0;
while (m--) {
int x, y; ll r = rnd();
read(x), read(y);
a[x] ^= r; a[y] ^= r;
}
for (int i = 1; i <= n; i++) a[i] ^= a[i - 1], h[a[i]]++;
for (auto u : h) chkmax(mx, u.second);
writeln(n - mx);
}
//fwrite(pf, 1, o1 - pf, stdout);
return 0;
}