题意可以这样理解, 2k 个选手进行单淘汰比赛,对阵选手可以任意分组,求每个选手的最好和最坏可能名次。其中,每两个选手对阵的胜负是固定的。名次是这样定义的,比如8个人的比赛,第一轮挂的全部都是第5名,因为有4个人进入了下一轮,而没进入下一轮的4个人中又无法分出优劣。也就是说,名次只会出现1、2、3、5、9。
最坏名次是很好求的,如果某个选手能虐所有人,他必然拿到第1名,否则一定存在使他第一轮出局的安排。
最好名次则可以通过dp解决。
dp(i,j)=1
表示选手
i
能在选手集合
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int w[20][20];
bool dp[20][1<<16];
int count_bit(int x){
int res = 0;
while(x){
if(x&1)res++;
x>>=1;
}
return res;
}
int n;
vector<int> masks[20];
void init(){
memset(masks,0,sizeof(masks));
for(int i=1;i<(1<<n);i++){
int cnt = count_bit(i);
masks[cnt].push_back(i);
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
dp[i][1<<(i-1)]=1;
}
}
int get_mask(int x,int m){
int bit=1;
int res=0;
while(x){
if(x&1){
if(m&1){
res|=bit;
}
m>>=1;
}
bit<<=1;
x>>=1;
}
return res;
}
int get_bit(int x,int bit){
int ans=1;
while(x){
if(x&1){
bit--;
if(bit==0){
return ans;
}
}
ans++;
x>>=1;
}
return -1;
}
int main(){
int t;
cin>>t;
int cas = 0;
while(t--){
cas++;
cin>>n;
init();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&w[i][j]);
}
}
//
for(int i=2;i<=n;i*=2){
for(int j=0;j<masks[i].size();j++){
int mask = masks[i][j];
int half = i>>1;
for(int k=0;k<masks[half].size();k++){
if(masks[half][k]>=(1<<i))break;
int m1 = get_mask(mask,masks[i>>1][k]);
int m2 = mask^m1;
for(int ii = 1;ii<=half;ii++){
for(int jj = 1;jj<=half;jj++){
int bit1 = get_bit(m1,ii);
int bit2 = get_bit(m2,jj);
if(dp[bit1][m1] && dp[bit2][m2]){
if(w[bit1][bit2]){
dp[bit1][mask] = 1;
}
if(w[bit2][bit1]){
dp[bit2][mask] = 1;
}
}
}
}
}
}
}
printf("Case #%d: \n",cas);
for(int i=1;i<=n;i++){
int MAX = 0;
for(int j=1;j<(1<<n);j++){
if(dp[i][j]){
MAX = max(MAX,count_bit(j));
}
}
bool flag=1;
for(int j=1;j<=n;j++){
if(i==j)continue;
if(!w[i][j])flag=0;
}
int ans1,ans2;
if(MAX==n){
ans1=1;
}else if(MAX==n/2){
ans1=2;
}else if(MAX==n/4){
ans1=3;
}else if(MAX==n/8){
ans1=5;
}else{
ans1=9;
}
if(flag){
ans2=1;
}else{
ans2=n/2+1;
}
cout<<ans1<<" "<<ans2<<endl;
}
}
return 0;
}