【CF】509E Pretty Song-白红宇

【CF】509E Pretty Song

阅读量：7221 次

发布时间：2019-06-29

本文共 1548 字，大约阅读时间需要 5 分钟。

数学规律题，很容易计算的。以初始测试数据3为例。

Str Y I S V O W E L

--------------------------

Len 1 2 3 4 | 5 6 7 8

Y + | +

I + + | + +

O + + + + | + + + +

E + | +

首先注意1-4与5-8是对称的（仅长度不同）。长度为2的总数可以在长度为1的总数的基础上累加计算（因为2-len-1的字符若为Vow则各递增1），长度为3的可以在长度为2的基础上累加计算。

故，首先求得cnt[]数组表示从1开始到位置n的Vow字符数目。然后遍历1-len/2的长度，求得结果，若len为奇数，则单独再计算一次(len+1)/2。

其实就是递推规律题目，O(n)时间复杂度。

1 /* 509E */ 2 #include 
     
       3 #include 
      
        4 #include 
        5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            
             10 #include 
             
              11 #include 
              
               12 #include 
               
                13 #include 
                
                 14 #include 
                 
                  15 #include 
                  
                   16 using namespace std;17 18 #define isVow(ch) (ch=='I'||ch=='E'||ch=='A'||ch=='O'||ch=='U'||ch=='Y')19 20 const int maxn = 5e5+5;21 char s[maxn];22 int cnt[maxn];23 24 int main() {25 int i, j, k;26 int len;27 __int64 sum;28 int l, r, tmp;29 double ans;30 31 #ifndef ONLINE_JUDGE32 freopen("data.in", "r", stdin);33 freopen("data.out", "w", stdout);34 #endif35 36 scanf("%s", s+1);37 memset(cnt, 0, sizeof(cnt));38 for (i=1; s[i]; ++i) {39 if (isVow(s[i]))40 cnt[i] = cnt[i-1]+1;41 else42 cnt[i] = cnt[i-1];43 }44 len = i-1;45 ans = 0.;46 sum = 0;47 l = 0;48 r = len;49 for (i=1, j=len; i<=len/2; ++i, --j) {50 sum += cnt[r] - cnt[l];51 ans += 1.0*sum/i + 1.0*sum/j;52 ++l;53 --r;54 }55 if (len & 1) {56 sum += cnt[r] - cnt[l];57 ans += 1.0*sum/i;58 }59 printf("%.7lf\n", ans);60 61 62 #ifndef ONLINE_JUDGE63 printf("%d\n", (int)clock());64 #endif65 66 return 0;67 }

转载于:https://www.cnblogs.com/bombe1013/p/4435878.html

你可能感兴趣的文章