题解：B4210 [常州市赛 2022] 最早对决

yd021a · 2025-06-14 20:28:34 · 题解

解题思路

本题关键在于判断两人是否为种子选手：

• 非种子选手情况
  若其中一人或两人都不是种子选手（编号 > 32），则最小相遇轮次为 1（非种子选手随机抽签）。

• 种子选手情况
  若两人都是种子选手（编号 ≤ 32），需计算他们的批次：

  1. 通过位运算确定选手批次：满足 2^{l-1} < x \leq 2^l 的最小 l。
  2. 取两人批次最大值 \max(a,b)。
  3. 相遇轮次公式：8 - \max(a,b) + 1。

     爱门！

     代码实现

#include<bits/stdc++.h>
using namespace std;
int g(int x){
    int l=0;
    while((1<<l)<x) l++;
    return l+1;
}
inline long long int read(){
    long long int w=1,s=0;
    char ch;
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return w*s;
}
int main(){
    int s,t;
    s=read(),t=raed();
    if (s>t) swap(s,t);

    if (s<=32&&t<=32){  // 两人均为种子选手
        int a=g(s);
        int b=g(t);
        int maxx=max(a,b);
        cout<<8-maxx+1<<endl;
    } 
    else{ // 至少一人非种子选手
        cout<<1<<endl;
    }
    return 0;
}

算法解析

1. 批次计算函数 g(x)

• 通过位运算 (1 << l) < x 确定满足条件的最小 l。
• 返回值 l + 1 表示选手所在批次。
• 示例：

2. 相遇轮次计算原理

设批次为 n，根据赛制：

• 第 n 批种子占据 2^{8-n} 个位置。
• 两人相遇轮次公式： \text{相遇轮次} = 8 - \max(a,b) + 1

3. 典型示例

时间复杂度：O(1)

我的题解就到此为止了，看完这篇以后，就是你来写了。（来自 2.2 的剧情感想）