[spoj1182][Sorted Bit Sequence] (数位dp)
Description
Let's consider the 32 bit representation of all integers i from m up to n inclusive (m ≤ i ≤ n; m × n ≥ 0, -2^31 ≤ m ≤ n ≤ 2^31-1). Note that a negative number is represented in 32 bit Additional Code. That is the 32 bit sequence, the binary sum of which and the 32 bit representation of the corresponding positive number is 2^32 (1 0000 0000 0000 0000 0000 0000 0000 0000 in binary).
For example, the 32 bit representation of 6 is 0000 0000 0000 0000 0000 0000 0000 0110
and the 32 bit representation of -6 is 1111 1111 1111 1111 1111 1111 1111 1010
because
0000 0000 0000 0000 0000 0000 0000 0110 (6)
+
1111 1111 1111 1111 1111 1111 1111 1010 (-6)
-------------------------------------------------
= 1 0000 0000 0000 0000 0000 0000 0000 0000 (2^32)
Let's sort the 32 bit representations of these numbers in increasing order of the number of bit 1. If two 32 bit representations that have the same number of bit 1, they are sorted in lexicographical order.
For example, with m = 0 and n = 5, the result of the sorting will be
No. |
Decimal number |
Binary 32 bit representation |
1 |
0 |
0000 0000 0000 0000 0000 0000 0000 0000 |
2 |
1 |
0000 0000 0000 0000 0000 0000 0000 0001 |
3 |
2 |
0000 0000 0000 0000 0000 0000 0000 0010 |
4 |
4 |
0000 0000 0000 0000 0000 0000 0000 0100 |
5 |
3 |
0000 0000 0000 0000 0000 0000 0000 0011 |
6 |
5 |
0000 0000 0000 0000 0000 0000 0000 0101 |
with m = -5 and n = -2, the result of the sorting will be
No. |
Decimal number |
Binary 32 bit representation |
1 |
-4 |
1111 1111 1111 1111 1111 1111 1111 1100 |
2 |
-5 |
1111 1111 1111 1111 1111 1111 1111 1011 |
3 |
-3 |
1111 1111 1111 1111 1111 1111 1111 1101 |
4 |
-2 |
1111 1111 1111 1111 1111 1111 1111 1110 |
Given m, n and k (1 ≤ k ≤ min{n − m + 1, 2 147 473 547}), your task is to write a program to find a number corresponding to k-th representation in the sorted sequence.
Input
The input consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 1000. The following lines describe the data sets.
For each data set, the only line contains 3 integers m, n and k separated by space.
Output
For each data set, write in one line the k-th number of the sorted numbers.
Example
Sample input:
- -
Sample output:
-
Solution
完了,一道简单题调了3个小时
#include<stdio.h>
inline int Rin(){
int x=,c=getchar(),f=;
for(;c<||c>;c=getchar())
if(!(c^))f=-;
for(;c>&&c<;c=getchar())
x=(x<<)+(x<<)+c-;
return x*f;
}
int f[][];
void init(){
int i,j;
f[][]=;
for(i=;i<=;i++){
f[i][]=f[i][i]=;
for(j=;j<i;j++)
f[i][j]=f[i-][j-]+f[i-][j];
}
}
int cal(int x,int k){
int cnt=,ans=,i;
for(i=;i;i--){
if(x&(<<i)){
cnt++;
if(cnt>k)break;
x^=(<<i);
}
if((<<(i-))<=x)
ans+=f[i-][k-cnt];
}
if(cnt+x==k)ans++;
return ans;
}
int solve(int x,int y,int k){
int i,cnt=;
for(i=;i<=;i++){
cnt=cal(y,i)-cal(x-,i);
if(k<=cnt)break;
k-=cnt;
}
int l=x,r=y,mid,ans=;
while(l<=r){
mid=l+r>>;
if(cal(mid,i)-cal(x-,i)<k)
l=mid+;
else
ans=mid,r=mid-;
}
return ans;
}
int main(){
init();
int T=Rin(),n,m,K;
while(T--){
m=Rin(),n=Rin(),K=Rin();
if(!m && !n)puts("");
else
if(!m){
K--,m=;
if(!K)puts("");
else printf("%d\n",solve(m,n,K));
}
else if(m>)printf("%d\n",solve(m,n,K));
else if(!n){
K--,n=-;
if(!K)puts("");
else printf("%d\n",(<<)|solve(m,n,K));
}
else printf("%d\n",(<<)|solve(m,n,K));
}
getchar();getchar();
return ;
}
最新文章
- border-radius结合transition的一个小应用(动画)
- 线性时间O(n)内求数组中第k大小的数
- Hyperledger fabric Client Node.js Hello World示例程序
- Winform开发框架之通用数据导入导出操作的事务性操作完善
- spark基础练习(未完)
- 函数参数选项的处理getopt getopt_long getopt_long_only
- Excel skills (2) -- 自动调整行宽列高
- C#微信开发之旅--自定义菜单
- 利用代码改变世界 #AzureDev
- Linux学习笔记——例说makefile 头文件查找路径
- TortoiseGit客户端密钥配置
- Android笔记:Fragment与ViewPager组合时,如何在FragmentActicity获取Fragment对象
- SQL动态语句 拼接SQL 并输入输出值
- 【前端单元测试入门02】react的单元测试之Enzyme
- Java中for_each循环的使用
- 一、docker的原理
- mysql 8.0 ~ 安装
- delphiredisclient开源GIT
- scala map操作 简单总结
- 字符串过滤掉所有最邻近的“<;”和“>;”之间的字符