双 11 又到了, 小 Z 依然只是一只单身狗, 对此他是如此的苦恼又无可奈何.
为了在这一天脱单小 Z 决定向女神表白, 但性格腼腆的小 Z 决定隐晦一点, 截取一段包含'L','O','V','E'的英文.(顺序不限)
小 Z 想起之前小 D 送给他一本英文书, 决定在这里面截取一段话, 小 Z 发现有好多种方案来截取这段话.
你能知道小 Z 能有多少种方案截取这段话么?
为了简化问题, 英文文本讲不会出现空格, 换行, 标点符号及只有大写的情况.
输入描述:
本题有 T 组数据.
对于每组数据只有一行文本.
1T20
1文本长度100000
输出描述:
输出结果, 并换行.
输入:
3ILOVEACMLOVELOVEALBECVOD
输出:
8154
题意: 找出包含 LOVE 的子串数目
题解: 这题可以用尺取法做, 而且答案就是每次的 len-R
代码:
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define MAX 100005
- string s;
- int T;
- ll ans;
- map<char,int>cnt;
- int main()
- {
- //cout<<ok()<<endl;
- cin>>T;
- while(T--)
- {
- s="";
- cnt.clear();
- cin>>s;
- int len=s.size();
- int st=0,ed=0;
- ans=0;
- int num=0;
- while(1)
- {
- while(ed<len&&num<4){
- if(s[ed]=='L'||s[ed]=='E'||s[ed]=='V'||s[ed]=='O') {
- cnt[s[ed]]++;
- if(cnt[s[ed]]==1) num++;
- }
- ed++;
- }
- if(num<4) break;
- //printf("ed %d \n",ed);
- ans+=len-ed+1;
- if(s[st]=='L'||s[st]=='E'||s[st]=='V'||s[st]=='O') {
- cnt[s[st]]--;
- if(cnt[s[st]]==0) num--;
- }
- st++;
- // printf("st %d \n",st);
- }
- cout<<ans<<endl;
- }
- }
来源: http://www.bubuko.com/infodetail-2750307.html