Atcoder D - XOR Replace（思维）

题目链接：http://agc016.contest.atcoder.jp/tasks/agc016_d

题解：稍微想一下就知道除了第一次的x是所有的异或值，之后的x都是原先被替换掉的a[i]所以要想可以通过操作得到必须使a[i]里的所有数b[j]里都有

而且数量相同，(a[0]=a[1]^a[2]^..^a[n]，b[0]=b[1]^b[2]^..^b[n])。然后就是怎么交换能够使得操作数最少，其实可以用并查集，但是用dfs比较好理解

一点其实都是一样的。显然f[a[i]]=b[i]，于是如果a[i]!=b[i]就可以把a[i]-b[i]连起来然后dfs一遍肯定能在a[i]结束。最后找一下规律就行。注意i=0链接

时候的贡献是不需要的。

#include <iostream>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

const int M = 1e5 + 10;

int a[M] , b[M] , ha[M] , hb[M];

bool vis[M] , have[M];

vector<int>vc[M];

void dfs(int u) {

    vis[u] = true;

    int len = vc[u].size();

    for(int i = 0 ; i < len ; i++) {

        int v = vc[u][i];

        if(vis[v]) continue;

        dfs(v);

    }

}

int main() {

    int n;

    cin >> n;

    a[0] = 0;

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

        cin >> a[i];

        a[0] ^= a[i];

        ha[i] = a[i];

    }

    ha[0] = a[0];

    b[0] = 0;

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

        cin >> b[i];

        b[0] ^= b[i];

        hb[i] = b[i];

    }

    hb[0] = b[0];

    sort(ha , ha + n + 1);

    sort(hb , hb + n + 1);

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

        if(ha[i] != hb[i]) {

            cout << -1 << endl;

            return 0;

        }//这里是判断能否通过操作得到。

    }

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

        a[i] = lower_bound(ha , ha + 1 + n , a[i]) - ha;

        b[i] = lower_bound(hb , hb + 1 + n , b[i]) - hb;

    }//离散一下由于a[i],b[i]太大了。当然用map就不用这样操作了。

    int ans = 0;

    memset(have , false , sizeof(have));

    memset(vis , false , sizeof(vis));

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

        if(a[i] != b[i] || i == 0) {

            if(i) ans++;

            have[a[i]] = true , have[b[i]] = true;

            vc[a[i]].push_back(b[i]);

        }

    }

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

        if(!vis[i] && have[i]) {

            dfs(i) , ans++;

        }

    }

    ans--;//这里的ans--是减去第0位点被算进去的情况

    ans = max(ans , 0);

    cout << ans << endl;

    return 0;

}

巴特西

Atcoder D - XOR Replace（思维）

最新文章

热门文章