P3048 [USACO12FEB]牛的IDCow IDs
- 12通过
- 67提交
- 题目提供者lin_toto
- 标签USACO2012
- 难度普及/提高-
- 时空限制1s / 128MB
提交 讨论 题解
最新讨论更多讨论
- 谁能解释一下这个样例啊....
题目描述
Being a secret computer geek, Farmer John labels all of his cows with binary numbers. However, he is a bit superstitious, and only labels cows with binary numbers that have exactly K "1" bits (1 <= K <= 10). The leading bit of each label is always a "1" bit, of course. FJ assigns labels in increasing numeric order, starting from the smallest possible valid label -- a K-bit number consisting of all "1" bits. Unfortunately, he loses track of his labeling and needs your help: please determine the Nth label he should assign (1 <= N <= 10^7).
FJ给他的奶牛用二进制进行编号，每个编号恰好包含K 个"1" (1 <= K <= 10)，且必须是1开头。FJ按升序编号，第一个编号是由K个"1"组成。
请问第N(1 <= N <= 10^7)个编号是什么。
输入输出格式
输入格式：
- Line 1: Two space-separated integers, N and K.
输出格式：
输入输出样例
输入样例#1：
7 3
输出样例#1：
10110
分析：首先有一个很简单的结论：一个只有0和1的数字串，只有1对数字串大小有影响，0没有影响。很简单证明，大小取决于1的位置和数量。
这道题有一个限制：第一位必须是0，那么我们先将这个串用足够大小保存，足够大的话我们可以添加前导0，到最后从第一个非0位输出即可，也就是说我们要找到一个m,使得C(m,k) >= n,这个可以用二分实现，我们先弄一个m位的全是0的串。然后考虑C(i-1,k)的意义，即还剩i-1位可以填k个1的方案数，也就是说我们还有C(i,k)个不同大小的数，如果C(i-1,k) < n,则说明剩下的数还不够n个，我们不能找到第n大的数，于是我们在i位填1，那么这个数就是能够出现的C(i-1,k)个数中最大的，n-=C(i-1,k),k--,如果C(i-1,k) >= n,说明后面还能找到第n大的，我们填0即可，就这样模拟一下就好了。
不过这个组合数会非常大，还会爆long long,需要分类讨论进行二分.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; long long n, k, f[][], m;
long long num[], cnt; long long Combination(long long n, long long m)
{
long long ans = ;
for (long long i = n; i >= (n - m + ); --i)
ans *= i;
while (m)
ans /= m--;
return ans;
} int main()
{
scanf("%lld%lld", &n, &k);
if (k == )
{
for (int i = n; i; i--)
{
if (i == n)
printf("");
else
printf("");
}
return ;
}
else
{
if (k == )
{
long long l = , r = ;
while (l <= r)
{
long long mid = (l + r) >> ;
if (Combination(mid, k) >= n)
{
m = mid;
r = mid - ;
}
else
l = mid + ;
}
}
else
{
if (k >= )
{
long long l = , r = ;
while (l <= r)
{
long long mid = (l + r) >> ;
if (Combination(mid, k) >= n)
{
m = mid;
r = mid - ;
}
else
l = mid + ;
}
}
else
{
long long l = , r = ;
while (l <= r)
{
long long mid = (l + r) >> ;
if (Combination(mid, k) >= n)
{
m = mid;
r = mid - ;
}
else
l = mid + ;
}
}
}
for (long long i = m; i; i--)
{
long long t = Combination(i - , k);
if (t < n)
{
num[i] = ;
n -= t;
k--;
if (!cnt)
cnt = i;
}
if (!k || !n)
break;
}
for (long long i = cnt; i; i--)
printf("%d", num[i]);
} return ;
}