P9451 [ZSHOI-R1] 新概念报数 题解

• Description
• Solution
• Code

Description

在此题中，对于一个数 \(x\)，若 \(\texttt{popcount}(x)\geq3\)（即 \(x\) 在二进制下 \(\texttt{1}\) 的个数大于等于三时），那它是非法的，否则其为合法的。

给定 \(T\) 个数，如果当前的数 \(x\) 是非法的，则输出 No,Commander,否则输出第一个大于 \(x\) 的合法的数。

Solution

对于一个数 \(x\)，我们可以快速得出 \(\texttt{popcount}(x)\)，若为非法，直接输出答案，否则还剩三种情况：

1. \(\texttt{popcount}(x)=0\)，说明 \(x=0\)，输出 \(\texttt{1}\) 即可。
2. \(\texttt{popcount}(x)=1\)，输出 \(x+1\) 即可，因为 \(\texttt{popcount}(x+1)=2\)（\(\texttt{popcount}(1+1)=1\) 为特例）
3. \(\texttt{popcount}(x)=2\)，设答案为 \(y\)，若 \(\texttt{popcount}(y)=1\) ，则 \(y=2^{\left\lceil\log_2{x}\right\rceil+1}\)，比如 \(x=\texttt{10100}\) 时 \(y=100000\)，而 \(\texttt{popcount}(y)=2\) 时，则需要找到其从低到高第一个 \(1\) 的位置 \(k\)，\(y=x+2^{k-1}\)，因为在把第 \(k\) 位的 \(\texttt{1}\) 消掉时，能同时加 \(\texttt{1}\) 到 \(k+1\) 位上，如 \(x=10100\) 时 \(y=11000\)，要比第一种更小，综上，输出 \(x+2^{k-1}\) 即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
int check(ll num){  // 得出popcount(x)
	int cnt=0;
	while(num){
		if(num&1){
			cnt++;
		}
		num>>=1;
	}
	return cnt;
}
ll next(ll x){ //记得开 long long
	if(check(x)==1||check(x)==0) return x+1;
	int cnt=0;
	ll y=x;
	while(x){
		if(x&1) break; //找到 k
		x/=2;
		cnt++;
	}
	ll xx=pow(2,cnt); // 加上 2^{k-1}
	return (ll)(y+xx);
}
int main(){
	cin>>t;
	while(t--){
		ll x;
		cin>>x;
		if(check(x)>=3) cout<<"No,Commander"<<endl;
		else cout<<next(x)<<endl;
	}
	return 0;
}