今日学习记录
1. Problem-2145C-cf
关键词： 问题分析： 给定一个只含有’a’和’b’的字符串,然后要求删除最小的连续的字符能使 a 和 b 的数量相等,求最短删除多少
核心思路:
一开始想着记录 a 和 b 的数量,思维还是不行,太笨了
如果记录 a 和 b 的数量,我们似乎需要两个状态量(a 的数量,b 的数量),我们可以把 a,b 抽象成 1 和-1,要 a 和 b 数量相同不就是计算为 0 吗,我们可以想到先计算 a 和 b 差多少,再看之前的数组中如果删除某个字符就会对差值 s 产生影响,那么就是要找到某段子数组总和等于 s,将问题转变为求和为 s 的连续最短子数组.
毕竟 cf 是思维题,把问题分析之后才能变成我们所熟知的解决方法(枚举右,维护左)
哈希表
枚举右端点,同时记录左端点,找到pre[r] - sum = pre[l]
**最终代码：
#include <bits/stdc++.h>
using namespace std;
#define ve vector
using ll = long long;
using ull = unsigned long long;
using sr = string;
using db = double;
int T,n;
sr str;
//我们要找到变化的状态,将问题转变为找到长度最短和为s的连续子数组
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>T;
while(T--){
cin>>n>>str;
ve<int> arr(n+1,0);
for(int i = 0;i<n;i++)
if(str[i]=='a') arr[i+1] = arr[i] - 1;
else arr[i+1] = arr[i] + 1;
int ans = INT_MAX;
int sum = arr[n];
//pre[r] - sum = pre[l]
unordered_map<int,int> mp;
mp[0] = 0;
for(int i = 0;i<=n;i++){
if(mp.count(arr[i]-sum)) ans = min(ans,i-mp[arr[i]-sum]);
mp[arr[i]] = i;
}
if(ans==INT_MAX||ans==n) cout<<-1;
else cout<<ans;
cout<<endl;
}
return 0;
}学到的点：
- 枚举