程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj3191【JLOI2013】卡牌游戲

bzoj3191【JLOI2013】卡牌游戲

編輯:關於C++

3191: [JLOI2013]卡牌游戲

Time Limit:10 SecMemory Limit:128 MB
Submit:410Solved:275
[Submit][Status][Discuss]

Description

  N個人坐成一圈玩游戲。一開始我們把所有玩家按順時針從1到N編號。首先第一回合是玩家1作為莊家。每個回合莊家都會隨機(即按相等的概率)從卡牌堆裡選擇一張卡片,假設卡片上的數字為X,則莊家首先把卡片上的數字向所有玩家展示,然後按順時針從莊家位置數第X個人將被處決即退出游戲。然後卡片將會被放回卡牌堆裡並重新洗牌。被處決的人按順時針的下一個人將會作為下一輪的莊家。那麼經過N-1輪後最後只會剩下一個人,即為本次游戲的勝者。現在你預先知道了總共有M張卡片,也知道每張卡片上的數字。現在你需要確定每個玩家勝出的概率。 這裡有一個簡單的例子: 例如一共有4個玩家,有四張卡片分別寫著3,4,5,6. 第一回合,莊家是玩家1,假設他選擇了一張寫著數字5的卡片。那麼按順時針數1,2,3,4,1,最後玩家1被踢出游戲。 第二回合,莊家就是玩家1的下一個人,即玩家2.假設玩家2這次選擇了一張數字6,那麼2,3,4,2,3,4,玩家4被踢出游戲。 第三回合,玩家2再一次成為莊家。如果這一次玩家2再次選了6,則玩家3被踢出游戲,最後的勝者就是玩家2.  

Input

第一行包括兩個整數N,M分別表示玩家個數和卡牌總數。 接下來一行是包含M個整數,分別給出每張卡片上寫的數字。  

Output

輸出一行包含N個百分比形式給出的實數,四捨五入到兩位小數。分別給出從玩家1到玩家N的勝出概率,每個概率之間用空格隔開,最後不要有空格。  

Sample Input

5 5
2 3 5 7 11

Sample Output

22.72% 17.12% 15.36% 25.44% 19.36%

輸入樣例2:
4 4
3 4 5 6

HINT

 

對於100%的數據,有1<=N<=50 1<=M<=50 1<=每張卡片上的數字<=50

概率DP。f[i][j]表示i個人,從莊家開始順時針第j個人留到最後的概率,然後枚舉一下轉移。
#include

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
using namespace std;
int n,m,a[55];
double f[55][55];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	n=read();m=read();
	F(i,1,m) a[i]=read();
	f[1][1]=1.0;
	F(i,2,n) F(j,1,i) F(k,1,m)
	{
		int pos=(a[k]-1)%i+1;
		if (pos==j) continue;
		if (pos  
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved