题解：P11485 「Cfz Round 5」Non-breath Oblige

Faisal · 2025-12-17 13:44:56 · 题解

题目大意

给定 n,s,t（0\le s,t<2^n），每次操作可将 s 改为 x（x<2^n 且 s|x=2^n-1），代价为 s\oplus x。求将 s 变为 t 的最小总代价。

令 f=2^n-1，若 s=t 则代价为 0；若 s|t=f 则代价为 s\oplus t；否则需两次操作，代价为 (s\oplus f)+(f\oplus t)。

证明

s=t

无需任何操作，代价为 0，显然是最小值。

s \lor t = f

此时 t 满足操作的约束条件（s \lor t = f），因此可直接一步将 s 改为 t，代价为 s \oplus t。 由于单次操作的代价是两数差异位的权重和，而多次操作需累加至少两次非零代价（每次操作代价均为非负），因此一步操作的 s \oplus t 是最小值。

s \lor t \neq f

此时 t 不满足操作约束（s \lor t \neq f），无法一步将 s 改为 t，必须通过两步操作完成：

中间值选择依据：f=2^n-1 的二进制全为 1，因此对任意 x 都满足 x \lor f = f，即 f 与任何数进行按位或运算都符合条件。

第一步操作：将 s 改为 f，满足 s \lor f = f，代价为 s \oplus f。

第二步操作：将 f 改为 t，满足 f \lor t = f，代价为 f \oplus t。

总代价为两步之和 (s\oplus f)+(f\oplus t)。显然不存在比两步更少的可行方案。

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

int T;

int main()
{
    cin>>T;
    while(T--)
    {
        long long n,s,t;
        cin>>n>>s>>t;
        if(s==t)
        {
            cout<<0<<endl;
            continue;
        }
        long long f=(1LL<<n)-1;
        if((s|t)==f)
        {
            cout<<(long long)(s^t)<<endl;
        }
        else
        {
            long long c1=s^f,c2=f^t;
            cout<<c1+c2<<endl;
        }
    }
    return 0;
}