给定一个自然数M,及其二进制长度N,得到一个N位的二进制串 b1 b2 ... bN-1 bN 将该串做左旋转,即b1移到bN后面,得到一个新的二进制串: b2 b3 ... bN-1 bN b1 对新的二进制串再做左旋转,得二进制串 b3 b4 ... bN-1 bN b1 b2 重复旋转操作操作,可得N个二进制串,对这N个串排序,可得一个N*N的矩阵. 例如: 1 0 0 0 1->0 0 0 1 1->0 0 1 1 0->0 1 1 0 0->1 1 0 0 0 对它们做排序,得矩阵
0 0 0 1 1
0 0 1 1 0
0 1 1 0 0
1 0 0 0 1
1 1 0 0 0
问:给出一个自然数M,及其二进制长度N,求出排序矩阵的最后一列。 对于上面的例子,给出M=3,N=5,要你的程序输出10010。 补充说明:存在自然数M的二进制表达超过N位的情况,在这种情况下,取前N次循环的二进制串排序后的最后一列即可。
第一行有一个自然数K,代表有K行测试数据(K<=1000)。 第二行至第K+1行,每行的第一个为自然数M,第二个为二进制长度N(N<64)。
输出K行,每行N个二进制,表示矩阵最后一列从上到下的二进制。
3
3 5
4 7
1099512709120 45
10010
1000000
110000000000000000000000000000100000000000000
CodingTrip - 携程编程大赛 (预赛第一场)
题意不明确,到底超过了n之后全保留排序结果是挫的,截取后面的n位反而是对的...
这道题还恶心,居然m要用unsigned __Int64
代码:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char str[68][100];
int cmp(const void *a , const void *b)
{
return strcmp((char *)a ,(char *)b);
}
int main()
{
int test,nn,i,j;
unsigned __int64 m;
scanf("%d",&test);
while(test--)
{
scanf("%I64d%d",&m,&nn);
memset(str,'0',sizeof(str));
i=nn-1;
while(m>0)
{
if(m&1) str[0][i]='1';
m>>=1L;
i--;
if(i<0) break;
}
for(i=1;i<nn;i++)
{
for(j=0;j<nn;j++)
{
str[i][j]=str[i-1][(j+1)%nn];
}
}
qsort(str,nn,sizeof(str[0]),cmp);
for(i=0;i<nn;i++)
printf("%c",str[i][nn-1]);
putchar(10);
}
return 0;
}