P15653 题解

· · 题解

Problem Link

赛时做法，好像很短，而且没有什么细节，写完差不多一遍就过了大样例。

先猜一下答案，观察一下题目里的不变量，发现 \binom k2 为偶数时总边数奇偶性不变，k 为奇数时每个点度数奇偶性不改变。

我们考虑最终哪些边 E 被操作了奇数次，显然我们想让 E 为 G 的补，并进行最少次数的调整使得上述的两个条件满足。

如果 k 是偶数，那么至多随便改一条边使 |E|\bmod 2=0 即可。

否则先把奇度点两两匹配，将匹配边翻转，如果还要改变总边数奇偶性，需要分讨。

如果不存在奇度点，直接翻转一个三元环，否则选一组匹配 (x,y) 翻转任意一个三元环 (x,y,t)，由于 (x,y) 被翻转过，所以次数只加一。

发现这个次数是正确的，考虑对这样的一组 E 构造方案。

尝试归纳，如果 n>k+2，尝试删掉第 n 个点。

此时我们进行若干过 n 的操作，并且不关心其对前 n-1 个点的影响，那就相当于每次翻转 k-1 个变量。

如果 n 度数为奇数，则 2\mid k，操作一次后度数变为偶数。

然后把 n 的邻域两两匹配，对于一对匹配 x,y，操作 n+x+S,n+y+S 即可，S 只要大小为 k-2，可以任选。

只要我们在首次调整后不让 n 的邻域大小变成 n-1（只要在调整时优先选 n 的邻居），则至多操作 n-1 次可以递归 (n-1,k) 的子问题。

直到 n=k+2，显然此时本质不同的操作只有 \binom n2 个，我们可以任意操作，记录一下哪些操作被进行了奇数次即可，所以总的操作次数一定不会越界。

显然考虑选出集合的补集 x,y，可以看成翻转所有边，然后翻转 x,y 的出边，再翻转边 (x,y)。

考虑构造一些抵消的量，如果总边数是偶数，那么翻转所有边可以被忽略，如果每个点操作次数是偶数，那么操作 (x,y) 相当于只翻转了边 (x,y)。

那么目标就是把总操作数和每个点的度数都变成偶数，总边数为奇数则 \binom k2\bmod 2=1 只要随便操作一次即可。

然后我们把奇度点两两匹配，每对点的补集操作一次，这样的效果是连接奇度和偶度点的边被翻转，且每对匹配边被翻转。

这样就使得每个点度数都是偶数，对每条存在的边，使其作为补集操作一次。

我们要证明总操作次数是偶数，如果奇度点存在，则必有 n\equiv k\equiv 0\bmod 2，所以连接奇度和偶度点的边数为偶数，则这部分操作次数和边的奇偶性改变量一致，那么总操作次数和原始边数奇偶性一致，均为偶数。

所以我们就完成了构造，操作次数不超过 \binom n2。

时间复杂度 \mathcal O(n^3)，需要精细实现一些操作对 E 的影响。

代码：

复刻赛时代码，目前通过了 QOJ 数据。

#include<bits/stdc++.h>
#include "starmap.h"
using namespace std;
namespace luotianyi {
bitset<505>a[505],o;
bool f[505][505],d[505];
int sz(const vector<int>&v) { return v.size(); }
void revE(int x,int y) { a[x].flip(y),a[y].flip(x); }
void build(int n,int k) {
    memset(f,0,sizeof(f));
    int tot=0;
    for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if(a[i][j]) tot^=1;
    if(tot) {
        o.reset(),f[n-1][n]^=1;
        for(int i=1;i<=k;++i) o.set(i);
        for(int i=1;i<=k;++i) a[i]^=o,a[i][i]=0;
    }
    memset(d,0,sizeof(d));
    vector <int> h;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=n;++j) if(i!=j&&a[i][j]) d[i]^=1;
        if(d[i]) h.push_back(i);
    }
    for(int i=0;i<sz(h);i+=2) f[h[i]][h[i+1]]^=1,revE(h[i],h[i+1]);
    for(int i=1;i<=n;++i) if(!d[i]) for(int j=1;j<=n;++j) if(d[j]) revE(i,j);
    for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if(a[i][j]) f[i][j]^=1;
    for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if(f[i][j]) {
        vector <int> q;
        for(int t=1;t<=n;++t) if(t!=i&&t!=j) q.push_back(t);
        invert(q);
    }
}
void solve(int n,int k) {
    if(n==k+2) return build(n,k);
    vector <int> h;
    for(int i=1;i<n;++i) if(a[i][n]) h.push_back(i);
    if(sz(h)%2==1) {
        vector <int> q{n};
        while(h.size()&&sz(q)<k) q.push_back(h.back()),h.pop_back();
        for(int i=1;i<n;++i) if(!a[i][n]&&sz(q)<k) q.push_back(i),h.push_back(i);
        invert(q),o.reset();
        for(int i=1;i<k;++i) o.set(q[i]);
        for(int i=1;i<k;++i) a[q[i]]^=o,a[q[i]][q[i]]=0;
    }
    for(int i=0;i<sz(h);i+=2) {
        int x=h[i],y=h[i+1];
        vector <int> q{n,x};
        for(int j=1;j<n;++j) if(j!=x&&j!=y&&sz(q)<k) q.push_back(j);
        invert(q),q[1]=y,invert(q);
        for(int j=2;j<k;++j) revE(q[j],x),revE(q[j],y);
    }
    solve(n-1,k);
}
void starmap(int n,int m,int k,vector<int>u,vector<int>v) {
    for(int i=1;i<=n;++i) {
        a[i].reset();
        for(int j=1;j<=n;++j) if(i!=j) a[i][j]=1; 
    }
    for(int i=0;i<m;++i) revE(u[i],v[i]);
    if(k%2==0) {
        int z=n*(n-1)/2,c=k*(k-1)/2;
        if(c%2==0&&m%2!=z%2) revE(1,2),--z;
        report(z);
    } else {
        memset(d,0,sizeof(d));
        vector <int> h;
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=n;++j) if(i!=j&&a[i][j]) d[i]^=1;
            if(d[i]) h.push_back(i);
        }
        int c=k*(k-1)/2,z=n*(n-1)/2-sz(h)/2;
        for(int i=0;i<sz(h);i+=2) revE(h[i],h[i+1]);
        if(c%2==0&&m%2!=z%2) {
            if(sz(h)) {
                int x=h[0],y=h[1],t=(x>1?1:(y>2?2:3));
                revE(x,y),revE(x,t),revE(y,t),--z;
            } else z-=3,revE(1,2),revE(2,3),revE(1,3);
        }
        report(z);
    }
    solve(n,k);
}
}
void init(int,int) {}
void starmap(int n,int m,int k,int,vector<int>u,vector<int>v) {
    luotianyi::starmap(n,m,k,u,v);
}