首页 > 代码库 > TopCoder-SRM637-DIV1-250pt-GreaterGame-集合+概率
TopCoder-SRM637-DIV1-250pt-GreaterGame-集合+概率
首先容易想到的是把那些已知的轮次尽可能的赢下来。对于已知但赢不下来的，可以放上当前最小的牌，这样能使期望最大。
然后就得到了我们当前的一手牌，和他们当前的一手牌。在已知牌的数字，但是不知牌的顺序的情况下，求得分的期望。
一开始试图用递归的方法去做，发现没办法很好的归纳出已经用了那些牌还剩那些牌。
最后猜测了一种方案，竟然有效：
枚举所有我们的牌和他们的牌，两个一组比较大小。最后用我们大于他们的个数除以总的比较次数，这样得到的结果作为概率，乘上这些剩下的牌数作为期望。再加上必胜的那些牌，就得到了正确答案。
我也不知这个如何证明，且等答案吧。
int n,m;class GreaterGame{ public: vector<int> h; vector<int> so; vector<bool> som; vector<bool> sum; double calc(vector <int> hand, vector <int> sothe) { h=hand;so=sothe; n=h.size(); som.resize(MAX_N*2+1,0); sum.resize(MAX_N*2+1,0); for(int i=0;i<n;i++){ sum[h[i]-1]=1; } for(int i=0;i<2*n;i++){ if(!sum[i]) som[i]=1; } int mustWin=0; int known=0; for(int i=0;i<n;i++){ if(so[i]!=-1){ known++; int sun=so[i]-1; bool found=false; som[sun]=false; for(int j=sun+1;j<2*n;j++){ if (sum[j]) { sum[j]=false; mustWin++; found=true; break; } } if (!found){ for(int j=0;j<2*n;j++){ if (sum[j]) { sum[j]=false; break; } } } } } int x=0,y=0; for(int i=0;i<2*n;i++) for(int j=0;j<2*n;j++){ if (sum[i] &&som[j]){ if (i>j) x++; y++; } } if ((n-known)==0) return mustWin; return (double(x)/double(y))*(n-known)+mustWin; }};
TopCoder-SRM637-DIV1-250pt-GreaterGame-集合+概率
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。