题解：P15653 [省选联考 2026] 星图 / starmap

MicroSun · 2026-03-17 08:14:03 · 题解

我们将原图的边反转，存在的边变为不存在，不存在的边变为存在，接下来我们在这个等价问题上进行分析。

考虑能否进行一些操作，从 n 的问题递归到 n-1 的子问题，并且如果操作次数能不超过 n-1 就可以符合题目中的操作次数限制。我们希望删空 n 的邻边。可以发现，(n,a,x_1,\dots,x_{k-2}),(n,b,x_1,\dots,x_{k-2}) 可以删掉两条 n 的邻边，但是这无法处理点度数为奇数的情况。如果 k 为偶数，一次操作必然会反转一个点的度数奇偶性，我们只需带上一条存在的邻边操作一次即可。操作次数容易发现是正确的。否则一定任意操作都无法改变这个点的奇偶性。这启发我们，当 k\bmod 2=1 时，将奇度点两两配对并将它们中间的一条边反转（显然奇度点可以两两配对），容易证明这是达到最小操作次数的合法操作。

如此递归，直到 n=k+2。此时可以有的性质是，我们用一次操作没有包含的两个点即可确定一次操作，所以本质不同的操作只有 \frac{n(n-1)}2 种。我们可以忽略操作次数限制，只需尝试在这个时候将图删空。但是，如果 \frac{k(k-1)} 2 是偶数，我们又发现一个我们无论怎么操作都无法改变的量：总边数的奇偶性。在接下来的操作中，我们会构造性证明：如果总边数和每个点的度数都是偶数，我们一定可以将图删为空图。

为了讨论 \frac{k(k-1)}2 的奇偶性，我们需要对 k\bmod 4 的值进行讨论，同时我们上面还对 k\bmod 2 的值也进行了讨论，需要合并在一起保证正确处理了相互的影响。下面列出 k\bmod 4 对应的值、对应限制以及处理方法。

• 当 k\bmod 4=0 时，对点度数无限制，原图边数必须是偶数。为了将有奇数条边的图调整成合法的，我们只需任选一条边将其反转。
• 当 k\bmod 4=1 时，点度数必须全为偶数，原图边数必须是偶数。此时我们先两两配对奇度点，如果图边数不合法，再选择一个包含刚刚翻转的边的三元环翻转即可，这只会使答案加一（没有奇度点时，答案会加三），容易证明这是使操作次数最小化的构造。
• 当 k\bmod 4=2 时，对点度数无限制，原图边数无限制，任意图都可以被直接消成空图。
• 当 k\bmod 4=3 时，点度数必须全为偶数，原图边数无限制，我们只需两两配对奇度点即可。

如上分类讨论，除了 k\bmod 4=1 可能比较难想，其他还是相对自然的。接着我们回到 n=k+2 的情况，探究如何将满足对应限制的图删空。

我们先把图调整成边数、每个点的度数均为偶数的情况。边数为奇数只需随意进行一次操作，度数为奇数我们可以用 (a,x_1,\dots,x_{k-1}),(b,x_1,\dots,x_{k-1}) 同时满足两个点 a,b 的需求。

接下来有两种做法。

第一种是，观察到 (a,b,x_1,\dots,x_{k-2}),(b,c,x_1,\dots,x_{k-2}),(c,d,x_1,\dots,x_{k-2}),(d,a,x_1,\dots,x_{k-2}) 可以反转一个四元环，不妨在两个连通块之间加一条出现了两次的重边，那么整个图的欧拉回路拼起来可以得到一条边数为偶数的欧拉回路，接着先把一号点删空，再进行 (1,a_1,a_2,a_3),(1,a_3,a_4,a_5) 这样的操作就可以删掉一整条回路。

第二种是，关注一次操作中没有出现的两个点 (u,v)，将操作写为如下操作的并：全局反转，反转 (u,v)，反转 u,v 的邻边。如果我们对每一条边做一次操作，那么全局会被反转偶数次，每条边会被反转点度数次，恰好将图删空。

代码写的是第一种做法，写得很丑。

#include<bits/stdc++.h>
#include "starmap.h"
using namespace std;
#define pb push_back
#define fst first
#define scd second
#define rep(i,s,e) for(int i=s;i<=e;++i)
#define dep(i,s,e) for(int i=s;i>=e;--i)

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;

const int N=510;

