关于选数异或问题的几种解答及相关讨论。

解题思路:关于此题，没来没当回事，所以使用了比较暴力的做法。然后经历了空间超限、时间超限等问题，下面是三种解法。

注意事项:

参考代码:

/*第一份代码，此份代码思维简单粗暴，但空间超限仅为只过了两份数据，但时间消耗小*/
#include<iostream>
#include<vector>


using namespace std;


const int MAX = 100001;//数据量最大为100000。

/*
第一次想法：
简单粗暴，把所有的n个整数两两异或的结果存放到一个n*n的矩阵中
然后在后续的输入中直接查询矩阵就好
这就像是对数据进行分析，将分析后的数据存放，使用的时候在读取
*/

int main()
{

    int n, m, x;
    cin >> n >> m >> x;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    vector<int> l(m);
    vector<int> r(m);
    for (int i = 0; i < m; i++)
    {
        cin >> l[i]>>r[i];
    }
    
    //定义n*n的结果矩阵，存放结果。
    vector<vector<bool>> res(n, vector<bool>(n,false));
    
    //矩阵赋值过程
    //a1要与a2,a3,a4...进行异或
    //a2要与a3,a4,a5...进行异或
    for (int i = 0; i < n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            if ((a[i] ^ a[j]) == x)
            {
                res[i][j] = true;
            }
        }
    }

    //然后是根据该数据集处理问题
    
    for (int i = 0; i < m; i++)
    {
        //对于每一组数据
        
        bool exit = false;

        //需要检查|l[i]到r[i],l[i]到r[i]|这个矩阵中有没有1。

        for (int j = l[i] - 1; j <= r[i] - 1; j++)
        {
            for (int k = j+1; k <= r[i] - 1; k++)
            {
                if (res[j][k]==true)
                {
                    exit = true;
                    break;
                }
            }
            if (exit)
                break;
        }
        cout << (exit ? "yes" : "no") << endl;;
    }

    return 0;
}
/*代码注释详细，我就不多比比了，接下请看第二份代码，使用了dp，但也没有满分，因为时间超限卡了四份数据*/
#include<iostream>
#include<vector>


using namespace std;


const int MAX = 100001;//数据量最大为100000。



int main()
{
    /*
    第一种方法很明显十分笨拙，为什么呢？
    处理了没必要的数据，我们不必知道那么详细的数据，存放起来
    数据处理的过于详细不仅会导致占用空间，而且在使用数据时还要对数据进行在此处理
    我们只需要从数据中处理出我们需要的信息，不必那么详细，在使用时能刚好就拿来用。
    那么这么想，
    对每一个a[i]，创建对应的一个整形变量，存放着到那个位置有异或为1。该变量初始化为无限大，然后在输入数据的同时不断更新。
    */

    int n, m, x;
    cin >> n >> m >> x;
    vector<int> a(n);
    vector<int> res_a(n,MAX);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        //每输入一个数，都要对已输入的数的res_a进行动态的检测修改。
        for (int j = 0; j < i; j++)
        {
            //倘若这个值的所在更小，那么才有检测的必要
            if (i < res_a[j])
            {
                if ((a[j] ^ a[i]) == x)
                {
                    //更新
                    res_a[j] = i;
                }
            }
        }
    }
    //此时的res_a里，有每个位置的值自己异或结果为x的最小位置。
    //我们想要的，是每个位置异或为x的最小区间。因此我们最后要更新一下这个结果。

    for (int i = n - 2; i >= 0; i--)
    {
        if (res_a[i] > res_a[i+1])
            res_a[i] = res_a[i + 1];
    }

    vector<int> l(m);
    vector<int> r(m);
    for (int i = 0; i < m; i++)
    {
        cin >> l[i] >> r[i];
    }


    for (int i = 0; i < m; i++)
    {
        if (res_a[l[i] - 1] <= r[i] - 1)
            cout << "yes" <<endl;
        else
            cout << "no" <<endl;
    }
    return 0;
}
/*这个算法的时间复杂度为O(n²)，因此卡了一部分数据。*/


/*注释详细，我就不多比比了，下面看第三份满分代码*/
#include<iostream>
#include<vector>


using namespace std;


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, x;
    cin >> n >> m >> x;
    vector<int> a(n);

    //定义dp,其中存放对于每个位置i来说，若i为r，那么期间存在与l异或为x的最小的区间，即最大的l。
    //初始化时，要让区间尽量大，于是让l尽量小，我干脆让其为-1
    vector<int> dp(n, -1);

    //存放每一个a[i]的位置，a[i]的最大为2的20次方，约小于1 100 000
    //且初始化值为最小
    vector<int> position_of_a(1100000,-1);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    //i从1开始是因为，第一个的索引为0的数作为r的话，一定不存在yes的情况
    //而且，for循环里有需要i-1的地方。
    for (int i = 1; i < n; i++)
    {
        position_of_a[a[i]] = i;
        //但是，如果数据中有重复的数据怎么办呢？
        //我想，对于每一个a[i]，它与x异或，得到目标值。
        //我们令a[i]的位置为r，那么目标值的位置一定是在a[i]的左边的。
        //那么对于目标值，如果已输入的目标值有多个，那么我一定希望取不大于a[i]中尽量大的，以获得更小的区间。
        //而这时，a[i]右边的值的位置信息，我们还没有赋值，被初始化为最小整形，那么我直接取目标位置最大的就好。
        //那么，dp里就是这个position_of_a[[i]^x],或者是左边的那个值的可异或区间
        dp[i] = max(position_of_a[a[i] ^ x],dp[i-1]);
    }
    /*检验*/
    /*
    for (int i = 0; i < n; i++)
    {
        cout << dp[i] << endl;
    }
    */
    vector<int> l(m);
    vector<int> r(m);
    for (int i = 0; i < m; i++)
    {
        cin >> l[i] >> r[i];
    }
    for (int i = 0; i < m; i++)
    {
        if (dp[r[i] - 1] >= l[i] - 1)
            cout << "yes"<<'\n';
        else
            cout << "no" << '\n';
    }
    
    return 0;
}
/*这里要注意“
ios_base::sync_with_stdio(0);
    cin.tie(0);
”是必要的。或者把输入输出改为scanf，printf，这样不需要这两行也能过。还有在使用这两行代码时不能使用endl换行，而要使用'\n'。
总之，干脆使用scanf，printf吧，输出格式化也方便。*/