18361 数绵羊

科技前沿 • 2025-03-12 14:53 • 阅读 47

大家好，我是讯享网，很高兴认识大家。

18361 数绵羊

时间限制:1000MS 代码长度限制:10KB
提交次数:7 通过次数:4

题型: 编程题语言: 不限定
Description
小粥今晚依然因相思而失眠，所以开始数绵羊：
一只绵羊，两只绵羊，三只绵羊，四只绵羊，五只绵羊，六只绵羊，七只绵羊，
八只绵羊，九只绵羊，十只绵羊，十二只绵羊，十一只绵羊，十三只绵羊，十四只绵羊，十五只绵羊。。。

什么，你说他数错了？绝对是因为你不够聪明所以看不出来他在数什么。

他数绵羊的顺序满足以下条件：

(1). 所数的数字为正数整；

(2). 在满足(1)的前提下，二进制表示中最高位1越小的越早被数到；

(3). 在满足(1),(2)的前提下，二进制表示中1的个数越少的越早被数到；

(4). 在满足(1),(2),(3)的前提下，二进制表示中字典序越小的越早被数到；

现在小粥想有一些问题，他想知道他自己数的第n个数是多少，或者是某个数字x是第几个被数到的数字。

讯享网

如果不解决这些问题的话小粥就要数绵羊数到天亮了，所以希望你们帮帮失眠的小粥解决这个问题，好让小粥安心睡觉吧。（说好的相思呢？

输入格式
第一行包含一个数字T(0 <= T <= )，表示下面总共有T个问题。

接下来T行每行包含一个字符（N或X）和一个数字a，以空格分隔。

如果行首是N，则表示这个问题是问第a个数是多少；

如果行首是X，则表示这个问题是问a是第几个被数到的数。(0 < a <= )

输出格式
输出T行，每行包含对应问题的结果。

输入样例
13
N 1
N 2
N 3
N 4
N 5
N 6
N 7
N 8
N 9
N 10
N 11
N
X

输出样例
1
2
3
4
5
6
7
8
9
10
12

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int N=2e5+10; typedef long long ll; int cnt[33][33];//排列组合 string str; int n; void init() { 
    for(int i=0;i<=32;i++) { 
    for(int j=0;j<=i;j++) { 
    if(j==0||j==i) { 
    cnt[i][j]=1; } else cnt[i][j]=cnt[i-1][j]+cnt[i-1][j-1]; } } } int gethighbit()//获取最高位 { 
    int mmax=0; for(int i=0;i<=31;i++) { 
    if((n>>i)&1) { 
    mmax=i; } } return mmax; } int getone()//除了最高位有几个1 { 
    int x=0; for(int i=0;i<gethighbit();i++) { 
    if((n>>i)&1) { 
    x++; } } return x; } void solve2() { 
    int mmax=gethighbit();//他的原数的位数 int ans=(1<<mmax)-1; int tp=0;//这个数有多少个1 while(ans+cnt[mmax][tp]<n) { 
    ans+=cnt[mmax][tp]; tp++; } int pos=n-ans;//tp个1的第pos个排列 ans=(1<<mmax); for(int i=mmax-1;i>=0;i--) { 
    //cout<<pos<<' '<<i<<' '<<tp<<' '<<cnt[i][tp]<<' '<<ans<<endl; if(tp==0) { 
    break; } else if(i+1==tp) { 
    for(int j=0;j<=i;j++) { 
    ans+=(1<<j); } break; } else if(pos>cnt[i][tp]) { 
    ans+=(1<<i); pos-=cnt[i][tp]; tp--; } } cout<<ans<<endl; } void solve1() { 
    int mmax=gethighbit();//最高位1 int ans=(1<<mmax)-1; int x=getone();//除了最高位有几个1 for(int i=0;i<x;i++)//加上小于他的1的个数的个数 { 
    ans+=cnt[mmax][i]; } for(int i=mmax-1;i>=1;i--) { 
    if((n>>i)&1) { 
    ans+=cnt[i][x]; x--; } } ans++; cout<<ans<<endl; } int main () { 
    ios::sync_with_stdio(0); cin.tie(0); init(); int T; cin>>T; while(T--) { 
    cin>>str>>n; if(str[0]=='X') { 
    solve1(); } else solve2(); } return 0; }

讯享网

18361 数绵羊

相关推荐