成都网站建设新网创想,软装设计公司网站,wordpress会被黑吗,酒店网站建设策划书怎么写4960. 子串简写 - AcWing题库
题目描述 题目分析
原本为纯暴力但是发现会超时#xff0c;可以加入前缀和#xff0c;从前往后先记录一下每个位置c1出现的次数
再从前往后扫一遍#xff0c;如果遇到c2就将答案加上此位置前的所有c1的个数#xff08;直接加上此位置的前缀…4960. 子串简写 - AcWing题库
题目描述 题目分析
原本为纯暴力但是发现会超时可以加入前缀和从前往后先记录一下每个位置c1出现的次数
再从前往后扫一遍如果遇到c2就将答案加上此位置前的所有c1的个数直接加上此位置的前缀和
纯暴力
#includebits/stdc.h
using namespace std;
typedef long long ll;
ll ans;
int main()
{ll k;string s;char c1, c2;cin k;cin s;cin c1 c2;ll len s.size();for(ll i 0, j 1; i len - 1; i ){if(s[i] c1){j i 1;while((s[j] ! c2 || j - i 1 k) j len - 1){j ;}if(s[j] c2 j - i 1 k){ans ;while(j len - 1) {j ;if(s[j] c2){ans ;}}}}}cout ans;return 0;
} ac代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 5e5 10;
ll k, ans, s[N];
string c;
char c1, c2;
int main()
{cin k;cin c;cin c1 c2;ll len c.size();for(int i 0; i len; i ){if(c[i] c1){s[i 1] s[i] 1;}else s[i 1] s[i];}for(int i k - 1; i len; i )//注意长度至少为k{ll l i - k 1;if(c[i] c2)ans s[l 1];}cout ans;return 0;
}
