CodeForces - 862C Mahmoud and Ehab and the xor(构造)【异或】

题目大意：

给出n、m,现在需要你输出任意n个不相同的数(n,m<1e5)，使他们的异或结果为m，如果不存在n个不相同的数异或结果为m,则输出"NO"，本题中所有数均需小于1e6。

解题分析：
因为本题是SPJ，且当n比较大的时候，需要输出很多数，所以我们试着去构造这n个数，力图找出一些规律。n<=2的时候很好直接进行特判即可。n>=3的时候，可以直接进行简单的构造，比如前面n-1项依次设为1,2,3,……（下面假设前面这些连续的项异或结果为res），最后一项为 cur = res^m (这是根据 0^x = x ，这个公式得到的，即前面的所有项都进行简单构造，然后最后一项让这n个数的异或结果为m)。这样看上去很完美，实际上存在一些漏洞。因为题目要求这n个数必须不相同，但是按照上面的构造方法，是可能让cur与前面n-1个数相同的，不相信的同学可以简单构造反例，所以，我们需要引进两个大的二进制数来避免这种情况，因为按照我们前面的够着方法，前n-1个数最大会小于n，而n<1e5,但是题目对我们构造的数的范围要求要小于1e6，所以我们可以添加两个大于1e5，小于1e6的数，同时，尽量让这两个数与之前构造的n-3个数之间相互异或的结果都不能为0 (至于为什么是要两个这样的数，可以自行举反例，主要的判断冲突依据就是这n个数必须互不相同)。所以最后的一个数cur = res^x1^x2^m。

#include <iostream>

using namespace std;

int main(){

    ios::sync_with_stdio(false);

    int n,m;cin>>n>>m;

    if(n==){

        puts("YES");

        cout<<m<<endl;

    }else if(n==){

        if(!m) {

            puts("NO");

        }else {

            puts("YES");

            cout<<"0 "<<m<<endl;

        }

    }else{

        int x1=<<,x2=<<;

        puts("YES");

        int res=;

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

            cout<<i<<" ";

            res^=i;

        }

        cout<<x1<<" "<<x2<<" "<<(res^x1^x2^m) <<endl;

    }

}

2019-02-01

巴特西

CodeForces - 862C Mahmoud and Ehab and the xor(构造)【异或】

最新文章

热门文章