首页 > 其他 > 详细

CodeForces 288C - Polo the Penguin and XOR operation(思维)

时间:2015-06-21 18:34:53      阅读:117      评论:0      收藏:0      [点我收藏+]

题意:

就是让你构造一个序列,使得序列异或和最大,序列为n 的全排列 ,序列和计算方式为   SUM  =   a[1] ^ 0 + a[2] ^ 1 + a[3] ^ 2 + .......a[n] ^ n 

构造出一个序列使得和最大

题解:

策略为使得每次异或出来的结果的1尽可能多,而优先从最大的n  开始考虑,因为n  最有可能出更大的数字

代码:

#include<stdio.h>
#include<string.h>
int Ans[1000005];
int main()
{
    int n, x;
    while(scanf("%d", &n) != EOF)
    {
         x = 1;

         while(x <= n)  x = x<<1;
         x --;
         memset(Ans, 255, sizeof(Ans));
         for(int i = n; i>= 0; i--)
         {
             if(Ans[i] != -1) continue;
          //   printf("%d\n", x);
             while((x^i) > n || Ans[x^i] != -1)  x = x>>1;
        //     printf("%d %d\n", i, x);
             Ans[x^i] = i, Ans[i] = x^i;
         }
         __int64 sum = 0;
         for(int i = 0; i <= n; i++)
         {
             sum += (i^Ans[i]);
         }
         printf("%I64d\n%d", sum, Ans[0]);
         for(int i = 1; i <= n;  i++)
         printf(" %d", Ans[i]);
         printf("\n");
    }
}

CodeForces 288C - Polo the Penguin and XOR operation(思维)

原文:http://blog.csdn.net/q651111937/article/details/46582493

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!