476B - Dreamoon and WiFi

链接:

https://codeforces.com/problemset/problem/476/B

题意:

给一个由 ’ + ’ 和 ’ - ’ 组成的串,为串s,+为向前1,-为向后1

给一个由 ’ + ’ , ’ - ’ 和 ’ ?’ 组成的串,为串t,+为向前1,-为向后1,?为50%+,50%为-

求执行t串后,位置结果和s串相同的概率

解:

dfs一下,暴力一下总数就行

实际代码:

#include<iostream>
#include<cstdio> 
#include<cmath>
#include<algorithm>
#include<cstring>
#define csh(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long int ll;
const int N=1E1+5;
char s[N];//原串 
char t[N];//干扰串 
ll ans=0;//原串目的 
double anssum=0,sum=0;
void dfs(ll mao,ll lg,ll z,ll f)
{
	if(mao>lg)
	{
		if(z-f==ans) anssum++;
		sum++;
	}
	if(t[mao]=='+') dfs(mao+1,lg,z+1,f);
	if(t[mao]=='-') dfs(mao+1,lg,z,f+1);
	if(t[mao]=='?')
	{
		dfs(mao+1,lg,z+1,f);
		dfs(mao+1,lg,z,f+1);
	}
}
int main()
{
	scanf("%s",s+1);
	scanf("%s",t+1);
	ll lgs=strlen(s+1);
	ll lgt=strlen(t+1);
	for(int i=1;i<=lgs;i++)
	{
		if(s[i]=='+') ans++;
		if(s[i]=='-') ans--;
	}
	dfs(1,lgt,0,0);
	//cout<<anssum/sum<<endl;
	double theans=anssum/sum;
	printf("%0.12lf\n",theans);
}

限制:

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

上一篇:《安富莱嵌入式周报》第228期:2021.08.30--2021.09.05


下一篇:【十分钟开发物联网】楼宇访客门禁管理(Wifi版)