AT_ARC161B 解题报告
题意
给你一个正整数 \(N\),求小于等于 \(N\) 的所有数中最大的一个在二进制下拥有 \(3\) 个 \(1\) 的数。
思路
我们先看无解的情况,因为题目要求必须有 \(3\) 个 \(1\),所以当 \(n \leq 6\) 时,直接输出 \(-1\)。
我们可以考虑使用递归,设 \(f(X)\) 为 \(X\) 在二进制下 \(1\) 的个数,我们可以得到以下几种情况。
-
当 \(f(X) \lt 3\) 时,将 \(X\) 减去 \(1\)(因为在递归过程中,每一步都是将 \(X\) 变得更小,即比 \(X\) 大的数都不满足要求,只能去比 \(X\) 小的数去找可行情况)。
-
当 \(f(X) =3\) 时,\(X\) 即为答案。
-
当 \(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;
}
标签:cnt,return,报告,int,long,ARC161B,二进制,解题
From: https://www.cnblogs.com/ccf-ioi/p/17871576.html