ecnu 개인전 B Black Peter dp
10333 단어 dp
제목 링크
https://codeforces.com/gym/102190
문제풀이의 방향.
dp[i][0]dp[i][0]dp[i][0]를 설정하면 거북이가 맞은편에 있고 양쪽에 각각 한 장의 카드가 있다. ii가 먼저 이길 확률을 dp[i][1]dp[i]로 설정한다. [1]dp[i][1]는 거북이가 자신에게 있고 양쪽에 각각 한 장의 카드가 있어 ii가 먼저 이길 확률을 나타낸다.
거북이 는 맞은편 에서 두 가지 이동 방식 이 있는데, 각각 맞은편 거북이 를 뽑는 것 과 맞은편 의 정상 패 를 뽑는 것 이다
내가 먼저 다음 상태로 이동하면 바로 맞은편에서 먼저 가는 것이다. dp방정식은 내가 이길 확률을 나타내고 다음 상태로 이동하면 상대방이 진다.
전이 방정식은 다음과 같다. dp [i] [0] = i + 1\8727(1: d p [i: 1] [1]] [1]] + 1 i + 1\8727(1: d p [i] [0]]) dp[i]]] =\rac {i} {i+1} * (1-dp[i] [1] [1]]]]) + 1 i + [1] [1]]]) + 1 i + 1 i + 1 i + 1 i + 1 i + 1 [1] * * (1-dp[i] [0] [0] [0] [1] [1] [1] [1] [1] [1] [1] [1 i [1] [1] [1] [1] [1] [ii[1] [1] [1] [1] [1dp[i][0]) dp[i] [1] = 1 - d p [i - 1] [0] dp[i] [1] = 1 - dp[i-1] [0] dp[i] [1] = 1 - dp[i - 1] [0]
또한 dp[i][0]dp[i][0]dp[i][0]와 dp[i][1]dp[i][1]dp[i][1]는 수치상 상관없이 정상적으로 이동하면 된다
#include
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define debug cout<
#define pb push_back
#define endl '
'
const int mod=(int)1e9+7;
const int maxn=(int)1e6+5;
string s1,s2;
int t,n;
//0 ,1
double dp[maxn][2];
void init()
{
dp[0][0]=1.0,dp[0][1]=0.0;
for(int i=1;i<maxn;i++)
{
dp[i][0]=(1+i*(1-dp[i-1][1]))/(i+2);
dp[i][1]=1-dp[i-1][0];
}
}
signed main()
{
init();
//cout<
IOS
cin>>t;
while(t--)
{
cin>>n;
cin>>s1>>s2;
int num=0;
int fl=0;
for(int i=0;i<n;i++)
{
if(s1[i]=='1'&&s2[i]=='1')
{
num++;
}
if(s1[i]=='1'&&s2[i]=='0')
{
fl=1;
}
}
cout<<fixed<<setprecision(10)<<dp[num][fl]<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.