洛谷P2727 01串 Stringsobits
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个1的方案数，可以知道如果第i位填1，那么大小是f + 1,这个很好证明.f数组该怎么推呢？第i位要么填1，要么填0，f = f + f.f = f = 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 = 1; i <= n; i++)
f = 1;
for (int i = 0; i <= l; i++)
f = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= l; j++)
if (j <= i)
f = f + f;
else
f = f;
for (int i = n; i >= 1; i--)
if (I && f < I)
{
printf("1");
I -= f;
l--;
}
else
printf("0");
//while (1);
return 0;
}
https://blog.51cto.com/u_15470004/4847885
页:
[1]