C. Sort
原题：C. Sort
标签：[[../../../数据结构与算法/前缀和]]、[[CF]]
题意
给定字符串a,b
定义
有q次询问，每次给出区间l,r，要求通过操作使
操作为将
思路
一开始由于是div3，尝试了一下是不是暴力
暴力的过法就是，每次询问都遍历一遍两个字符串的区间，然后比较各个字符的数量
比如说在a中有3个‘a’，2个’b‘，在b中有2个‘a‘3个’b‘，那么只需要将一个’b‘变成’a‘就可以
但是实际上不需要看’b‘，就看’a‘差了几个就行，只考虑补足数量不足的字符
暴力法显然过不去，然后再回看这种数量关系，很容易想到前缀和
而且每类字符单独考虑，就用类似
代码
const int N = 2e5 + 10;
int len, q;
string s1, s2;
vector<int> sum1[N];
vector<int> sum2[N];
void build() {
for (int i = 0; i <= len; i++) {
for (int j = 0; j < 26; j++) {
sum1[i][j] = 0;
sum2[i][j] = 0;
}
}
for (int i = 0; i < len; i++) {
sum1[i + 1][s1[i] - 'a']++;
sum2[i + 1][s2[i] - 'a']++;
}
for (int i = 2; i <= len; i++) {
for (int j = 0; j < 26; j++) {
sum1[i][j] += sum1[i - 1][j];
sum2[i][j] += sum2[i - 1][j];
}
}
}
void solve() {
cin >> len >> q;
cin >> s1 >> s2;
build();
int l, r;
for (int i = 0; i < q; i++) {
cin >> l >> r;
int ans = 0;
for (int j = 0; j < 26; j++) {
int t = (sum1[r][j] - sum1[l - 1][j]) - (sum2[r][j] - sum2[l - 1][j]);
if (t < 0)
ans += t;
}
cout << -ans << endl;
}
}
signed main() {
for (int i = 0; i <= N - 1; i++) {
sum1[i].resize(26, 0);
sum2[i].resize(26, 0);
}
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}D. Fun
原题：D. Fun
标签：[[../../../数据结构与算法/枚举]]、[[CF]]
题意
给定两个整数 n 和 x ，要求
输出满足条件的三元组
思路
本题在经过一系列找规律后，发现根本找不到规律。。。
找不到规律就先开始考虑暴力枚举
本题如果枚举三个数是会超时的，那么看看能不能枚举两个数
本题给的两个限定条件
如果是确定
代码
核心代码
for (int a = 1; a <= x; a++)
for (int b = 1; a * b <= n && a + b < x; b++)
ans += min(x - a - b, (n - a * b) / (a + b));E. Decode
原题：E. Decode
标签：[[../../../数据结构与算法/字符串/字符串]]、[[../../../数据结构与算法/前缀和]]、[[CF]]
题意
给定01串
答案对1e9+7取余
思路
- 出现这种数量相等的情况，一般考虑能不能用前缀和处理一下，让01的数量通过加1减1来抵消
如
index 1 2 3 4 5 6 7 8 9 10
1 1 0 0 1 1 1 0 0 1
sum 1 2 1 0 1 2 3 2 1 2以下标2到3为x,y，那么就可以在
- 那么现在的问题转变成了要怎么找到所有这样的x和y呢？
显然通过sum，对于l到r，
所以将sum值相同的下标存储在一起
- 现在的问题又转化为，该怎么快速的将答案求出来呢
在这个例子中，对于
我们先手算一下答案：
相当于是，用一个变量
流程就是，在处理完小的
代码
说明，由于我是用数组处理，所以所有负数转变成正数了
可以用map处理
#include <bits/stdc++.h>
using namespace std;
#define YES "Yes"
#define NO "No"
#define F first
#define S second
#define int long long
#define ull unsigned long long
#define endl "\n"
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define rep(i, j, k) for (i = (j); i < (k); i++)
#define all(x) x.begin(), x.end()
#define vi vector<int>
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int N = 2e5 + 10;
int ii, jj, kk;
string s;
int sum[N] = {0};
vector<int> v[2 * N];
void solve() {
cin >> s;
int len = s.length();
for (int i = 0; i < len; i++) {
if (s[i] == '1')
sum[i + 1] = sum[i] + 1;
else
sum[i + 1] = sum[i] - 1;
}
// 由于有负数的原因，将每个值+len，保证是正数
for (int i = 0; i <= len; i++)
v[sum[i] + len].push_back(i);
int ans = 0;
for (int i = 0; i <= 2 * len; i++) {
int cur = 0;
for (int vv : v[i]) {
ans = (ans + ((len + 1 - vv) * cur)) % MOD;
cur = (cur + 1 + vv) % MOD;
}
}
cout << ans << endl;
for (int i = 0; i <= 2 * len; i++)
v[i].clear();
}
signed main() {
IOS;
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}贡献者
lulaalu