2020 CCPC Wannafly Winter Camp Day 2 Div. 1 & 2 - A 토 미의 문자열 [구조, 수학]

8957 단어 수론구조모방 하 다문자열알고리즘동적 계획
제목 전송 문
제목 설명
토 미 는 문자열 이 하나 있 는데, 그 는 자주 꺼 내 서 논다.이날 영어 시간 에 그 는 모음 자모 a, e, i, o, u {a, e, i, o, u} a, e, i, o, u 와 반모음 y {y} y 를 배 웠 다."이 자모 들 은 매우 중요 합 니 다!" 라 고 토 미 는 이렇게 생각 했다. "그럼 제 가 무 작위 로 키 꼬치 를 뽑 으 면 그 안의 모음 이 기대 보다 얼마나 클 까요?" 그래서 토 미 에 대한 문자열 을 구 해 보 세 요. 무 작위 로 키 꼬치, 모음 (a, e, i, o, u, y) (a, e, i, o, u, y) (a, e, i, o, u, y) (a, o, u, y) 자모 가 하위 꼬치 의 길 이 를 차지 하 는 것 에 대한 기 대 는 얼마 입 니까?
입력 설명:
길이 가 10.610 ^ 6 106 을 넘 지 않 는 소문 자 만 포함 하 는 문자열, 즉 토 미의 문자열 을 읽 습 니 다.
출력 설명:
출력 에 필요 한 기대 치 는 상대 적 (절대) 오차 가 10 - 6 10 ^ {- 6} 10 - 6 을 초과 하지 않도록 요구 합 니 다.
입력
legilimens
출력
0.446746032
제목
  • 모든 하위 문자열 모음 자모 가 차지 하 는 평균 값
    • 을 통계 한다.
    해제
  • 령 sum [   i   ] \ \text{sum}[\ i\ ]  sum[ i ] 전 i i 자모의 모음 자모의 개 수 를 나타 낸다
  • 길이 가 i i 인 하위 문자열 에서 모음 자모 가 나타 나 는 개수 의 합 은 f [  i   ] f[\ i\ ] f[ i ]，
  • f [   1   ] = sum [   n   ] f [   2   ] = f [   1   ] + sum [ n − 1 ] − sum [   1   ] f [   3   ] = f [   2   ] + sum [ n − 2 ] − sum [   2   ] ⋯ ⋯ \begin{aligned} &f[\ 1\ ]=\text{sum}[\ n\ ]\\ &f[\ 2\ ]=f[\ 1\ ]+\text{sum}[n-1]-\text{sum}[\ 1\ ]\\ &f[\ 3\ ]=f[\ 2\ ]+\text{sum}[n-2]-\text{sum}[\ 2\ ]\\ &\cdots\cdots \end{aligned} ​f[ 1 ]=sum[ n ]f[ 2 ]=f[ 1 ]+sum[n−1]−sum[ 1 ]f[ 3 ]=f[ 2 ]+sum[n−2]−sum[ 2 ]⋯⋯​
  • 마지막 답 은 (∑ f [  i   ] ) / i n ( n + 1 ) / 2 \displaystyle\frac{\left(\sum f[\ i\ ]\right)/i}{n(n+1)/2} n(n+1)/2(∑f[ i ])/i​

    • AC-Code 
    #include 
#define ll long long
using namespace std;
const int maxn = 1e6 + 10;

string str;
ll sum[maxn];
ll f[maxn];
int main(){
     
    while(cin >> str){
     
        int n = str.length();
        double ans = 0;
        for(int i = 0; i < n; ++i){
     
            if(str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u' || str[i] == 'y')
                sum[i+1] = sum[i] + 1;
            else
                sum[i+1] = sum[i];
        }
        ans = f[1] = sum[n];
        for(int i = 1; i < n; ++i){
     
            f[i+1] = f[i] + sum[n-i] - sum[i];
            ans += 1.0*f[i+1]/(i+1);
        }
        ans = ans / (n*(n+1LL)/2.0);
        printf("%.9f
    "    , ans);
    }
    return 0;
}
    프로 그래 밍 입문 - 자바 작업
    uva 567 Risk

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage