题解：P12203 [COI 2022] 三元传递 / Mensza（无法评测）

· · 题解

警示后人

目前（2026.1.14）oj.uz上的这题评测器有问题，千万别去那里提交！

思路

发现前两个人选的值是无法被第三个人看见的。唯一有用的信息是前两个人选了同样数字。

因为 \lceil \log_2{5\times 10^5} \rceil = 19 所以我们可以考虑分解成二进制后考虑每一位。而且每一位最多只能写一个数，否则就超 L 了。

做过类似这种比较数字的题，很容易能想到从最高位往低位进行比较。这里我们可以试着往数组里写数字的前缀。

例如 A = 10111, B = 10100，我们从最高位往最低位写前缀：

A_p = \{1,10,101,1011,10111\} B_p = \{1,10,101,1010,10100\}

数组 c 有 k 个 2，则说明两数的前 k 位是相同的，从第 k+1 开始两数不同。

看起来是不错的思路？可是怎么判断具体是谁高谁低呢？

发现第一位不相同的时候，肯定有一位是 0 另外一个是 1。

那么我们假设 B>A，则 A 是 0，B 是 1。

这时，我们可以试着让 A 只在当前位为 0 的时候写。让 B 只在当前位为 1 的时候写。

这样的话在最高的不同位，两个前缀都会写进数组里，且 B 写的数会大 1。所以我们让 B 写的数减一，判断数组里是否有 2 即可，有则输出 B 没则输出 A。因为在这只后前缀肯定不同了，所要有相同的数，只可能在这里有。

代码

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

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int L,q;
    cin>>L>>q;
    while (q--){
        string name;
        cin>>name;
        if (name[0]=='a'||name[0]=='b'){
            int AB,cur=0;
            cin>>AB;
            vector<int> v(20),ans;
            for (int i=19;i>=1;i--){
                v[i]=AB&1;
                AB>>=1;
            }
            v[0]=1;
            for (int i=0;i<20;i++){
                cur<<=1;
                cur+=v[i];
                if (name[0]=='b'&&v[i]) ans.push_back(cur-1);
                if (name[0]=='a'&&!v[i]) ans.push_back(cur);
            }
            cout<<ans.size();
            for (int i:ans) cout<<" "<<i;
        }
        else{
            int n;
            cin>>n;
            bool flag=0;
            while (n--){
                int num;
                cin>>num;
                if (num==2) flag=1;
            }
            if (flag) cout<<"B";
            else cout<<"A";
        }
        cout<<"\n";
    }
    return 0;
}