题目描述:
输入要求
输出要求
A single line containing the integer that represents the Ith element from the order set, as described.
假如输入
应当输出
翻译一下:
中文意思就是：
给定N,L,I，找出所有长度为N，最多含有L个1，第I大的二进制串（允许类似00000之类的有前导0的串）
样例解读
00000 -> 1
00001 -> 2
00010 -> 3
00011 -> 4
00100 -> 5
00101 -> 6
00110 -> 7
00111 -> 8
01000 -> 9
01001 -> 10
01010 -> 11
01011 -> 12
01100 -> 13
01101 -> 14
01110 -> 15
01111 这是不行的，超出N位了！
10000 -> 16
10001 -> 17
10010 -> 18
10011 -> 19 答案！
i表示字串长度,j表示最多含有的1的个数,dp[i][j]表示所含有的排列总数
初始化 dp[i][0]=1,dp[0][j]=1;
如此理解。 字串添加的要么是0，要么是1.
当添加是0的时候。 为dp[i-1][j]
当添加是1的时候。 为dp[i-1][j-1]
所以dp[i][j] = dp[i-1][j]+dp[i-1][j-1];
输出时即判断需不需要输出1.
if(t > dp[i-1][l]) 输出1； 因为 当t>dp[i-1][j]这种添加0的情况时。你就知道它必定包含部分dp[i-1][j-1]中的数字。但应当知道 t <= dp[i-1][j]+dp[i-1][j-1];
所以此题可解
需要注意的是。。如果输出了1之后。要把l--掉。。我当时没注意，wa这里了。。还有这个最大总数是2^32-1。你需要开long long 或者 unsigned int 或者 unsigned long。不然，会错！
附上我的代码:
- /*
- * @user ipqhjjybj
- * @Time
- * @data 20130629
- */
- #include <cstdio>
- #include <cmath>
- #include <cstdlib>
- #include <ctime>
- #include <iostream>
- #include <cmath>
- #include <algorithm>
- #include <numeric>
- #include <utility>
- #include <cstring>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <map>
- #include <string>
- using namespace std;
- #define inf 0x3f3f3f3f
- #define MAXN 100
- #define MAXX 10010
- #define clr(x,k) memset((x),(k),sizeof(x))
- #define clrn(x,k) memset((x),(k),(n+1)*sizeof(int))
- #define cpy(x,k) memcpy((x),(k),sizeof(x))
- #define Base 10000
- typedef vector<int> vi;
- #define foreach(it,c) for(vi::iterator it = (c).begin();it != (c).end();++it)
- #define max(a,b) ((a)>(b)?(a):(b))
- #define min(a,b) ((a)<(b)?(a):(b))
- long long dp[MAXN][MAXN];
- int main(){
- long long I;
- int n,l,i,j;
- clr(dp,0);
- for(i = 0;i < MAXN;i++) dp[i][0]=dp[0][i]=1;
- for(i = 1;i < MAXN;i++)
- for(j=1;j < MAXN;j++)
- dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
- while(scanf("%d %d %lld",&n,&l,&I)!=EOF){
- while(n--){
- if(I>dp[n][l])
- printf("1"),I-=dp[n][l],l--;
- else printf("0");
- }
- printf("\n");
- }
- return 0;
- }