[微软编程之美挑战赛P2]女神---CLJ神?的代码 - CSDN博客
[微软编程之美挑战赛P2]女神---CLJ神?的代码
Time Limit:20000ms
Case Time Limit:10000ms
Memory Limit:256MB
Description
在 牧场物语 游戏中，如果第一次进入游戏就是春1日，开电视按左键就有和女神猜数字的游戏。
如果第二年春1日要玩猜拳游戏，要第一年冬30日参加过除夕大会。
地点：自家住宅
时间：每年的春之月，一到五日（新年特别节目）
游戏角色：女神
可玩次数：5次
注意手上别拿任何物品，否则无法拿取奖品。
打开电视(4个方向有不同的节目)，这时候会出现由女神主持的猜数字大小节目，只要按左键频道就可换至此节目。
玩法很简单，女神说一个数字，你猜下一个数字比这个数字大还是小，数字为0-9这几个数。如果相同，继续猜，猜中的次数决定你的奖品，奖品答完后奖品直接到手上。
0～1 没东西
2次药草 (各种颜色都有机会得到)
3～9 乔麦粉或年糕 (随机取得)
10～14 轻松茶茶叶
15～19 防晒霜
20～25 润肤霜
26～29 面膜
30～39 香水
40～49 礼物 (保装好的裙子)
50～59 黄金资材 (买价10万G，但不能卖出)
60～69 古代鱼化石 (可卖5000G)
70～79 海盗的宝藏 (可卖10000G)
80～89 料理瓶子 (番茄酱的制作方法)
90～99 料理石板 (考地瓜的制作方法)
100~oo 女神猜拳***
比如说，一开始女神说数字5，你第一次猜&大&，然后女神说数字8，8 & 5, 你说对了一次；
然后，第二次你猜&小&，然后女神说数字4, 4 & 8, 你说对了第二次；
然后，第三次你猜&大&，然后女神说数字4，4 = 4，女神要你重新说;
然后，第四次你猜&大&，然后女神说数字7，7 & 4, 你说对了第三次；
然后，第五次你猜&小&，然后女神说数字9，9 & 7, 你猜错了。
于是你总共说对了3次，获得荞麦粉.
你可以假设，每次出现0-9的概率是相同的，都为10%
由于GG不屑与使用金手指等即时存档工具(但是他会在猜数字开始前，存一个档，如果猜数字游戏的结果不理想，他会执着的反复读档重来)，所以他想知道的是，假设他十分理智，请问他期望猜多少次，才能在一次游戏中，猜对≥ expect次。
这里认为的猜一次，是一次选择大小的过程，也就是说，一局游戏中，会猜很多次。而偏执的GG会反复的玩很多局游戏，直到达到目的。
这里认为，GG的足够理智体现在：
如果在一局游戏中，还没有猜正确够expect次，则他会如果上一个数字 ≥ 5,则猜小；如果上一个数字 ≤ 4,则猜大
如果在一局游戏中，他已经猜正确够expect次，则他会如果上一个数字 ≥ 5,则猜大；如果上一个数字 ≤ 4,则猜小，因为已经达到目的后，他希望这局游戏快点结束。
输入首先是一个整数T ( 1 ≤ T ≤ 100 ), 表示测试数据组数
每组测试数据占一行，为一个整数expect，表示GG要在一局游戏中至少猜对expect次。
如果你的***，和正确***的差的绝对值≤ 1，则被认为是正确的。具体格式详见样例。
大数据：1 ≤ expect ≤ 30
小数据：1 ≤ expect ≤ 100
看起来游戏没有想象得那么困难，要想猜对10次，获得轻松茶茶叶，期望次数不是1024次，而是77.3次。当然您非要拿到***的话，就自求多福了。。。
对于大数据，请务必小心精度问题！
Sample Input
Sample Output
Case 1: 77.422
今天编程之美挑战赛上CLJ完虐PKU的吴铮锴等人，满分100分拿到了80分，最神奇的是他居然在比赛最后9min怒虐第3题，而且还是一遍AC，牛翻了。更有意思的是他在写第二题的时候，在程序最后几行加上了一个笑脸的注释，眼神直飘右边的网友评论栏，真是大神回眸一笑百媚生啊。。。
下面就是CLJ大神牛气哄哄的代码（虽然只过了小数据），抢在他开始虐第3题前一刻copy来的
#include&cstdio&
#include&algorithm&
#include&cstring&
#include&vector&
#include&iostream&
#include&cmath&
#define REP(i,n) for(int i=0;i&n;++i)
const int MAX_N=100+10;
const int MAX_L=1000+10;
int id[MAX_N][10];
long double equ[MAX_L][MAX_L],b[MAX_L];
void gauss(long double ans[],int n){
int at[1001]={};
memset(at,-1,sizeof at);
bool used[1001]={};//for row
REP(iter,n){
int r,who=-1;
REP(rr,n)if(!used[rr])REP(c,n)
if(at[c]==-1 &&
(who==-1||fabs(equ[rr][c])&fabs(equ[r][who])))
r=rr,who=c;
long double by=equ[r][who];
equ[r][c]/= b[r]/=
REP(nr,n) if(r!=nr) {
long double by=equ[nr][who];
REP(c,n) equ[nr][c]-=equ[r][c]*
b[nr] -= b[r]*
at[who]=r;
ans[i]=b[at[i]];
struct Pair{
ld a,b; //a+b*x[rt]
Pair(ld a=0,ld b=0):a(a),b(b){}
Pair operator+(const Pair&o)const{return Pair(a+o.a,b+o.b);}
Pair operator-(const Pair&o)const{return Pair(a-o.a,b-o.b);}
Pair operator*(ld o)const{return Pair(a*o,b*o);}
long double solve(int n){
int nid=0;
memset(equ,0,sizeof equ);
memset(b,0,sizeof b);
long double end[10];
REP(i,10){
equ[i][i]-=1;
REP(j,10) {
if(i&=4&&j&i)
if(i&=5&&j&i)
equ[i][j]+=0.1;
gauss(end,10);
memset(equ,0,sizeof equ);
memset(b,0,sizeof b);
REP(i,n) REP(j,10)
id[i][j]=nid++;
int rt=nid++;
equ[rt][rt]-=1;
REP(j,10){
equ[rt][id[0][j]]+=0.1;
REP(i,n) REP(j,10) {
int me=id[i][j];
equ[me][me]-=1;
REP(k,10){
if(j&=4 &&k&j) ok=
if(j&=5 &&k&j) ok=
equ[me][me]+=0.1;
if(i+1==n){
b[me]-=0.1*end[k];
int nxt=id[i+1][k];
equ[me][nxt]+=0.1;
equ[me][nxt]+=0.1;
long double ans[1001];
gauss(ans,nid);
return ans[rt];
long double solve2(int n){
int nid=0;
memset(equ,0,sizeof equ);
memset(b,0,sizeof b);
long double end[10];
REP(i,10){
equ[i][i]-=1;
REP(j,10) {
if(i&=4&&j&i)
if(i&=5&&j&i)
equ[i][j]+=0.1;
gauss(end,10);
Pair what[MAX_L];
REP(i,n) REP(j,10)
id[i][j]=nid++;
int rt=nid++;
for(int i=n-1;i&=0;--i) REP(j,10) {
int me=id[i][j];
Pair ret(1.0,0.0);
REP(k,10){
if(j&=4 &&k&j) ok=
if(j&=5 &&k&j) ok=
if(i+1==n){
ret.a+=0.1*end[k];
int nxt=id[i+1][k];
ret=ret+what[nxt]*0.1;
ret.b+=0.1;
ret=ret*(1.0/0.9);
what[me] =
at = at + what[id[0][i]]*0.1;
ld ans = at.a/(1-at.b);
//00. : long double
//25. :long long double
int main(){
int T;cin&&T;
REP(i,T) {
printf(&Case %d: %0.20lf\n&,i+1,(double)solve2(n));
本文已收录于以下专栏：
相关文章推荐
时间限制:2000ms
单点时限:1000ms
内存限制:256MB
L国是一个有着优美景色且物产丰富的国家，很多人都喜欢来这里旅游并且喜欢带走一些纪念品，大神同学也...
大神与三位小伙伴
时间限制:2000ms
单点时限:1000ms
内存限制:256MB
L国是一个有着优美景色且物产丰富的国家，很多人都喜欢来这里旅游并且喜欢带走一些纪...
#include//微软编程之美2013全国挑战赛复赛第2题
//由于比赛结束后，提交入口关闭，没来得及提交,但本地数据测试是没错的，不知道能否AC
由于本人能力有限，才编出来资格赛的第一题。不知道算法对不对，欢迎大家批评指导。
时间限制: 1000ms 内存限制: 256MB
Alice和Bob还有其他几位好朋友在...
//source here
int main(){
时间限制: 1000ms 内存限制: 256MB
Alice和Bob还有其他几位好朋友在一起玩传话游戏。这个游戏是这样进行的：首先，所有游戏者按顺序站成一排，Alice站第一...
时间限制:8000ms
单点时限:4000ms
内存限制:256MB
你的硬盘上有一个神秘的文件占用了大量空间，你决定将其压缩以节省空间。不幸的是，你还没有***任何压缩软件，所以你决定自...
总Time Limit: 6000ms Memory Limit: 262144kB
Description
Alice新开了一家公司，它的下面有两个项目，分别需要N1和N2个人来完成。现在有N...
PS:大数据中有趣的应用
节选自: 
大数据时代，什么都跟数据密不可分。觉得追女生是一件不需要科学的东西？那你就错了。微软数据视界近期就通过多...
题目1 : 焦距
时间限制:2000ms
单点时限:1000ms
内存限制:256MB
一般来说，我们采用针孔相机模型，也就是认为它用到的是小孔...
他的最新文章
讲师：何宇健
讲师：董岩
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)