G:网络流

题意:
将题意简单化
意思是给你一个数组 a 已经填出了奇数位置的值,
要求你填完偶数位置,填入偶数位置的值只能是属于 [0,n - 1] 且 不在奇数位置出现
填数的要求如下
1: 任意两个相邻位置的数的二进制有且仅有一位不同
2: 第 n 位 只需要保证与 n - 1 位 有一个不同即可
保证有解

解析: 半天看不懂题,看懂题之后就知道怎么做了
将限制转换成为建边
首先对于网络流的题应该 先规划出 源点S 汇点T 以及中间点的范围;
本题 将 a 数组中能够出现的数字 [0, n - 1], 以及 (a数组中的下标)[n, 2 * n] 设为中间点 
S 设为 n, T 设为 2 * n;

因为对于我们填入的偶数坑,实际上是有两个限制的,要同时满足 跟两边的奇数坑里的数只有一个二进制位不同,
那么手动模拟一下情况可以知道,
当 a[i] 与 a[i + 2] 在某个二进制位相同时 a[i + 1] 在这一位也只能取相同
当他们在当前二进制位不同时 a[i + 1] 可以取反;
如此我们可以建一条S 向 n + i + 1 的边 容量为 1
同时对 当前位置可填入的值 res 建一条 n + i + 1 向 res 的边
同时 res 要向 T 建一条边;
注意每个 res 只能向 T 建一条边,因为实际上这个 res 只能被用一次, 我们用set 去重即可
特殊的 对于 n 这个位置而言 他只有 n - 1 一个约束条件 所以随便改，只要值小于 n 都可以建边
最后套板子;

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define x first
#define y second
using namespace std;
const int maxN = 2e5 + 10;
const int maxM = 2e5 + 10;
const int INF = 1e18;
const int mod = 998244353;
inline ll read()
{
    ll ans=0,f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return f?-ans:ans;
}
int m,n,S,T;
struct edge
{
    int nxt,to,f;
}e[maxM << 1];
int head[maxN << 1],idx;
void add(int u,int v,int w)
{
    e[idx] = {head[u], v, w}; head[u] = idx++;
}
int d[maxN], cur[maxN], a[maxN];
bool bfs()
{
    queue<int>q;
    for(int i = 0 ; i <= T ; i++) d[i] = -1;
    q.push(S),cur[S] = head[S];
    d[S] = 0;
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        for(int i = head[t] ; ~i ; i = e[i].nxt)
        {
            int ver = e[i].to;
            if(d[ver] == -1 && e[i].f)
            {
                d[ver] = d[t] + 1;
                cur[ver] = head[ver];
                if(ver == T) return true;
                q.push(ver); 
            }
        }
    }
    return false;
}
int find(int u, int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = head[u] ; ~i && flow < limit ; i = e[i].nxt)
    {
        cur[u] = i;
        int ver = e[i].to;
        if(d[ver] == d[u] + 1 && e[i].f)
        {
            int t = find(ver, min(e[i].f, limit - flow));
            if(!t) d[ver] = -1;
            e[i].f -= t;
            e[i ^ 1].f += t;
            flow += t;
        }
    }
    return flow;

}
void dinic()
{
    int r = 0,flow;
    while(bfs())
        while((flow = find(S,INF)) && flow)
            r += flow;
    for(int i = 0 ; i < idx ; i += 2)
    {
        if(!e[i].f && e[i].to < n && e[i ^ 1].to > n)
            a[e[i ^ 1].to - n] = e[i].to;
    }
    for(int i = 1 ; i <= n ; i++) printf("%lld ",a[i]);
}
signed main()
{
    memset(head, -1, sizeof head);
    n = read();
    S = n, T = n + n + 1;
    for(int i = 1 ; i <= n ; i += 2) a[i] = read();
    int res = 0;
    set<pair<int,int>>G;
    for(int i = 1 ; i < n - 1 ; i += 2)
    {
        for(int j = 17 ; j >= 0 ; j--)
        {
            if((a[i] >> j & 1) == (a[i + 2] >> j & 1)) continue;
            else 
            {
                if(a[i] >> j & 1) 
                {
                    res = a[i + 2] + (1ll << j);
                    if(G.find({S, n + i + 1}) == G.end())
                    {
                        G.insert({S,n + i + 1});
                        add(S, n + i + 1, 1);
                        add(n + i + 1, S, 0);
                    }
                    add(n + i + 1, res, 1);
                    add(res, n + i + 1, 0);
                    if(G.find({T, res}) == G.end())
                    {
                        G.insert({T, res});
                        add(res, T, 1);
                        add(T, res, 0);
                    }
                }
                else 
                {
                    res = a[i + 2] - (1ll << j);
                    if(G.find({S, n + i + 1}) == G.end())
                    {
                        G.insert({S,n + i + 1});
                        add(S, n + i + 1, 1);
                        add(n + i + 1, S, 0);
                    }
                    add(n + i + 1, res, 1);
                    add(res, n + i + 1, 0);
                    if(G.find({T, res}) == G.end())
                    {
                        G.insert({T, res});
                        add(res, T, 1);
                        add(T, res, 0);
                    }
                }
            }
        }
    }
    res = 0;
    add(S, 2ll * n, 1);
    add(2ll * n, S, 0);
    for(int i = 17 ; i >= 0 ; i--)
    {
        if(a[n - 1] >> i & 1)
        {
            res = a[n - 1];
            res -= (1ll << i);
            if(res > n - 1) continue;
            add(2 * n, res, 1);
            add(res, 2 * n, 0);
            if(G.find({T, res}) == G.end())
            {
                G.insert({T, res});
                add(res, T, 1);
                add(T, res, 0);
            }
        }
        else 
        {
            res = a[n - 1];
            res += (1ll << i);
            if(res > n - 1) continue;
            add(2 * n, res, 1);
            add(res, 2 * n, 0);
            if(G.find({T, res}) == G.end())
            {
                G.insert({T, res});
                add(res, T, 1);
                add(T, res, 0);
            }
        }
    }
    dinic();
    system("pause");
    return 0;
}