B4210题解

洛谷上本文的链接

思路

本题的情况大致分为两种：

• 有人不是种子选手
• 都是种子选手

有人不是种子选手的情况比较简单，因为都是随机抽签，所以最小的相遇的可能性就是 1。

否则需要计算两人的批次后计算最小相遇轮数。步骤：

1. 确定批次。批次为满足条件 $2^{l-1}<x\le 2^l$ 的最小 $l$。
2. 最小相遇轮数为 $8-\max(a,b)+1$。其中 $a,b$ 为两人的批次。

最后直接输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	int s,t;
	cin>>s>>t;
	if(s>t) swap(s,t);
	
	int a,b;
	a=0;
	while((1<<a)<s) a++;
	a++;
	b=0;
	while((1<<b)<t) b++;
	b++;
	
	if(s<=32&&t<=32){
		cout<<8-max(a,b)+1<<endl;
	} 
	else{
		cout<<1<<endl;
	}
	return 0;
}

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

AC 记录