Posted on 2010-03-12 22:23
Uriel 閱讀(312)
評論(0) 編輯 收藏 引用 所屬分類:
POJ 、
模擬
這道題被選作ECUST 2010.03.11 weekly contest 的一題，比賽的時候切了三道之后搞了1h+的這題，想用DFS做但是一直出不了sample，賽后問了ZYY才知道題意都理解錯了。。。今天按照自己理解的ZYY的方法（不知道是不是ZYY原來的方法。。）搞了很久終于切掉了。。
LP大牛和其他人不知道用了什么方法，不過ZYY這個方法很好寫而且0Ms~
分為兩部分求：
首先一點：最后的冠軍最高rank和最低rank都是1
1. 求最高rank，假設win變量存的是最后獲勝者編號，然后輸給win的所有參賽者最高rank為2，然后找輸給rank的參賽者，他們的rank為3，以此類推~
2. 求最低rank，假設參賽者x一共參加了i 場比賽，在第i 場輸了，那么他的最低rank就是(1<<n)-(1<<(n-i))+1；
EOJ上比POJ BT的是結束0之前的那個case最后不用空一行。。這一點沒有ZYY提醒估計我就不是今天PE兩次的問題了。。。
下面是在EOJ上過的代碼，在POJ上的代碼就是改為每個case后都空一行就行了~
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n,k,win;
int adj[500],mark[500],maxx[500],flag[10][500];
int main()
{
int i,j,query;
bool ok=false;
while(scanf("%d",&n))
{
if(!n)break;
else if(ok)printf("\n");
ok=true;
memset(adj,0,sizeof(adj));
memset(maxx,0,sizeof(maxx));
for(i=1;i<=1<<n;i++)
{
flag[0][i]=i;
}
for(i=1;i<=1<<n;i++)maxx[i]=1<<n;
for(i=n-1;i>=0;i--)
{
for(j=1;j<=1<<i;j++)
{
scanf("%d",&flag[n-i][j]);
maxx[flag[n-i][j]]=(1<<n)-(1<<(n-i))+1;
if(flag[n-i][j]==flag[n-i-1][2*j])
{
adj[flag[n-i-1][2*j-1]]=flag[n-i-1][2*j];
}
else
adj[flag[n-i-1][2*j]]=flag[n-i-1][2*j-1];
}
}
win=flag[n][1];
memset(mark,0,sizeof(mark));
mark[win]=1;
int p=1;
for(i=1;;i++)
{
for(j=1;j<=1<<n;j++)
{
if(mark[adj[j]]==i)
{
mark[j]=i+1;
p++;
}
}
if(p==1<<n)break;
}
scanf("%d",&k);
while(k--)
{
scanf("%d",&query);
printf("Player %d can be ranked as high as %d or as low as %d.\n",query,mark[query],maxx[query]);
}
// printf("\n");
}
// system("PAUSE");
return 0;
}