862. 二进制数01串
★ 输入文件:kimbits.in
输出文件:kimbits.out
简单对比 时间限制:1 s 内存限制:128 MB
USACO/kimbits(译 by !Starliu )
描述
考虑排好序的N(N<=31)位二进制数。
你会发现,这很有趣。因为他们是排列好的,而且包含所有可能的长度为N且含有1的个数小于等于L(L<=N)的数。
你的任务是输出第I(1<=I<=长度为N的二进制数的个数)大的,长度为N,且含有1的个数小于等于L的那个二进制数。
注意:这里“长度为N”包括长度小于N的数(我们认为高位用0补齐)
共一行,用空格分开的三个整数N,L,I。
共一行,输出满足条件的第I大的二进制数。
题目链接:
分析:这道题很难,构思巧妙,先用dp求出所要求dp[i,j]前i位1的个数不大于j的方案数,然后便是printf了。
先讲一下如何计算dp[i,j]。
dp[i,j]表示前i位,1的个数不大于j的方案数。
显然:dp[i,j]=dp[i-1,j]+dp[i-1,j-1];
dp[i-1,j]表示当前第i位以0开头所得到的方案数,dp[i-1,j-1]表示当前第i位以1开头得到的方案数。
如何根据得到的dp[i,j]来printf呢?如果当前我要确定第i位,那么肯定要看dp[i-1]集合中的值判断,例如我当前确定第5位,前4位不超过3个1的方案数为15,而我现在要求第19位,则第5为1,因为19>15,为什么呢?因为第5位可能为0,1,而为0的占了15个,为1的开头也是占15个,显然19属于为1开头的数,所以输出1,输出1的同时还要更新数据即可。输出0就什么也不用更新。
更新数据是指:当前第19位要减去15,3个1要变为2个1,以更新完的数据去得到第i+1个数才能是正确的。二分对每一位判断当改位是0的时候的有多少个符合条件的数就行了
貌似代码跑的飞起来,COGS上第一道排名NO.1的题,纪念一下!
下面给出AC代码:
1 #include2 using namespace std; 3 const int maxn=32+5; 4 typedef long long ll; 5 ll dp[maxn][maxn],n,o=0; 6 ll C(ll a,ll b) 7 { 8 if(a==0) 9 return 1;10 if(dp[a][b]!=-1)11 return dp[a][b];12 return a==1?b:dp[a][b]=(C(a-1,b)*(b-a+1))/a;13 }14 ll total(ll num,ll len,ll maxo)15 {16 ll cnt=0;17 len=n-len-1;18 for(ll i=0;(i+o)<=maxo;i++)19 {20 cnt+=C(i,len);21 }22 return cnt;23 }24 int main()25 {26 ll l,i,len;27 char ans[maxn];28 memset(dp,-1,sizeof(dp));29 memset(ans,0,sizeof(ans));30 freopen("kimbits.in","r",stdin);31 freopen("kimbits.out","w",stdout);32 cin>>n>>l>>i;33 for(len=0;len =i)37 ans[len]=0+'0';38 else39 {40 ans[len]=1+'0';41 i=i-temp;42 o++;43 }44 }45 cout< <