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

· · 题解

更好的阅读体验

思路

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

有人不是种子选手的情况比较简单，因为都是随机抽签，所以最小的相遇的可能性就是 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 记录