C
题目大意
给定两个字符串a，b，q个询问，每次操作可以将a[i]赋值为任意一个字符，每次询问[l , r]区间内使得sorted(a[l, r]) == sorted(b[l, r])的最小操作次数
分析
不妨先考虑一个区间如何判断sorted后的字串是否相等，发现跟字符出现的次数有关，于是考虑前缀和预处理每一个26个字母分别出现的次数，答案为不同字符数量之和除以2。时间复杂度O(q)。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n, q;
cin >> n >> q;
string a, b;
cin >> a >> b;
a = " " + a, b = " " + b;
vector<vector<int>> mp1(n + 1, vector<int> (26)), mp2(n + 1, vector<int> (26));
for (int i = 1; i <= n; i++) {
for (char j = 'a'; j <= 'z'; j++) {
mp1[i][j - 'a'] = mp1[i - 1][j - 'a'];
mp2[i][j - 'a'] = mp2[i - 1][j - 'a'];
}
mp1[i][a[i] - 'a']++;
mp2[i][b[i] - 'a']++;
}
while (q--) {
int l, r, ans = 0;
cin >> l >> r;
for (char i = 'a'; i <= 'z'; i++) {
ans += abs(mp1[r][i - 'a'] - mp1[l - 1][i - 'a'] - mp2[r][i - 'a'] + mp2[l - 1][i - 'a']);
}
cout << ans / 2 << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
D
题目大意
给定n, x，计算有多少个三元组(a, b, c)满足 a * b + b * c + a * c <= n 且 a + b + c <= x。a, b, c均为正整数。
分析
不难想到先固定一个数再去考虑其他的数，不妨固定a，那么根据两个不等式，我们可以发现b <= n / a 且 b <= x - a - 1，因此b <= min(n / a, x - a - 1)。枚举b，每次答案加上min((n - a * b) / (a + b), x - a - b)即可。
时间复杂度为O(min(n, x)sqrt(min(n, x)))
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n, x;
cin >> n >> x;
i64 ans = 0;
for (int i = 1; i <= min(n, x); i++) {
for (int j = 1; j <= n / i && j <= x - i - 1; j++) {
int c = min((n - i * j) / (i + j), x - i - j);
ans += 1ll * c;
}
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
E
题目大意
给定一个01串，求出所有的区间[l, r]的数量，使得其中至少有一个子区间[x, y]满足x到y中的0和1的计数相等。
分析
从01串和区间问题不难想到前缀和的思想，如果是0，就加上-1，如果是1，就加上1，这样一来，所有前缀和为0的位置的贡献为n - i + 1(假设i为当前位置)。考虑前缀和不为0的情况，当pre[y] == pre[x - 1]时，显然L有x中取法，R有n - y + 1种取法，总方案数为x * (n - y + 1)。因此我们可以先预处理种每一种前缀下R的取法数之和，枚举x - 1，如果存在pre[x - 1]，就加上与之匹配的R的方案数。注意枚举的x - 1，因此L的方案数应为i + 1。
时间复杂度为O(nlogn)
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int mod = 1e9 + 7;
void solve() {
string s;
cin >> s;
int n = s.size();
s = " " + s;
vector<i64> pre(n + 1);
map<int, i64> f;
for (int i = 1; i <= n; i++) {
pre[i] = (s[i] == '1' ? pre[i - 1] + 1 : pre[i - 1] - 1);
f[pre[i]] += n - i + 1;
}
i64 ans = 0;
for (int i = 1; i <= n; i++) {
if (f[pre[i]]) {
f[pre[i]] -= n - i + 1;
ans = (ans + 1ll * f[pre[i]] * (i + 1)) % mod;
if (pre[i] == 0) ans = (ans + n - i + 1) % mod;
}
}
cout << (ans + mod) % mod << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}