Gym - 101190F Foreign Postcards(확률 dp)

원제:
ACM ICPC 2016–2017, Northeastern European Regional Contest.St. Petersburg – Barnaul – Tbilisi – Almaty, December 4, 2016Problem F. Foreign PostcardsInput file: foreign.inOutput file: foreign.outFedor is an avid traveler. As a result of his hobby, he has gathered a big collection of postcards fromall over the world. Each postcard has a unique picture on the front side and some fields for addressinformation and text on the back side.During one of the parties at Fedor’s house, he decided to show all his of postcards to the guests. Toachieve that, he wants to lay them all out on the table. Initially, all of his postcards are arranged in asingle stack that Fedor is holding in his hands. Unfortunately, some of the postcards in that stack canbe turned incorrectly — upside down. Ideally, Fedor would like all postcards on the table to lie with thepicture on top, but looking at every postcard and turning it over individually can be very time-consuming.Instead, he came up with the following process:1. Let n be the number of postcards remaining in the stack in his hands. Fedor chooses a randomnumber k uniformly between 1 and n and takes top k postcards from the stack.2. He looks at the topmost postcard among these k postcards. If it is oriented in the wrong way, heturns the whole stack of k postcards upside down together.3. He then puts these k postcards on the table without any further rotations.4. If there are still some postcards remaining in the stack in his hands, Fedor goes back to step 1.Of course, after all the postcards are on the table, there might still be some that lie back side up. Whatis the expected number of such postcards?InputThe input consists of a single line of “C” and “W” characters — i-th character corresponds to i-th postcardin the stack, counting from the top of the stack. “C” means that i-th postcard is oriented correctly in theinitial stack, and “W” means that i-th postcard is oriented in the wrong way. The number of charactersis between 1 and 106 inclusive.OutputOutput one real number — the expected number of incorrectly placed postcards on the table. Theabsolute or relative error should not exceed 10−9.Examplesforeign.in foreign.outcWCC 1.0WWCWCCW 2.333333333333Page 8 of 15 제목:
한 세트의 패는 정반대편으로 나뉘어 한데 쌓이고 매번 랜덤으로 패 꼭대기에서 k장을 선택한다. 만약에 첫 번째 패가 반대편이라면 모든 패를 한쪽에 놓고 카드 더미에서 선택한 패가 다 선택될 때까지 반복해서 모든 패 중 반대편의 패의 기대를 구한다.
아이디어:
모든 패의 뒤집는 면의 총계를 구하려면sum[i]는 i~n의 패 중 선택한 뒤집는 패의 총계이고 s[i]==s[i+1]이면 Sum[i]=Sum[i+1], 그렇지 않으면 Sum[i]=(double)(len-i)*(len-1-i)/2.0-sum[i+1];(Sum[i+1]의 패의 정면과
dp[i]=p*Sum[i]+p*Exp,Exp+=dp[i].

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#define pi acos(-1.0)
#define INF 2147483647
using namespace std;
typedef long long ll;
typedef pair  P;
double dp[1000010];
double Sum[1000010];
string s;
int main ()
{
    freopen("foreign.in", "r", stdin);
    freopen("foreign.out", "w", stdout);
    cin>>s;
    memset(dp,0,sizeof(dp));
    memset(Sum,0,sizeof(Sum));
    int len=s.size();
    double p,Exp=0;
    for(int i=len-2; i>=0; i--)
    {
        if(s[i]==s[i+1])
            Sum[i]=Sum[i+1];
        else
            Sum[i]=(double)(len-i)*(len-1-i)/2.0-Sum[i+1];
    }

    for(int i=len-1; i>=0; i--)
    {
        p=1.0/(1.0*(len-i));
        dp[i]=p*Sum[i]+p*Exp;
        Exp+=dp[i];
    }
    printf("%.10lf
",dp[0]);
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

문제 풀이 보고서 의 CodeForces 91B Queue

Otherwise, print the i-th walrus's displeasure: the number of other walruses that stand between him and the furthest fro...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Gym - 101190F Foreign Postcards(확률 dp)

좋은 웹페이지 즐겨찾기