链接:
https://codeforces.com/contest/1272/problem/C
题意:
- Recently, Norge found a string s=s1s2...sn consisting of n lowercase Latin letters. As an exercise to improve his typing speed, he decided to type all substrings of the string s. Yes, all n(n+1)2 of them!
- A substring of s is a non-empty string x=s[a...b]=sasa+1...sb (1≤a≤b≤n). For example, "auto" and "ton" are substrings of "automaton".
Shortly after the start of the exercise, Norge realized that his keyboard was broken, namely, he could use only k Latin letters c1,c2,...,ck out of 26.
After that, Norge became interested in how many substrings of the string s he could still type using his broken keyboard. Help him to find this number.
思路:
遍历一边计数, 一个长为 n 的串的所有子串是 1+2++n.
代码:
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- const int MAXN = 2e5;
- char s[MAXN];
- int main()
- {
- int n, k;
- cin>> n>> k;
- cin>> s;
- map<char, bool> Mp;
- char c;
- for (int i = 1;i <= k;i++)
- {
- cin>> c;
- Mp[c] = true;
- }
- int len = strlen(s);
- LL ans = 0, tmp = 0;
- for (int i = 0;i <len;i++)
- {
- if (!Mp[s[i]])
- {
- ans += (1+tmp)*tmp/2;
- tmp = 0;
- continue;
- }
- tmp++;
- }
- if (tmp> 0)
- ans += (1+tmp)*tmp/2;
- cout << ans << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3333600.html