CodingTrip - 携程编程大赛（预赛第一场）第四题

时间：2014-04-11 14:11:28 阅读：530 评论：0 收藏：0 [点我收藏+]

旋转的二进制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2119 Accepted Submission(s): 339

Problem Description

给定一个自然数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次循环的二进制串排序后的最后一列即可。

Input

第一行有一个自然数K，代表有K行测试数据（K<=1000）。
第二行至第K+1行，每行的第一个为自然数M，第二个为二进制长度N(N<64)。

Output

输出K行，每行N个二进制，表示矩阵最后一列从上到下的二进制。

Sample Input

3 5

4 7

1099512709120 45

Sample Output

10010

1000000

110000000000000000000000000000100000000000000

这题目是改了又改，总感觉还是有问题。这句话“补充说明：存在自然数M的二进制表达超过N位的情况，在这种情况下，取前N次循环的二进制串排序后的最后一列即可”不知道管理员有没有正确的表达自己的意思。自我感觉没错，但是就是不对···等题目出来再继续调吧。

  1 /*
  2 ID: asif
  3 LANG: C++
  4 TASK: test
  5 */
  6 //# pragma comment(linker, "/STACK:102400000,102400000")
  7 # include<iostream>
  8 # include<cstdio>
  9 # include<cstdlib>
 10 # include<cstring>
 11 # include<algorithm>
 12 # include<cctype>
 13 # include<cmath>
 14 # include<string>
 15 # include<set>
 16 # include<map>
 17 # include<stack>
 18 # include<queue>
 19 # include<vector>
 20 # include<numeric>
 21 using namespace std;
 22 const int maxn=128;
 23 const double inf=0.000001;
 24 const int INF=~0U>>1;
 25 const int mod=1000000007;
 26 # define PI (acos(0)*2.0)
 27 # define lson l,m,rt<<1
 28 # define rson m+1,r,rt<<1 | 1
 29 # define PS printf("\n")
 30 # define S(n) scanf("%d",&n)
 31 # define P(n) printf("%d\n",n)
 32 # define Ps(n) printf(" %d",(n))
 33 # define SB(n) scanf("%llu",&n)
 34 # define PB(n) printf("%llu\n",n)
 35 # define PBs(n) printf(" %llu",n)
 36 # define SD(n) scanf("%lf",&n)
 37 # define PD(n) printf("%.3lf\n",n)
 38 # define Sstr(s) scanf("%s",s)
 39 # define Pstr(s) printf("%s\n",s)
 40 # define S0(a) memset(a,0,sizeof(a))
 41 # define S1(a) memset(a,-1,sizeof(a))
 42 typedef unsigned long long ll;
 43 ll n,ans[maxn];
 44 int m,a[maxn];
 45 int equal(double x,double y)
 46 {
 47     if(x-y>=-inf&&x-y<=inf)
 48         return 0;
 49     else if(x-y>inf)
 50         return 1;
 51     return -1;
 52 }
 53 ll Pow(ll a,int b)
 54 {
 55     ll sum=1;
 56     while(b--)
 57         sum*=a;
 58     return sum;
 59 }
 60 int main()
 61 {
 62     //freopen("input.in", "r", stdin);
 63     //freopen("output.out", "w", stdout);
 64     int T;
 65     S(T);
 66     while(T--)
 67     {
 68         SB(n),S(m);
 69         /*if(n==0LL)
 70         {
 71             puts("0");
 72             continue;
 73         }*/
 74         int t=0;
 75         S0(ans);
 76         S0(a);
 77         ans[0]=n;
 78         while(n)
 79         {
 80             a[t++]=n%2;
 81             n>>=1;
 82         }
 83         while(t<m)
 84             a[t++]=0;
 85         for(int i=1;i<m;i++)
 86         {
 87             int temp=a[t-1];
 88             for(int j=t-1;j>0;j--)
 89                 a[j]=a[j-1];
 90             a[0]=temp;
 91             ll sum=0;
 92             for(int j=0;j<t;j++)
 93                 sum+=(ll)a[j]*Pow(2LL,j);
 94             ans[i]=sum;
 95         }
 96         sort(ans,ans+m);
 97         for(int i=0;i<m;i++)
 98             printf("%d",ans[i]%2);
 99         PS;
100     }
101     return 0;
102 }

