题目链接：Codeforces Round 962 (Div. 3)
总结：ABC秒过，D有点难评了，E优化很妙。
A. Legs
tag：签到
void solve(){
cin >> n;
int a = n / 4, b = n % 4;
a += b / 2;
cout << a << endl;
}
B. Scale
tag：模拟
void solve(){
cin >> n >> k;
vector a(n + 1, vector<char>(n + 1));
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
cin >> a[i][j];
for (int i = 1; i <= n; i += k){
for (int j = 1; j <= n; j += k)
cout << a[i][j];
cout << endl;
}
}
C. Sort
tag: 前缀和
Description：给定两个字符串\(a, b\)，有\(q\)次查询，每次查询给定\(l_i, r_i\)。每次操作可以将一个\(a_i\)变成一个字符\(x\)；求每次询问令\(sort(al, ar) == sort(bl, br)\)的最小操作次数。
Solution：典型的trick，使用前缀和记录一下每个字符出现的次数，这样我们就可以\(O(1)\)得到每个区间内每个字符的个数。
void solve(){
int q;
cin >> n >> q;
string a, b;
cin >> a >> b;
a = "$" + a;
b = "$" + b;
vector ta(n + 1, vector<int>(26));
vector tb(n + 1, vector<int>(26));
for (int i = 1; i <= n; i ++){
ta[i] = ta[i - 1];
tb[i] = tb[i - 1];
ta[i][a[i] - 'a'] ++;
tb[i][b[i] - 'a'] ++;
}
while (q --){
int l, r;
cin >> l >> r;
vector<int> t(26), tt(26);
int cnt = 0;
for (int i = 0; i < 26; i ++){
t[i] = ta[r][i] - ta[l - 1][i];
tt[i] = tb[r][i] - tb[l - 1][i];
cnt += abs(t[i] - tt[i]);
}
cout << cnt / 2 << endl;
}
}
D. Fun
tag：数学
Description：给定\(n, x\)，求三元组\(a, b, c\)满足\(a * b + a * b + b * c <= n \and a + b +c <= x\)的三元组的数量。
Solution：注意到是不等式显然需要化简，我们枚举\(a, b\)的值，那么\(c <= (n - a *b ) / (a + b) \and c <= x - (a + b)\)。时间复杂度是一个调和机数，\(n + n / 2 + n / 3 + ... + 1\)
void solve(){
int x;
cin >> n >> x;
int ans = 0;
for (int a = 1; a < n; a ++)
for (int b = 1; a * b < n; b ++){
ans += max(0LL, min((n - a * b) / (a + b), x - a - b));
}
cout << ans << endl;
}
E. Decode
tag：前缀和 + 优化
Description：给定一个\(0,1\)字符串\(s\)，对于所有\(1 <= l <= r <= n\)，求有多少对\(x, y\)，\(l <= x <= y <= r\)，且\([s_x, s_y]\)中两种字符的数量相等。
Solution：显然对于一个\(x, y\)区间，对所有包含它们的\(l, r\)都会有一个贡献，那么总贡献为\(x * (n - y + 1)\)。
- 但是对于同一个\(y\)可能有多个\(x\)，使用vector存储会TLE。
- 我们考虑同一个\(y\)，两个\(x\)的贡献：\(x_1 * (n - y + 1) + x_2 * (n - y + 1) == (x_1 + x_2) * (n - y + 1)\)化简后可知，我们只需要将相同状态的下标和相加即可。
void solve(){
string s;
cin >> s;
s = "&" + s;
map<int, int> mp;
int ans = 0;
int t = 0;
mp[0] = 1;
for (int i = 1; i < s.size(); i ++){
if (s[i] == '1')
t ++;
else
t --;
ans += (s.size() - i) * (mp[t]) % mod;
ans %= mod;
mp[t] += i + 1;
mp[t] %= mod;
}
cout << ans << endl;
}
F. Bomb
tag: 二分
Description：给定两个长度为\(n\)的数组，可以执行\(k\)次操作，每次操作后\(ai\)变为\(max(0, ai - bi)\)，得分加\(ai\)，求最高得分。1 <= n <= 1e5, 1 <= k <= 1e9。
Solution：显然我们需要每次取最大的\(ai\)，但是暴力会超时。我们发现每个数都变化是一个等差数列，那么能否知道每个数最后会变为多少呢？
- 考虑使用二分找到变化后数组中最大值的最小值\(x\)（即数组中所有值都不能超过这个值）。
- 如果操作次数小于\(k\)，那么剩下的操作次数一定小于数组中\(x\)的数量，否则\(x\)可以更小。
void solve(){
cin >> n >> k;
vector<int> a(n), b(n);
for (int i = 0; i < n; i ++)
cin >> a[i];
for (int i = 0; i < n; i ++)
cin >> b[i];
int ans = 0;
auto check = [&](int &mid, int &t, int &res) -> bool{
res = 0, t = 0;
for (int i = 0; i < n; i ++){
if (a[i] <= mid)
continue;
int tt = (a[i] - mid + b[i] - 1) / b[i];
res += tt;
t += (a[i] + a[i] - b[i] *(tt - 1)) * tt / 2;
}
if (res > k)
return true;
return false;
};
int l = -1, r = 1e15, t, res;
while (l + 1 < r){
int mid = l + r >> 1;
if (check(mid, t, res))
l = mid;
else
r = mid;
}
cout << t + (k - res) * r << endl;
}