2020 CCPC-Wannafly Winter Camp Day2 A
文章目录 2020 CCPC-Wannafly Winter Camp Day2 A题目思路代码
题目
思路
一开始没什么思路，直到看了题解，有了一点想法，然后自己推了推就推出来了，就觉得当时的自己就是个憨批，下面是我的思路，设sum[i]是字符串1~i中出现的元音字符个数，f[i]是长度为i的子串中出现的元音字符个数，因为我们不能暴力统计每一个子串的元音字母个数（会TLE），想到统计子串【L…R】的元音个数，我们可以使用前缀和，用sum数组记录
然后就可以推出题解的式子了
而且会发现，f数组是对称的，所以
for(i = n/2+1; i <= n; i++) { f[i] = f[n-i+1]; ans += double(f[i]) / double(i); } 代码 #include <iostream>#include <cstdio>#include <set>#include <list>#include <vector>#include <stack>#include <queue>#include <map>#include <string>#include <sstream>#include <algorithm>#include <cstring>#include <cstdlib>#include <cctype>#include <cmath>#include <fstream>#include <iomanip>using namespace std;#define dbg(x) cerr << #x " = " << x <<endl;typedef pair<int, int> P;typedef long long ll;const int MAXN = 1e6+5;ll sum[MAXN];ll f[MAXN];int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); string op; cin >> op; int n = op.size(); for(int i = 0; i < n; i++) { if(op[i] == 'a' || op[i] == 'e' || op[i] == 'i' || op[i] == 'o' || op[i] == 'u' || op[i] == 'y') { sum[i+1] = sum[i] + 1; } else { sum[i+1] = sum[i]; } } double ans = 0; int i; for(i = 1; i <= op.size()/2; i++) { if(i == 1) { f[i] = sum[op.size()]; } else { f[i] = f[i-1] + sum[n-i+1] - sum[i-1]; } ans += double(f[i]) / double(i); } for(; i <= n; i++) { f[i] = f[n-i+1]; ans += double(f[i]) / double(i); } ans /= ((double(n) * (n+1) / 2.0)); cout << fixed << setprecision(8) << ans << endl;}
