题解 CF1178B 【WOW Factor】

Uichiha_Itachi

2019-11-10 14:51:15

Solution

这个题可以用类似于前缀和的搞法搞(口胡)。 首先,我们可以用一个数组```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; } ```