NC53218. 小w的进制转换
描述
小w在将一个10进制数转换为二进制数的时候，不小心将“0”和“1”搞混了，也就是说本来该输出1的时候他输出了0，本来该输出0的时候他又输出了1。而他在输出答案的时候，又将输出的左右顺序搞混了。举个例子：小w将6转换为二进制，本来6的二进制表示为110，但是小w转换成了001，输出时又倒了过来变成100。现在假设评测姬中的评测数据是1,2,3,4,5,6...n也就是从1到n，问小w能AC其中的多少组测试案例？
输入描述
第一行为一个整数T，表示有T组数据
接下来T行，每行一个整数n，表示评测姬中的数据是从1到n
输出描述
对于每个n，输出一行一个整数表示小w能通过的案例组数。
示例1
输入:
3 1 2 10
输出:
0 1 2
说明:
1在二进制下表示为1，而小w转换成了0，WAC++(g++ 7.5.0) 解法, 执行用时: 58ms, 内存消耗: 1360K, 提交时间: 2022-09-22 21:50:28
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t, n;
int check(int len){
int x = 0, ans = (n >> (len >> 1));
x = ans << (len >> 1);
for(int i = 1; i <= (len >> 1); i ++){
if(!((1ll << (i - 1)) & ans)) x |= (1ll << (len / 2 - i));
}
if(x <= n) return ans;
return ans - 1;
}
signed main(){
scanf("%d", &t);
while(t --){
scanf("%lld", &n);
int bit = 0, m = n;
for(; m; m >>= 1) bit ++;
if(bit & 1) printf("%lld\n", (1ll << (bit >> 1)) - 1);
else printf("%lld\n", check(bit));
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 61ms, 内存消耗: 1388K, 提交时间: 2019-09-27 22:15:51
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t,m,i,j,ans,o[65536];
ll n;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
for(m=0;1LL<<m<=n;m++);
ans=0;
for(i=1;i<<1<m;i++)ans+=1<<i-1;
if(!(m&1))
{
m>>=1;
i=n>>m;
ans+=i-(1<<m-1);
for(j=0;i;i>>=1)j=j<<1|(!(i&1));
if(j<=(n&(1<<m)-1))ans++;
}
printf("%d\n",ans);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 66ms, 内存消耗: 1512K, 提交时间: 2019-10-29 20:10:47
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n;
int check(int len)
{
int x=0,ans=(n>>(len>>1));
x=ans<<(len>>1);
for(int i=1;i<= (len >> 1); i ++)if(!((1ll<<(i-1))&ans))x|=(1ll<<(len/2-i));
if(x<=n)return ans;
return ans-1;
}
signed main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
int bit=0,m=n;
for(;m;m>>=1)bit++;
if(bit&1)printf("%lld\n",(1ll<<(bit>>1))-1);
else printf("%lld\n",check(bit));
}
return 0;
}