JZTXT

AT_ARC161B解题报告

发布时间 2023-12-02 14:36:44作者: CCF_IOI

AT_ARC161B 解题报告

题意

题目传送门

给你一个正整数 \(N\)，求小于等于 \(N\) 的所有数中最大的一个在二进制下拥有 \(3\) 个 \(1\) 的数。

思路

我们先看无解的情况，因为题目要求必须有 \(3\) 个 \(1\)，所以当 \(n \leq 6\) 时，直接输出 \(-1\)。

我们可以考虑使用递归，设 \(f(X)\) 为 \(X\) 在二进制下 \(1\) 的个数，我们可以得到以下几种情况。

  1. 当 \(f(X) \lt 3\) 时，将 \(X\) 减去 \(1\)（因为在递归过程中，每一步都是将 \(X\) 变得更小，即比 \(X\) 大的数都不满足要求，只能去比 \(X\) 小的数去找可行情况）。

  2. 当 \(f(X) =3\) 时，\(X\) 即为答案。

  3. 当 \(f(X) \gt 3\) 时，将 \(X\) 在二进制下最右边的 \(1\) 变为 \(0\)（满足贪心，减去一个最小的数，使答案最大化）。

不开 long long 见祖宗。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t, n;

int f(int x){
    int cnt = 0;
    while (x){
        cnt++;
        x ^= (x & -x);
        /*
         N & -N 用于获取 N 的最低位的 1。
         这是通过将 N 的二进制表示与其负值（按位取反再加 1）进行按位与操作得到的。
         N ^ (N & -N) 则是将 N 的最低位的 1 置为 0，其它位保持不变。
        */
    }
    return cnt;
}

int solve(int x, int k){//x 表示当前数值，k 表示 x 在二进制数下有多少个 1。
    if (k < 3) return solve(x - 1, f(x - 1));
    if (k == 3) return x;
    if (k > 3) return solve(x ^ (x & -x), k - 1);
}

signed main(){
    cin >> t;
    while (t--){
        cin >> n;
        if (n <= 6) cout << -1 << endl;
        else cout << solve(n, f(n)) << endl;
    }
    return 0;
}