AcWing 3175. 人物相关性分析
原题链接
简单
作者:
Mr.W
,
2021-01-19 20:36:12
,
所有人可见
,
阅读 718
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;
int K;
vector<int> alice, bob;
int main()
{
cin >> K;
string s;
getchar();
getline(cin, s);
int n = (int)s.size();
int cur = 0;
while(cur < n)
{
int index = s.find("Alice", cur);
if(index == -1) break;
if((index + 5 >= n || !isalpha(s[index + 5])) && (index - 1 < 0 || !isalpha(s[index - 1])))
alice.push_back(index);
cur = index + 5;
}
cur = 0;
while(cur < n)
{
int index = s.find("Bob", cur);
if(index == -1) break;
if((index + 3 >= n || !isalpha(s[index + 3])) && (index - 1 < 0 || !isalpha(s[index - 1])))
bob.push_back(index);
cur = index + 3;
}
long long cnt = 0;
for(int i = 0, j = 0, k = 0; i < (int)alice.size(); i ++ )
{
while(j < (int)bob.size() && bob[j] + 3 + K < alice[i]) j ++ ;
while(k < (int)bob.size() && bob[k] + 3 < alice[i]) k ++ ;
cnt += (k - j);
}
for(int i = 0, j = 0, k = 0; i < (int)bob.size(); i ++ )
{
while(j < (int)alice.size() && alice[j] + 5 + K < bob[i]) j ++ ;
while(k < (int)alice.size() && alice[k] + 5 < bob[i]) k ++ ;
cnt += (k - j);
}
cout << cnt << endl;
return 0;
}