时间：2024-07-27
C. Sort
原题：C. Sort
标签：前缀和
题意
给定字符串a,b
定义 \(sorted(a[l..r])\) 表示将a的lr区间排序为有序
有q次询问，每次给出区间l,r，要求通过操作使\(sorted(a[l..r])==sorted(b[l..r])\)
操作为将\(a_i\)变成需要的任意字符，求最少次数
思路
一开始由于是div3，尝试了一下是不是暴力
暴力的过法就是，每次询问都遍历一遍两个字符串的区间，然后比较各个字符的数量
比如说在a中有3个‘a’，2个’b‘，在b中有2个‘a‘3个’b‘，那么只需要将一个’b‘变成’a‘就可以
但是实际上不需要看’b‘，就看’a‘差了几个就行，只考虑补足数量不足的字符
暴力法显然过不去，然后再回看这种数量关系，很容易想到前缀和
而且每类字符单独考虑，就用类似 \(sum[N][26]\) 的形式，存储前 \(i\) 个字符中 \(j+'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
标签：枚举
题意
给定两个整数 n 和 x ，要求 \(ab+ac+bc≤n\) 和 \(a+b+c≤x\)
输出满足条件的三元组 \((a,b,c)\) 的组数
思路
本题在经过一系列找规律后，发现根本找不到规律。。。
找不到规律就先开始考虑暴力枚举
本题如果枚举三个数是会超时的，那么看看能不能枚举两个数
本题给的两个限定条件 \(n\) 和 \(x\) ，要理清思路，假如确定了两个值，第三个值是能直接算出来的
如果是确定 \(a、b\) ，那么对于 \(c\) ，首先 \(c \le x-a-b\) ，同时 \(c \le (n-a*b)/(a+b)\)
代码
核心代码
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
标签：字符串、前缀和
题意
给定01串 \(s\)，对与任意的区间\(l\)到\(r\)，在\(l\)到\(r\)中再选取任意\(x<y\)，要求\(s[x...y]\)中的01个数相等
答案对1e9+7取余
思路
- 出现这种数量相等的情况，一般考虑能不能用前缀和处理一下，让01的数量通过加1减1来抵消
如 \(1100111001\)
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，那么就可以在 \(O(1)\) 时间得出l和r的种类，\(l\in[1,x],r\in[y,10]\)
- 那么现在的问题转变成了要怎么找到所有这样的x和y呢？
显然通过sum，对于l到r，\(sum[r]==sum[l-1]\)
所以将sum值相同的下标存储在一起
- 现在的问题又转化为，该怎么快速的将答案求出来呢
在这个例子中，对于\(sum=1\)有以下下标：1 3 5 9
我们先手算一下答案：
\(1*(10-3+1)+1*(10-5+1)+1*(10-9+1)+3*(10-5+1)+3*(10-9+1)+5*(10-9+1)\)
答案不是重点，重点是式子，我们转化成如下式子：
\(1*(10-9+1)+3*(10-9+1)+5*(10-9+1)\)
\(1*(10-5+1)+3*(10-5+1)\)
\(1*(10-3+1)\)
相当于是，用一个变量 \(cur\) 存储需要用到的 \(l\) ，比如对于\(3\)，需要用\(1\)，对于\(5\)，需要用\(1+3\),
流程就是，在处理完小的 \(l\) 和 \(r\) 后，将 \(r\) 存储到 \(cur\) 中，这样 \(cur\) 存的就是\(1+3\)
\(cur\) 与 \(5\) 算完后，再将 \(5\) 存储到 \(cur\) 中，然后是 \(cur\) 和\(9\)
代码
说明，由于我是用数组处理，所以所有负数转变成正数了
可以用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;
}