View Code

错误找到了，“补充说明：存在自然数M的二进制表达超过N位的情况，在这种情况下，取前N次循环的二进制串排序后的最后一列即可”，这句话的意思是取自然数m的最后n位二进制位进行n次循环！！！呵呵···并且数据不能用long long，得用__int64，fuck。神题，无话可说···

不知道大神们在比赛的时候是怎么过的，膜拜

  1 /*
  2 ID: asif
  3 LANG: C++
  4 TASK: test
  5 */
  6 //# pragma comment(linker, "/STACK:102400000,102400000")
  7 # include<iostream>
  8 # include<cstdio>
  9 # include<cstdlib>
 10 # include<cstring>
 11 # include<algorithm>
 12 # include<cctype>
 13 # include<cmath>
 14 # include<string>
 15 # include<set>
 16 # include<map>
 17 # include<stack>
 18 # include<queue>
 19 # include<vector>
 20 # include<numeric>
 21 using namespace std;
 22 const int maxn=128;
 23 const double inf=0.000001;
 24 const int INF=~0U>>1;
 25 const int mod=1000000007;
 26 # define PI (acos(0)*2.0)
 27 # define lson l,m,rt<<1
 28 # define rson m+1,r,rt<<1 | 1
 29 # define PS printf("\n")
 30 # define S(n) scanf("%d",&n)
 31 # define P(n) printf("%d\n",n)
 32 # define Ps(n) printf(" %d",(n))
 33 # define SB(n) scanf("%I64u",&n)
 34 # define PB(n) printf("%llu\n",n)
 35 # define PBs(n) printf(" %llu",n)
 36 # define SD(n) scanf("%lf",&n)
 37 # define PD(n) printf("%.3lf\n",n)
 38 # define Sstr(s) scanf("%s",s)
 39 # define Pstr(s) printf("%s\n",s)
 40 # define S0(a) memset(a,0,sizeof(a))
 41 # define S1(a) memset(a,-1,sizeof(a))
 42 typedef unsigned __int64 ll;
 43 ll n,ans[maxn];
 44 int m,a[maxn];
 45 int equal(double x,double y)
 46 {
 47     if(x-y>=-inf&&x-y<=inf)
 48         return 0;
 49     else if(x-y>inf)
 50         return 1;
 51     return -1;
 52 }
 53 ll Pow(ll a,int b)
 54 {
 55     ll sum=1;
 56     while(b--)
 57         sum*=a;
 58     return sum;
 59 }
 60 int main()
 61 {
 62     //freopen("input.in", "r", stdin);
 63     //freopen("output.out", "w", stdout);
 64     int T;
 65     S(T);
 66     while(T--)
 67     {
 68         SB(n),S(m);
 69         /*if(n==0LL)
 70         {
 71             puts("0");
 72             continue;
 73         }*/
 74         int t=0;
 75         S0(ans);
 76         S0(a);
 77         //ans[0]=n;
 78         /*while(n)
 79         {
 80             a[t++]=n%2;
 81             n>>=1;
 82         }
 83         while(t<m)
 84             a[t++]=0;*/
 85         for(;t<m;t++)
 86             a[t]=n%2,n/=2;
 87         for(int i=0;i<m;i++)
 88         {
 89             ll sum=0;
 90             for(int j=0;j<t;j++)
 91                 sum+=(ll)a[j]*Pow(2LL,j);
 92             ans[i]=sum;
 93             int temp=a[t-1];
 94             for(int j=t-1;j>0;j--)
 95                 a[j]=a[j-1];
 96             a[0]=temp;
 97         }
 98         sort(ans,ans+m);
 99         for(int i=0;i<m;i++)
100             printf("%d",ans[i]%2);
101         PS;
102     }
103     return 0;
104 }

View Code

CodingTrip - 携程编程大赛（预赛第一场）第四题,布布扣,bubuko.com

CodingTrip - 携程编程大赛（预赛第一场）第四题

原文：http://www.cnblogs.com/asif/p/3657965.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)

CodingTrip - 携程编程大赛 （预赛第一场）第四题

旋转的二进制

CodingTrip - 携程编程大赛（预赛第一场）第四题