字符串函数 (strfun)

题目描述

两个等长的由大写英文字母构成的字符串a和b，从a中选择连续子串x，从b中选出连续子串y。子串x与子串y的长度相等。

定义函数f(x,y)为满足条件xi=yi(1<=i<=|x|)的i的个数，计算f(x,y)的数学期望。

输入

第一行输入n(1<=n<=2*10^5)，表示a和b的长度

第二行输入字符串a

第三行输入字符串b

输出

输出一个实数表示f(x,y)的期望，答案保留6位小数。

提示

【样例解释】

考虑第一个样例，x,y的选择有5种情况分别是("A","B"),("A","A"),("B","B"),("B","A"),("AB","BA")其中，第2对和第3对所对应的f(x,y)等于1，其他都是0，由于选择每一对的概率都是1/5，所以f(x,y)的期望为1/5*0+1/5*1+1/5*1+1/5*0+1/5*0=2/5=0.4

solution

上面的一个A（位置为i）与下面的一个A（位置为j）

贡献为min（i,j）*min（n-i+1,n-j+1）

例如

xxAxxxx

xxxAxxx

贡献为min(3,4)*min(4,5)=3*4=12

考虑算答案

把对于每一个字符，把A串前缀和起来，同理也做一遍后缀和

扫一遍B串统计即可

比如上面那个例子

A串的前缀0033333

A串的后缀5550000（暂时没有用到）

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

#define maxn 200005

using namespace std;

int n;

double sl[maxn][27],sr[maxn][27],ans;

char a[maxn],b[maxn];

int main()

{

    cin>>n;

    scanf("%s",a+1);scanf("%s",b+1);

    for(int i=1;i<=n;i++){

        int t=a[i]-'A'+1;

        for(int j=1;j<=26;j++)sl[i][j]+=(ll)sl[i-1][j];

        sl[i][t]+=i;

    }

    for(int i=n;i>=1;i--){

        int t=a[i]-'A'+1;

        for(int j=1;j<=26;j++)sr[i][j]+=(ll)sr[i+1][j];

        sr[i][t]+=n-i+1;

    }

    for(int i=1;i<=n;i++){

        int t=b[i]-'A'+1;

        double s1=sl[i][t]*(ll)(n-i+1),s2=sr[i+1][t]*(ll)i;

        ans=ans+s1+s2;

    }

    double aa=((double)ans*6.0)/(double)n/(double)(n+1)/(double)(2*n+1);

    printf("%.6lf\n",aa);

    return 0;

}

巴特西

字符串函数 (strfun)

字符串函数 (strfun)

题目描述

输入

输出

提示

最新文章

热门文章