spoj1182 Sorted bit squence/[USACO2003 Dec]Cow Queueing

本文主要是介绍spoj1182 Sorted bit squence/[USACO2003 Dec]Cow Queueing，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：SPOJ的->http://www.spoj.com/problems/SORTBIT/

题目大意：

约翰给每头奶牛用一个数字编号，这些奶牛在集合时，会将自己编号转换成二进制表示，并按照以下规则排队：
• 首先，编号的二进制中1 出现次数较少的排在队伍的前面；
• 其次，如果1 的数量一样多，那么编号较小的排在前面；
举个例子，从4 到15，有12 个数字，顺序应该是
100; 1000; 101; 110; 1001; 1010; 1100; 111; 1011; 1101; 1110; 1111
假设编号在A到B之间的所有奶牛都在排队，那么这个队伍中排在第K 位的奶牛编号应该是多少呢？

注意：USACO的保证都是非负数0 ≤A≤B<10^9；而spoj上可能有负数但A，B同正同负 -2^31 ≤ A ≤ B ≤ 2^31-1，而且若为负数，则其二进制与其相反数的二进制的和为2^32。

题解：

组合+二分+数位DP

下面的都是最低位为第0位(还是1..???忘了..自己看)。

设f[i][j][k]表示在0~i中，做到了第j位(二进制)，要放k个1有多少种方案(即有多少个这样的数)。

首先，如果i在这位上有1，那么我在这一位取0的话就不在上限边缘，就可以在j-1个位置上随便摆k个1，有C(j-1,k)种方案；而我若取了1，那就为f[i][j-1][k-1]。

而如果i在这位上是0的话，那我也只能取0了啊，所以为f[i][j-1][k]。

这个有什么用呢？

我们先找到排第K位的奶牛有几个1。知道↑之后不用说怎么做吧。

然后在范围[A,B]中二分，使排位不断接近K。因为是用左端点不断靠近答案，所以最后输出l。

USACO的输入输出都是二进制，而spoj的输入输出都是十进制(而且负数要搞回负数..（提醒了我负数这一回事

如果都是负数的话，因为其二进制与其相反数的二进制的和为2^32，那么我们把这个数+2^32，最后再减回来是一样的。

为什么呢？假设这个数为x，相反数为-x，相反数为正数所以是正常的...意思就是(-x)10=(-x)2诶就是说-x的二进制表示的大小和原数相同。

那么 有 -x +（x)2 = 2^32 --> (x)2=x+2^32。

就得到了它的二进制了。其他的照做就好了。 

p.s.下面的代码是spoj的。如果要交USACO的话就把多组数据删了，注释的弄回来，“=====”之间的注释掉。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;LL bit[40],C[40][40];
char s[40];
const LL MX=1LL<<32;
void redc()//预处理组合C(i,j)
{C[0][0]=1;for (int i=1;i<=32;i++){C[i][0]=1;for (int j=1;j<=i;j++)C[i][j]=C[i-1][j]+C[i-1][j-1];}
}
void dels(LL &x)//这是处理二进制输入的
{int len=strlen(s);x=0;for (int i=len-1,k=0;i>=0;i--,k++)x+=bit[k]*(s[i]-'0');
}
LL dfs(LL x,int w,int k)//就是上面说的f[x][w][k]。不过没有存下来而已。意义一样
{if (w==0 && k==0) return 1;if (x<0 || w==0 || k<0) return 0;LL p=1LL<<(w-1);if (x&p) return C[w-1][k]+dfs(x,w-1,k-1);return dfs(x,w-1,k);
}
int main()
{//freopen("cowq.in","r",stdin);//freopen("cowq.out","w",stdout);int i,T;LL l,r,now,sum,K;LL A,B,mid,jl,ind;bit[0]=1;for (i=1;i<=32;i++) bit[i]=bit[i-1]*2;redc();scanf("%d",&T);while (T--){// scanf("%s\n",s);dels(A);// scanf("%s",s);dels(B);//-----------------------scanf("%lld%lld",&A,&B);scanf("%lld",&K);bool pd=0;if (A<0 || B<0) A+=MX,B+=MX,pd=1;if (A>B) {LL t=A;A=B;B=t;}//------------------------sum=now=0;for (i=0;i<=31;i++){now=dfs(B,32,i)-dfs(A-1,32,i);if (sum+now<K) {sum+=now;ind=i;}else {K=K-sum;break;}}ind++;//找排第K的有ind个1l=A;r=B;jl=dfs(A-1,32,ind);while (l<r)//二分{mid=(l+r)>>1;now=dfs(mid,32,ind)-jl;if (now<K) l=mid+1;else r=mid;}//-----------------------if (pd) l=l-MX;printf("%lld",l);//-----------------------// bool pd=0;// for (i=32;i>=0;i--)// if (l&bit[i])// {// printf("1");// pd=1;// }else if (pd) printf("0");printf("\n");}return 0;
}

这篇关于spoj1182 Sorted bit squence/[USACO2003 Dec]Cow Queueing的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---