862C - Mahmoud and Ehab and the xor（构造）

原题链接：http://codeforces.com/contest/862/problem/C

题意：给出n,x，求n个不同的数，使这些数的异或和为x

思路：(官方题解）只有n==2&&x==0时输出NO，接下来考虑YES的情况

先定义一个数pw=2¹⁷（输出答案时保证不会出现重复数字）

因为数x 完全可以由三个数异或得到，那么对于n>3的情况，先求1到n-3的异或和，得到y，如果y==x，那么剩下三个数为pw, pw*2, pw^(pw*2)（当x==0时，0， pw，pw^x的输出是不符合题意的），否则输出0， pw，pw^x^y。

n<=3的情况可以直接输出。

AC代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int MAXN=1e5+;

 const int pw=<<;

 int main()

 {

     int n,x;

     scanf("%d %d", &n, &x);

     if(n==&&x==)printf("NO\n");

     else

     {

         printf("YES\n");

         if(n==) printf("%d\n", x);

         else if(n==) printf("%d %d\n", , x);

         else if(n==) printf("%d %d %d\n", pw^x, pw<<, pw^(pw<<));

         else

         {

             int res=;

             printf("%d", );

             for(int i=;i<=n-;i++){

                 res^=i;

                 printf(" %d", i);

             }

             if(res==x){

                 printf(" %d %d %d\n", pw, pw<<, pw^(pw<<));

             }

             else {

                 //cout<<'*'<<endl;

                 printf(" %d %d %d\n", , pw, pw^x^res);

             }

         }

     }

     return ;

 }

巴特西

862C - Mahmoud and Ehab and the xor（构造）

最新文章

热门文章