题目链接:https://www.starrycoding.com/problem/166
题目描述
本题与hard版本的唯一区别就是数据范围的不同,保证hard能过的代码ez能过)
我们规定仅当一个正整数 x x x的二进制表示中 1 1 1的个数不超过 2 2 2时,这个数才是合法的
现在给出正整数 x x x,如果这个数合法,你需要找出下一个合法的数字,否则报告这个数字二进制表示中1的个数
输入格式
第一行1个整数 t t t( 1 ≤ t ≤ 1000 1 \leq t \leq 1000 1≤t≤1000),表示有 t t t组样例测试
接下来 t t t 行每行 1 1 1个整数 x x x ( 1 ≤ x ≤ 1000 ) 1 \leq x \leq 1000) 1≤x≤1000)。
输出格式
输出仅一行一个整数,按题目所要求,若合法报告下一个合法的数,否则报告二进制表示中 1 1 1的个数
样例
输入样例#1
3
1
4
6
输出样例#1
2
5
8
输入样例#2
1
7
输出样例#2
3
题解
由于数的范围很小,假如这个数合法,我们直接从此数 + 1 +1 +1开始枚举,直到合法为止
最坏情况下时间复杂度为 O ( T n / 2 ) O(Tn/2) O(Tn/2)
#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
const int N = 2e5 + 10;
const int M = 15;
const int mod = 998244353;
using namespace std;
typedef pair<int, int>p;
typedef long long ll;
int a(int x)
{
int res = 0;
while (x)
{
if (x & 1)res++;
x >>= 1;
}
return res;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--)
{
int n;
cin >> n;
if (a(n)<=2)
{
n++;
while (a(n) >= 3)n++;
cout << n << endl;
}
else
{
cout << a(n) << endl;
}
}
}
欢迎加入免费公益的C++学习、ACM、蓝桥杯、CCF-CSP竞赛等程序设计交流扣扣群,欢迎加群一起玩耍:746470220