01数字排序 题解

题目描述

现有一个升序排序的N位的二进制数。
这些二进制数包含所有长度为N且这个二进制数中1的位数的个数小于等于L(L<=N)的数。
你需要输出的是第i(输入的i确保1<=i<2的N次幂)小的,长度为N,且1的位数的个数小于等于L的那个二进制数,如果还是看不懂的,可以看样例解释。
(比如:001001这样的数字,N=6,含有位数为1的个数为2)。
N<=31

输入

共一行,用空格分开的三个整数N,L,i。

输出

共一行,输出满足条件的第i小的二进制数。

样例输入

5 3 18

样例输出

10010

提示

样例解释:
1 00000
2 00001
3 00010
4 00011
5 00100
6 00101
7 00110
8 00111
9 01000
10 01001
11 01010
12 01011
13 01100
14 01101
15 01110
15 01111 (有四个1,不符条件,pass掉)
16 10000
17 10001
18 10010
19 10011

题目解析

step1:暴力

枚举答案即可。

step:优化

不难得出,在长度为 \(x\) 出现 \(y\) 个 \(1\) 的总数为

\[f(x,y)=\sum^y_{i=0}C^i_x \]

利用这个公式我们从高到低进行确定这位是取 \(0\) 还是 \(1\) 。(类似于康托展开的感觉)
最后记得计算排列的时候要卡精度。
Tips: \(C^x_y=C^{y-x}_y\)
\(32!>2^{62}-1\)

typedef unsigned long long ull;
ll c(int x,int y){
	if(y>x) return c(x,x);
	ull res=1;
	if(x/2<y) return c(x,x-y);
	int j=1;
	for(int i=x;i>=x-y+1&&j<=n;i--){
		res*=(ull)i;
		while(res%j==0&&j<=y) res/=j++;
	}
	for(;j<=y;j++) res/=(ull)j;
	return res;
}

最后是代码:

#include<cstdio>
using namespace std;
typedef long long ll;
typedef long long Type;
inline Type read(){
	char c=getchar();
	int flag=0;
	Type sum=0;
	while((c<'0'||c>'9')&&c!='-') c=getchar();
	if(c=='-') c=getchar(),flag=1;
	while('0'<=c&&c<='9'){
		sum=(sum<<1)+(sum<<3)+(c^48);
		c=getchar();
	}
	if(flag) return -sum;
	return sum;
}
ll k,n,l;
int check(int x){
	int num=0;
	while(x>0){
		if(x&1) num++;
		x>>=1;
		if(num>l) return 0;
	}
	return 1;
}
typedef unsigned long long ull;
ll c(int x,int y){
	if(y>x) return c(x,x);
	ull res=1;
	if(x/2<y) return c(x,x-y);
	int j=1;
	for(int i=x;i>=x-y+1&&j<=n;i--){
		res*=(ull)i;
		while(res%j==0&&j<=y) res/=j++;
	}
	for(;j<=y;j++) res/=(ull)j;
	return res;
}
ll f(int x,int y){
	if(x<y) return f(x,x);
	ll res=0;
	for(int i=0;i<=y;i++)
	    res+=c(x,i);
	return res;
}
void printx(int x){
	for(int i=n-1;i>=0;i--){
		if(x&(1<<i)) putchar('1');
		else putchar('0');
	}
}
int ans[139],tmp;
int main(){
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	n=read(); l=read(); k=read();
	for(int i=n;i>=1;i--)
	    if(f(i-1,l)>=k){
	    	ans[i]=0;
		}
	    else{
	    	ans[i]=1;
	    	k-=f(i-1,l);
	    	l--;
		}
	for(int i=n;i>=1;i--) printf("%d",ans[i]);
	return 0;
}

上一篇:【真题】CSP-S 2019 Solution


下一篇:中二羊专题:栋栋的入门题(前缀和)