Posted on 2010-03-12 22:23
Uriel 阅读(297)
评论(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;
}