本文主要是介绍zoj 1153 Tournament Seeding，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
太纠结了这题
题意：
n个人淘汰制比赛，从最厉害到最差水平的人分别编号1~n
定义一场比赛强度为两个比赛者的编号之和，理想强度是尽可能让比赛强度最小，比赛顺序、对手依据此编排。
给出比赛强度m，求m最早可能出现在哪一轮比赛。（最下为第一轮，决赛为上取整logn轮）
方法：
比赛顺序和对手是一定的，按题目要求使比赛强度最小，预处理很重要。
match[i]表示 i 选手初始在第几个位置开始比赛
play[i] 返回来对应自己的编号
剩下的就是模拟所有的比赛强度为m的组合 看他们最早在哪一轮相遇 即所求答案
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;int match[130],play[130],t,n,r,tmp,i,j,cnt,m,x,rou,p1,p2,ans;int main()
{match[0]=1;tmp=64;r=2;for(i=1;i<=7;i++){for(j=0;j<128;j+= 2*tmp){match[j+tmp]=r+1-match[j];}r*=2;tmp/=2;}for(i=0;i<128;i++)play[match[i]]=i;scanf("%d",&t);while(t--){cnt=0;while(scanf("%d%d",&n,&m)&&(n||m)){cnt++;tmp=n-1;r=0;while(tmp>0){tmp/=2;r++;}x=1<<(7-r);ans=inf;// printf("x:%d r:%d\n",x,r);for(i=1;i<=(m-1)/2;i++){if(i<=n&&(m-i)<=n){rou=0;tmp=x*2;p1=play[i];p2=play[m-i];while(p1!=p2){rou++;p1=p1-(p1%tmp);p2=p2-(p2%tmp);tmp*=2;// printf("tmp:%d pip2:%d %d\n",tmp,p1,p2);}if(ans>rou) ans=rou;}}printf("Case %d: Round %d\n",cnt,ans);}if(t) putchar('\n');}return 0;
}
这篇关于zoj 1153 Tournament Seeding的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
