「NOIP模拟赛」欢乐斗牛
题目时限2s，空间128M
「题目背景」
为了更快的获取欢乐豆（因为本蒟蒻斗地主水平太低233），hzwer准备去玩欢乐斗牛，但是由于rp太差，hzwer在一个小时之内输光了20个QQ号的欢乐豆（每天系统会赠送每个号4000欢乐豆）。第二天他准备继续再战欢乐斗牛的抢庄模式，但是由于缺乏思考能力，hzwer需要编写一个程序来决定是否抢庄。
「题目描述」
在玩家决定是否抢庄之前，系统会下发四张牌称为底牌，最后一张牌在决定后发放，每张牌可能为1-10，J，Q，K，hzwer认为最后一张牌为每一种点数的概率是相同的，对于一个由五张牌组成的牌型，分数计算规则如下，请你得出底牌的期望得分。
首先注意：在斗牛中，J，Q，K的点数视为10点，即11，12，13在计算头或点数时均视为10，所有牌无视其花色。
首先考虑特殊牌型
- 四炸——即5张牌中有4张一样的牌(如33334)，分数为40
- 五花牛——五张牌均是J，Q或K（如JQJQK），分数为50
- 五小牛——五张牌点数都小于5且点数和小于或等于10（如11223），分数为60
若有多种特殊牌型，得分取分数最大的特殊牌型（如11112视为五小牛）。
如果没有特殊牌型，首先判断牌型是否有“头”，如果五张牌中任意三张的总和为10的倍数如（1K9）即为有“头”，无“头”的牌型得分为0。
对于有头的牌型得分计算如下：
所有牌的和记为t，如果t%10=0则称为“牛牛”,牛牛得分为30；t%10<7称为“小牛”，得分为t%10，否则得分为（t%10）*2。
「输入格式」
第一行一个整数T，表示T组数据
每组数据占一行，为4个整数（11，12，13分别表示J，Q，K）
「输出格式」
对于输入的n行，输出每4张牌的期望得分（四舍五入）
「样例输入」
2
2 2 2 2
10 4 5 12
「样例输出」
43
9
「样例解释」
对于2 2 2 2，最后一张为1或2时，构成五小牛，否则为炸弹，期望得分(2*60+11*40)/13=43.08
对于10 4 5 12，最后一张为1-13的得分分别是30+0+0+0+4+5+0+0+0+18+18+18+18=111/13=8.54
1为牛牛，5为4点，6为5点，10-13为9点，其余无头
「数据范围」
30%的数据T<=5
70%的数据T<=100000
100%的数据T<=1000000
「蒟蒻感言」
在某次对局中发现期望得分很高，果断抢了庄，但是发现有闲家3个“牛牛”，瞬间消失20W欢乐豆
题解
直接枚举模拟可以得30-70
但是发现一共就13^4种情况那么直接预处理所有情况即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #define inf 0x7fffffff #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int f[14][14][14][14]; int cd[5],v[5],num[15],sum; int tot; bool jud1() { memset(num,0,sizeof(num)); for(int i=0;i<=4;i++) { num[cd[i]]++; if(num[cd[i]]==4)return 1; } return 0; } bool jud2() { for(int i=0;i<=4;i++) if(cd[i]<=10)return 0; return 1; } bool jud3() { if(sum>10)return 0; for(int i=0;i<=4;i++) if(cd[i]>=5)return 0; return 1; } bool judhead() { for(int i=0;i<=4;i++) for(int j=i+1;j<=4;j++) if((sum-v[i]-v[j])%10==0)return 1; return 0; } int getans() { sum=0; for(int i=0;i<=4;i++) sum+=v[i]; if(jud3())return 60; if(jud2())return 50; if(jud1())return 40; if(!judhead())return 0; int t=sum%10; if(t<=6&&t!=0)return t; else if(t!=0)return t*2; else return 30; } int main() { //freopen("niuniu.in","r",stdin); //freopen("niuniu.out","w",stdout); for(int a=1;a<=13;a++) for(int b=1;b<=13;b++) for(int c=1;c<=13;c++) for(int d=1;d<=13;d++) { tot=0; cd[0]=a;cd[1]=b;cd[2]=c;cd[3]=d; for(int i=0;i<4;i++)v[i]=min(cd[i],10); for(int i=1;i<=13;i++) { cd[4]=i;v[4]=min(cd[4],10); int t=getans(); tot+=t; } f[a][b][c][d]=tot; } int T=read(); while(T--) { for(int i=0;i<4;i++)cd[i]=read(); printf("%.0lf\n",(double)f[cd[0]][cd[1]][cd[2]][cd[3]]/13); } return 0; } |
或者可以将已经计算过的存下来
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #define inf 0x7fffffff #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int f[14][14][14][14]; int a[5],v[5],num[15],sum; int tot; bool jud1() { memset(num,0,sizeof(num)); for(int i=0;i<=4;i++) { num[a[i]]++; if(num[a[i]]==4)return 1; } return 0; } bool jud2() { for(int i=0;i<=4;i++) if(a[i]<=10)return 0; return 1; } bool jud3() { if(sum>10)return 0; for(int i=0;i<=4;i++) if(a[i]>=5)return 0; return 1; } bool judhead() { for(int i=0;i<=4;i++) for(int j=i+1;j<=4;j++) if((sum-v[i]-v[j])%10==0)return 1; return 0; } int getans() { sum=0; for(int i=0;i<=4;i++) sum+=v[i]; if(jud3())return 60; if(jud2())return 50; if(jud1())return 40; if(!judhead())return 0; int t=sum%10; if(t<=6&&t!=0)return t; else if(t!=0)return t*2; else return 30; } int main() { //freopen("niuniu.in","r",stdin); //freopen("niuniu.out","w",stdout); memset(f,-1,sizeof(f)); int T=read(); while(T--) { for(int i=0;i<4;i++)a[i]=read(); double t=f[a[0]][a[1]][a[2]][a[3]]; if(t!=-1){printf("%.0lf\n",t/13);continue;} tot=0; for(int i=0;i<4;i++)v[i]=min(a[i],10); for(int i=1;i<=13;i++) { a[4]=i;v[4]=min(a[4],10); int t=getans(); tot+=t; } f[a[0]][a[1]][a[2]][a[3]]=tot; printf("%.0lf\n",(double)tot/13); } return 0; } |
OI 课件=>
