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

CS_profys · 2025-12-18 13:46:13 · 题解

1. 题意

可进行若干次操作。每次操作，选择一个非负整数 x 并把 s 的值修改为 x，但有如下要求：

• 必须满足 x<2^n；
• 必须满足 s | x=2^n−1，其中 | 为按位或运算；
• 花费 s \oplus x 的代价，其中 \oplus 为按位异或运算。

需求出令 s=t 所需代价之和的最小值。

2. 思路

a. s \ne t

如果令 s \oplus x 或 x \oplus t 的代价最小，那么 x 在二进制中 1 的个数需要尽量的多，显而易见 x 取 2^n−1。所以可得出代价公式：

• [s \oplus (2^n−1)] + [(2^n−1) \oplus t]

直接运用即可。

b. s = t

不难发现结果为 0。

3. 代码

#include<bits/stdc++.h>
//#pragma GCC optimize("O3","Ofast","inline","unroll-loops")
#define ll long long
using namespace std;
ll T,n,s,t; 
int main()
{
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    cin >> T;
    while(T--)
    {
        cin >> n >> s >> t;
        if(s==t) cout << 0;
        else
        {
            ll x=(1<<n)-1;
            cout << (s^x)+(x^t);
        }
        cout <<"\n";
    }

    return 0;
}