异或图(异或运算)

发布于 2020-06-27  0 次阅读


题目地址:

异或图

思路:

对于异或运算,只需要特判两种情况,
1.当mp[x]^mp[y]==k时,一步到达
2.当mp[x]==mp[y]时,如果存在中间值使得mp[x]^mp[i]==k即可两步到达,这题时间卡的紧,使用快读读入,开数组记录读入的数据。

AC Code:

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=2e6+5;
int mp[maxn], vis[maxn];

inline int read()
{
    int x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * w;
}

int main()
{
    int n, q;
    n = read();
    q = read();
    for (int i = 1; i <= n; i++)
    {
        mp[i] = read();
        vis[mp[i]] = 1;
    }
    int k, x, y;
    for (int i = 0; i < q; i++)
    {
        k = read();
        x = read();
        y = read();
        if ((mp[x] ^ mp[y]) == k)
            printf("1\n");
        else if (mp[x] == mp[y] && vis[k ^ mp[x]])
            printf("2\n");
        else
            printf("-1\n");
    }
    return 0;
}

平平无奇的在校大学生