【题解】P2727 [USACO3.2] Stringsobits
题目大意
考虑排好序的位二进制数,且包含所有长度为且这个二进制数中的个数小于等于的数。
现在输出满足长度为$N$,且的个数小于等于的第小的那个二进制数。
分析
直接搜索全排列产生会超时。考虑做法。设表示前位中,恰有个的二进制数量。容易得出, 从到。求出在前位中,最多有个的二进制数的数量,即。如果这个数大于$k$,那么答案的第位为。
实现
$(41ms,~688.00kb)$
1 |
|
考虑排好序的位二进制数,且包含所有长度为且这个二进制数中的个数小于等于的数。
现在输出满足长度为$N$,且的个数小于等于的第小的那个二进制数。
直接搜索全排列产生会超时。考虑做法。设表示前位中,恰有个的二进制数量。容易得出, 从到。求出在前位中,最多有个的二进制数的数量,即。如果这个数大于$k$,那么答案的第位为。
$(41ms,~688.00kb)$
1 | #include<bits/stdc++.h> |