void init(int c,int t){}
int c[N],mp[N][N],nn;
bitset<512> t[N];
vector<int> a;
void dfs(int u){
    a.pb(u);
    rep(i,1,nn) if(t[u][i]&&u!=i){
        t[u][i]=t[i][u]=0;
        dfs(i);
        break;
    }
}
void starmap(int n,int m,int k,int p,vector<int> u,vector<int> v){
    nn=n;
    memset(mp,0,sizeof(mp));
    memset(c,0,sizeof(c));
    a.clear();
    rep(i,1,n)
        rep(j,1,n) if(i!=j)
            t[i][j]=1;
    rep(i,0,m-1)
        t[u[i]][v[i]]=t[v[i]][u[i]]=0;
    rep(i,1,n) rep(j,1,n) if(i!=j) c[i]^=t[i][j];
    int cnt=0;
    rep(i,1,n) rep(j,i+1,n) cnt^=t[i][j];
    auto rev=[&](int i,int j){
        t[i].flip(j);t[j].flip(i);
        c[i]^=1;c[j]^=1;
    };
    int dans=0;

    //make sure the graph is good
    if(k%4==0){
        if(cnt){
            rev(1,2);
            dans=1;
            cnt^=1;
        }
    }
    else if(k%4==1){
        vector<int> t;
        rep(i,1,n) if(c[i]) t.pb(i);
        int lst=0;
        for(int i:t){
            if(lst==0) lst=i;
            else{
                rev(i,lst);
                cnt^=1;
                ++dans;
                lst=0;
            }
        }
        if(cnt){
            if(t.empty()){
                dans+=3;
                rev(1,2);rev(2,3);rev(3,1);
            }
            else{
                ++dans;
                int p=0;
                rep(i,1,n) if(i!=t[0]&&i!=t[1]) p=i;
                rev(p,t[0]);rev(t[0],t[1]);rev(t[1],p);
            }
        }
    }
    else if(k%4==3){
        int lst=0;
        rep(i,1,n) if(c[i]){
            if(!lst) lst=i;
            else{
                rev(lst,i);
                lst=0;
                ++dans;
            }
        }
    }
    report(n*(n-1)/2-dans);

    //start construction
    auto inv=[&](vector<int> ve,bool flg=1){
        if(flg) invert(ve);
        bitset<512> v;
        for(int i:ve) v[i]=1;
        for(int i:ve) t[i]^=v;
    };

    //i=k+3~n
    //delete a point i use cost at most i-1
    dep(i,n,k+3){
        int cnt=0,p=0;
        rep(j,1,i-1){
            cnt^=t[i][j];
            if(t[i][j]) p=j;
        }
        if(cnt){
            bool flg=0;
            vector<int> v;
            v.pb(i);
            rep(j,1,k-1){
                v.pb(j);
                if(t[i][j]) flg=1;
            }
            if(!flg){
                v.pop_back();
                v.pb(p);
            }
            inv(v);
        }
        int lst=0;
        rep(j,1,i-1) if(t[i][j]){
            if(!lst) lst=j;
            else{
                vector<int> v;
                v.pb(lst);v.pb(i);
                rep(t,1,i-1) if(t!=lst&&t!=j){
                    if(v.size()<k) v.pb(t);
                }
                inv(v);
                v.clear();
                v.pb(j);v.pb(i);
                rep(t,1,i-1) if(t!=j&&t!=lst){
                    if(v.size()<k) v.pb(t);
                }
                inv(v);
                lst=0;
            }
        }
    }

    //solve when n=k+2
    //make the graph good
    cnt=0;rep(i,1,n) rep(j,i+1,n) cnt^=t[i][j];
    if(k%4==3||k%4==2) if(cnt){
        mp[1][2]^=1;mp[2][1]^=1;
        rep(i,3,k+2) rep(j,3,k+2) t[i].flip(j);
    }
    rep(i,1,k+2) c[i]=0;
    rep(i,1,k+2)
        rep(j,1,k+2) if(i!=j) c[i]^=t[i][j];
    if(k%4==0||k%4==2){
        int lst=0;
        rep(i,1,k+2) if(c[i]){
            if(!lst) lst=i;
            else{
                int p=0,cnt=0;
                rep(t,1,k+2){
                    if(t!=lst&&t!=i){
                        if(cnt<k-1){
                            ++cnt;
                        }
                        else p=t;
                    }
                }
                mp[p][lst]^=1;mp[lst][p]^=1;
                vector<int> t;
                rep(j,1,k+2) if(j!=p&&j!=lst) t.pb(j);
                inv(t,0);
                mp[p][i]^=1;mp[i][p]^=1;
                t.clear();
                rep(j,1,k+2) if(j!=p&&j!=i) t.pb(j);
                inv(t,0);
                lst=0;
            }
        }
    }
    auto inv4=[&](int a,int b,int c,int d){
        mp[a][b]^=1;mp[b][c]^=1;mp[c][d]^=1;mp[d][a]^=1;
        mp[b][a]^=1;mp[c][b]^=1;mp[d][c]^=1;mp[a][d]^=1;
    };
    int lst=0;
    //delete point1
    rep(i,2,k+2) if(t[1][i]){
        if(!lst) lst=i;
        else{
            int p=2;
            while(p==lst||p==i) ++p;
            inv4(1,lst,p,i);
            t[1].flip(lst);t[lst].flip(p);t[p].flip(i);t[i].flip(1);
            t[lst].flip(1);t[p].flip(lst);t[i].flip(p);t[1].flip(i);
            lst=0;
        }
    }
    vector<int> now;
    auto ins=[&](int v){
        if(now.empty()){
            now.pb(v);
            return;
        }
        if(v==now.back()) return;
        if(now.size()==1){
            now.pb(v);
            return;
        }
        if(v==now[now.size()-2]){
            now.pop_back();
            return;
        }
        now.pb(v);
    };
    rep(i,2,k+2){
        a.clear();
        dfs(i);
        if(now.empty()){
            now=a;
        }
        else{
            a.pb(now.back());
            for(int i:a) now.pb(i);
        }
    }
    vector<int> tt;
    swap(now,tt);
    for(int i:tt) ins(i);
    int t=0;
    while(t<now.size()-1){
        inv4(1,now[t],now[t+1],now[t+2]);
        t+=2;
    }
    rep(i,1,k+2){
        rep(j,i+1,k+2){
            if(mp[i][j]){
                vector<int> v;
                rep(t,1,k+2)
                    if(t!=i&&t!=j) v.pb(t);
                invert(v);
            }
        }
    }
}