题解 CF1178B 【WOW Factor】
Uichiha_Itachi
2019-11-10 14:51:15
这个题可以用类似于前缀和的搞法搞(口胡)。
首先,我们可以用一个数组```isv```记录位置i前的‘w’的个数(两个连在一起的‘v’看做一个‘w’)。
然后,我们就可以对每一个‘o’,计算以其为```wow```中间的‘o’时可以构造几个```wow```。
由乘法原理得,此处应有$cnt_{[1,i-1]}cnt_{[i+1,l]}=cnt_{[1,i-1]}(cnt_{[1,l]}-cnt_{[1,i+1]})$个互异解。($cnt_{[i,j]}$即为区间$[i,j]$内w的个数,l为题中所给字符串长度)
然后就有代码了(
code:
```cpp
#include <bits/stdc++.h>
using namespace std;
long long isv[1000001];
int main()
{
string s;
cin >> s;
int l = s.length();
for(int i = 1;i < l;i++)
{
if(s[i] == 'o')
isv[i] = isv[i - 1];
else if(s[i] == 'v' && s[i - 1] == 'v')
isv[i] = isv[i - 1] + 1;
else isv[i] = isv[i - 1];
}
long long sum = 0;
for(int i = 0;i < l;i++)
{
if(s[i] == 'o')
{
if(i != 0 && i != l - 1)
{
sum += isv[i - 1] * (isv[l - 1] - isv[i + 1]);
}
}
}
cout << sum << endl;
}
```