B. WOW Factor: http://codeforces.com/contest/1178/problem/B
题意:
Bob的键盘坏了,只能用vv代表w,只有两个相邻的vv才能表示w。现在有一个字符串,问能否通多删减,但不改变相对顺序来得到vvovv来表示wow,如果可以问有多少个?
分析:
首先通过遍历字符串打表,建立起一个 x1ox2ox3ox4 这样的格式。x1表示在第一个o之前有多少个vv,x2表示在第二个o之前有多少个vv,以此类推。最后计算每一个o对应的左右两边的vv个数, 然后算出在这个o的基础上能有多少个wow。
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6+7;
char s[N];
vector<int> ve;
int main()
{
while(scanf("%s", s) != EOF)
{
ve.clear();
ve.resize(1);
int len = strlen(s);
int ind = 0;
int sum = 0; // vv总数
for(int i=1; i<len; i++) // 遍历字符串,打表计算vv个数
{
if(s[i] == 'v' && s[i-1] == 'v')
{
ve[ind] ++;
sum ++;
}
else if(s[i] == 'o')
{
ve.resize(ind+2+1); // 每遇到一个o都要往后增加两个,一个存o,一个存vv个数
ve[ind+1] = -1; // o标记为-1
ind += 2; // 下标要越过o
}
}
int front = 0; // 当前o之前有多少个vv
LL ans = 0;
int lenv = ve.size();
for(int i=0; i<lenv; i++)
{
if(ve[i] != -1)
{
front += ve[i];
}
else
{
ans += 1LL * front * (sum - front);
}
}
printf("%lld\n", ans);
}
return 0;
}