CF2057C Trip to the Olympiad 题解

Helenty · 2025-02-02 15:08:42 · 题解

解题思路

考虑将 l 和 r 转为二进制，一定形如 \texttt{xxxx0****} 和 \texttt{xxxx1****}。即以第一个不同的位分隔。显然可以构造 a = \texttt{xxxx10000}，b = \texttt{xxxx01111}，c 任意取即可。显然这种方案可以使 l 和 r 第一个不同位及其之后的每一位都为 \texttt{1}，因此最优。

完整代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int l, r, T = 1, x = 1;
void work()
{
    cin >> l >> r;
    int op;
    for (int k = 32; k >= 0; k--)
    {
        if ((l & (1 << k)) != (r & (1 << k)))
        {
            op = k;
            break;
        }
    }
    int p = (l >> op) << op;
    int a = p + (1 << op), b = p + (1 << op) - 1;
    if (b == l) cout << a << " " << b << " " << r << "\n";
    else cout << l << " " << a << " " << b << "\n";
}

signed main()
{
    if (x) cin >> T;
    while (T--) work();
    return 0;
}