自动搬运

查看原文

来自洛谷，原作者为

	yd021a "May you, the beauty of this world, always shine."

搬运于2025-08-24 21:17:51，当前版本为作者最后更新于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 表示选手所在批次。
• 示例：
  • $x=1$ → $l=0$ → 批次 $1$。
  • $x=3$ → $l=2$ → 批次 $3$。

2. 相遇轮次计算原理

设批次为 $n$，根据赛制：

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

3. 典型示例

时间复杂度：$O(1)$

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