P2727 01串 Stringsobits
- 24通过
- 55提交
- 题目提供者该用户不存在
- 标签USACO
- 难度普及+/提高
提交 讨论 题解
最新讨论
- 这题的思路是啥啊！！！跪求…
题目背景
考虑排好序的N(N<=31)位二进制数。
题目描述
他们是排列好的，而且包含所有长度为N且这个二进制数中1的位数的个数小于等于L(L<=N)的数。
你的任务是输出第i（1<=i<=长度为N的二进制数的个数）小的（注：题目这里表述不清，实际是，从最小的往大的数，数到第i个符合条件的，这个意思），长度为N，且1的位数的个数小于等于L的那个二进制数。
（例：100101中，N=6，含有位数为1的个数为3）。
输入输出格式
输入格式：
共一行，用空格分开的三个整数N，L，i。
输出格式：
共一行，输出满足条件的第i小的二进制数。
输入输出样例
输入样例#1：
5 3 19
输出样例#1：
10011
说明
题目翻译来自NOCOW。
USACO Training Section 3.2
之前写的没保存，被删了......
分析：如果直接枚举，N可能高达32，TLE.换个思路，每位只能填0或1，有点类似动态规划的思想，其实可以这么做.考虑从右往左第i位填的数字，如果填1，那么得到的数必然要比要求的I小，关键是怎么计算这个数是第几大呢？设f[a][b]为填a个数最多只能填b个1的方案数，可以知道如果第i位填1，那么大小是f[i-1][l] + 1,这个很好证明.f数组该怎么推呢？第i位要么填1，要么填0，f[i][j] = f[i-1][j-1] + f[i-1][j].f[i][0] = f[o][i] = 1.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; long long n, l, I, f[][]; int main()
{
scanf("%lld%lld%lld", &n, &l, &I);
for (int i = ; i <= n; i++)
f[i][] = ;
for (int i = ; i <= l; i++)
f[][i] = ;
for (int i = ; i <= n; i++)
for (int j = ; j <= l; j++)
if (j <= i)
f[i][j] = f[i - ][j] + f[i - ][j - ];
else
f[i][j] = f[i][i];
for (int i = n; i >= ; i--)
if (I && f[i - ][l] < I)
{
printf("");
I -= f[i - ][l];
l--;
}
else
printf("");
//while (); return ;
}