《P2111 考场奇遇》

题目背景

本市的某神校里有一个学霸，他的名字叫小明（为了保护主人公的隐私，他的名字都用“小明”代替）。在这次的期中考试中，小明同学走桃花运，在考场上认识了一位女生，她的名字叫小红（同样是为了保护隐私）。

题目描述

英语考试结束了，打完铃，她就主动来找小明说话，一来就要借英语卷子对答案。小明是公认的英语大神，二话不说就把卷子借给了她。小红对了一遍答案，简直是千差万别，她不禁冒出了冷汗。这时，小明走过来，安慰她：“没事，我又不是标准答案，不一定全对。”

已知小明答案的准确率是 A%，一共有 N 道题，给出小红对答案的结果 S（一个长为 N 的 01 串，其中1表示两人答案一样，0表示不一样）。为了简化问题，所有题目都是判断题。

请你帮小红写一个程序，计算出她对 Q 题及以上的概率。

（P.S. 小明后来把那张卷子送给了小红，别想多了，不是定情信物）

输入格式

第 1 行，三个正整数 N,A,Q。

第 2 行，一个 01 字符串 S。

输出格式

一行，一个实数，表示她对 Q 题及以上的概率。（保留 3 位小数）

输入输出样例

输入 #1复制

3 90 2 100

输出 #1复制

0.172

说明/提示

对于 90% 数据，N≤50,N−5≤Q≤N。

对于剩下的 10% 数据，N≤10000,Q=0。

代码实现：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; char c; int n,m,cnt0,cnt1,f[6],g[6]; double p,res=0; double qpow(double a, int b) { double ans=1; for (;b;a=a*a,b>>=1) if (b&1) ans=ans*a; return ans; } int main() { scanf("%d %lf %d\n",&n,&p,&m); if (n<=50) { m=n-m; while ((c=getchar())!='0'&&c!='1') c=getchar(); while (c=='0'||c=='1') { if (c=='1') cnt1++; if (c=='0') cnt0++; c=getchar(); } f[0]=1, f[1]=cnt1, f[2]=f[1]*(cnt1-1)/2, f[3]=f[2]*(cnt1-2)/3, f[4]=f[3]*(cnt1-3)/4,f[5]=f[4]*(cnt1-4)/5; g[0]=1, g[1]=cnt0, g[2]=g[1]*(cnt0-1)/2, g[3]=g[2]*(cnt0-2)/3, g[4]=g[3]*(cnt0-3)/4,g[5]=g[4]*(cnt0-4)/5; for (int i=0;i<=m;i++) { for (int j=0;j<=min(i,cnt0);j++) { if (i-j>cnt1) continue; res+=g[j]*qpow(p*0.01,j)*f[i-j]*qpow((1-p*0.01),i-j)*qpow(1-p*0.01,cnt0-j)*qpow(p*0.01,cnt1-i+j); } } printf("%.3lf",res); } else { printf("1.000"); return 0; } return 0; }