R（双指针）

题目链接

https://ac.nowcoder.com/acm/contest/23479/A

题面

思路

题目中要求解的是子串至少包含k个R字符且不能包含P字符的数量，注意子串和子序列的区别，因为子串不能包含P字符，我们不难想到这个P就相当于把字符串分割成了两部分（因为子串要求连续），对于一个不包含P的字符串我们要求这样的子串数量，很容易联想到双指针，我们会发现当我们第一次匹配成功后，后面所有的情况都满足条件也就是每次匹配成功我们就处理完以当前i开头的所有子串，举个栗子：BBBBR，当我们第一次匹配成功也就是BBB这个时候我们发现后面的BBBB和BBBBR都是满足条件的，因为题目要求的是大于等于k，所以我们一次统计完就好了，复杂度 O ( N ) O(N) O(N)，现在问题就转化为了字符串以P为分界线，分割成不包含P的子串，然后求这些子串的满足条件的子串情况，也就也是做 N / ( c o u t ( P ) ) + 1 N/(cout(P)) + 1 N/(cout(P))+1的双指针处理就好了，详情请看代码

代码

#include
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e5+10;
//----------------自定义部分----------------
ll n,k,m,q,a[N];

ll vis[200];
string S[N];
ll ans = 0;
void slove(string s){
	memset(vis,0,sizeof vis);
	ll len = s.size();
	ll res = 0;
	for(int i = 0,j = 0;i