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

Bingxiu2 · 2026-03-08 16:08:44 · 题解

upd 20260312 代码发下来了并调过了。本算法应该没问题。补充 AC Code 在最后。（我不会证明但是似乎几乎是卡着 \frac{n(n-1)}{2} 次操作过的）

upd 20260309 我怎么分讨漏了 k=n-2,2 \nmid k 的情况。更新了 5,13,14,15,16 的内容，并把原 5~11 平移至 6～12。略微修改 k \neq 2 且 2 \mid k 的情况。

~~这是我的赛时做法，代码还没拿到。不确定过没过。所以我也不写任何证明了。~~

~~13:44:57 调完，13:45:00 交卷，差点似，难绷。~~

怎么被 corner case 弄成 0pts 了。

我们充分发扬人类智慧，发现一些十分容易想到的基本结构：

1. C_4

考虑操作 \newcommand\w[2]{\{#1,#2,x_1,x_2,\cdots,x_{k-2}\}}\w uv,\w vw,\w wt,\w tu。

这样可以反转 (u,v),(v,w),(w,t),(t,u)。

2. K_3+K_{k-2}

考虑操作 \newcommand\w[2]{\{#1,#2,x_1,x_2,\cdots,x_{k-2}\}}\w uv,\w vw,\w wu。

这样可以反转 (u,v),(v,w),(w,u),(x_i,x_j)_{1 \le i \lt j \le k-2}。

3. K_3+K_3(k \neq n-2)

考虑用两个操作 2。

4. P_3(2 \mid k)

考虑先操作 \newcommand\w[2]{\{#1,#2,x_1,x_2,\cdots,x_{k-2}\}}\w uv,\w vw，再用 \frac{k}{2}-1 个操作 1 反转 (u,x_{2a-1}),(x_{2a-1},w),(w,x_{2a}),(x_{2a},u)。

这样可以反转 (u,v),(v,w)。

5. k \neq 3 且 k \equiv 3 \pmod 4 且 2 \nmid m 时的第零个修正

操作 \{1,2,\cdots,k\}。

然后还可以发现 2 \nmid k 的时候点的度数奇偶性无法改变，2 \mid k 的时候有以下改变度数的方法：

6. k 个点

就是题目中的操作。

7. 2 个点

考虑操作 \{u,x_1,x_2,\cdots,x_{k-1}\},\{v,x_1,x_2,\cdots,x_{k-1}\}。

这样可以改变 u,v 的奇偶性。

于是你先努力把度数与 n-1 奇偶性不同的点用操作 6、7 调掉，然后考虑以下方法集中没有连的边：

8. 仅允许两个特殊点 A,B 不连边

先固定两个点 A,B。

考虑对每条没连的边 (u,v)。

如果存在另一条没连的边 (w,u)，则使用操作 1 反转 (w,u),(u,v),(v,A),(A,w)；
否则如果存在另一条没连的边 (v,w)，则使用操作 1 反转 (u,v),(v,w),(w,A),(A,u)；
否则使用操作 1 反转 (u,v),(v,A),(A,B),(B,u)。

9. 仅允许三个特殊点 A,B,C，其中 C 可以不连边，除此以外 (A,B) 可以不连

先用操作 8，然后考虑对每个除 A,B,C 以外与 A,B 中至少一点没连的点 u。

如果 (u,A),(u,B) 都没连，使用操作 1 反转 (A,u),(u,B),(B,C),(C,A)；
否则如果 (u,A) 没连，使用操作 1 反转 (A,u),(u,C),(C,B),(B,A)；
否则使用操作 1 反转 (B,u),(u,C),(C,A),(A,B)。

10. k=3 时的修正

如果 (A,B) 没连，首先反转 (A,B),(B,C),(C,A)；
若与 C 没连边的点数 \ge 2，且 (u,C),(v,C) 没连，则反转 (u,C),(C,v),(v,u)。

11. k=2 时

不要使用以上操作，直接连起来每对没连的点 (u,v)。

12. 2 \mid k 且 k \neq 2 时的修正

如果 k \equiv 2 \pmod 4 且没连的边数为奇数，在最开始时先操作 \{1,2,\cdots,k\}；
如果 (A,B) 没连，首先用操作 4 反转 (A,B),(B,C)；
若与 C 没连边的点数 \ge 2，且 (u,C),(v,C) 没连，则用操作 4 反转 (u,C),(C,v)。

13. k \neq 3 且 2 \nmid k 时反转 (a_1,a_2),(a_2,a_3),(a_3,a_1),(a_1,a_4),(a_4,a_5),(a_5,a_1)

用两次操作 1 分别反转 (a_1,a_2),(a_2,a_4),(a_4,a_5),(a_5,a_1) 与 (a_1,a_3),(a_3,a_2),(a_2,a_4),(a_4,a_1)。

14. k \neq 3 且 2 \nmid k 时的第一个修正

如果 (u,C),(v,C),(w,C),(t,C) 没连（u,v,w,t \neq A,B），则用操作 13 反转 (C,u),(u,v),(v,C),(C,w),(w,t),(t,C)；
如果 (A,C),(B,C),(A,B) 中至少两条没连，且 (u,C),(v,C) 没连，则用操作 13 反转 (C,A),(A,B),(B,C),(C,u),(u,v),(v,C)。

15. k \equiv 1 \pmod 4 时的第二个修正

如果 (A,B),(A,C),(B,C) 没连，且 (u,C) 没连，则任选另一点 v，用操作 13 反转 (C,A),(A,B),(B,C),(C,u),(u,v),(v,C)；
如果 (A,B),(A,C),(B,C) 没连，且 (u,v) 没连，则用操作 13 反转 (C,A),(A,B),(B,C),(C,u),(u,v),(v,C)；
如果 (A,C) 没连，且 (u,C),(v,C),(w,C) 没连，则用操作 13 反转 (C,A),(A,u),(u,C),(C,v),(v,w),(w,C)；
如果 (B,C) 没连，且 (u,C),(v,C),(w,C) 没连，则用操作 13 反转 (C,B),(B,u),(u,C),(C,v),(v,w),(w,C)；
如果 (A,B),(A,C),(u,C) 没连，则用操作 1 反转 (B,A),(A,C),(C,u),(u,B)；
如果 (A,B),(B,C),(u,C) 没连，则用操作 1 反转 (A,B),(B,C),(C,u),(u,A)。

16. k \neq 3 且 k \equiv 3 \pmod 4 时的第二个修正

容易发现经过第零个、第一个修正后，边数为偶数条，且除了 (A,B) 和一端点为 C 的边外，共有偶数条边没连，于是直接使用操作 15 即可。

然后就水掉了一道黑题。

不是很难想到，我把这些都想出来耗时约 1\rm h，但是代码是真的难写，建议封装。

~~压行写了约 200 行，6\mathrm{KB}。写代码+调试耗时 1.5\rm h，差点没调完就比赛结束。~~

赛后调试最后压行写了约 350 行，10.45\mathrm{KB}。这么难写。

为什么分讨会漏一种情况呢？为什么 2 \nmid k 且 k \neq 3,n-2 会少一步呢？会挂吗？会挂吗？会挂吗？会挂吗？会挂吗？会挂吗？会挂吗？

为什么呢？为什么呢？为什么呢？为什么呢？为什么呢？

挂了。0pts。

:::info[AC 记录] AC Code:

#include <vector>
void init(int, int);
void report(int c);
void invert(std::vector<int>);

//-----------

//#include "starmap.h"
#include<bits/stdc++.h>
using namespace std;
void init(int c,int t) {
    return;
}
bool f[509][509];
int r;
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
typedef pair<int,piii> piiii;
typedef set<int> st;
typedef vector<int> vi;
//set<pii> s;
st Q;
int K,N;
struct ANS{
    set<piiii> r;
    inline void f(int a,int b,int c,int d){
        if(c>K+1) c=0;
        if(d>K+1) d=0;
        if(c>d) swap(c,d);
        if(c==K+1) c=0;
        else if(c==0&&d==K+1) d=0;
        if(a<=K) a=0;
        if(b<=K) b=0;
        if(a>b) swap(a,b);
        if(d==K+1){
            if(!c||b>=K+2) d=0,swap(c,d);
        }
        if(d==K){
            if((!c&&b>=K+1)||a>=K+1) d=0,swap(c,d);
        }
        piiii z=(piiii){a,(piii){b,(pii){c,d}}};
        if(r.find(z)==r.end()) r.insert(z);
        else r.erase(z);
    }
}e;
struct ANS2{
    set<vi> r;
    inline void f(st &o){
        vi V;
        for(int i:o) V.push_back(i);
        if(r.find(V)==r.end()) r.insert(V);
        else r.erase(V);
    }
}e2;
int ot[509];
st W;
st o,z[509];
vector<int> V,B;
inline void upd(int u,int v){
    if(u>v) swap(u,v);
    if(f[u][v]){
        f[u][v]=0,f[v][u]=0;
        if(u>3) /*s.insert((pii){u,v}),*/z[u].insert(v),z[v].insert(u);
        --r;
    }
    else{
        f[u][v]=1,f[v][u]=1;
        if(u>3) /*s.erase((pii){u,v}),*/z[u].erase(v),z[v].erase(u);
        ++r;
    }
}
inline void upd2(vector<int> P){
    o.clear();
    for(int i=0;i<P.size();++i) o.insert(P[i]);
    e2.f(o);
    for(int i=0;i+1<P.size();++i) for(int j=i+1;j<P.size();++j) upd(P[i],P[j]);
}
inline void g(int u,int w,int v,int t,bool up=1){
    //o.clear();
    //for(int i=1,j=0;j<K-2;++i) if(i!=u&&i!=w&&i!=v&&i!=t) o.insert(i),++j;
    //o.insert(u),o.insert(w);
    e.f(u,w,v,t);//cout<<o.size()<<" abcd\n";//{u,w}
    //o.erase(u),o.insert(v);
    e.f(w,v,u,t);//cout<<o.size()<<" efgh\n";//{w,v}
    //o.erase(w),o.insert(t);
    e.f(v,t,u,w);//cout<<o.size()<<" ijkl\n";//{v,t}
    //o.erase(v),o.insert(u);
    e.f(t,u,v,w);//cout<<o.size()<<" mnop\n";//{t,u}
    if(up) upd(u,w),upd(w,v),upd(v,t),upd(t,u);
}
inline void upd3(int u,int v,int w){
    st O;
    O.clear();
    for(int i=1,j=0;j<K-2;++i) if(i!=u&&i!=v&&i!=w) O.insert(i),++j;
    O.insert(u),O.insert(v);
    e2.f(O),upd(u,v);//{u,v}
    O.erase(u),O.insert(w);
    e2.f(O),upd(v,w);//{v,w}
    O.erase(v),O.erase(w);
    while(!O.empty()){
        int x=*O.begin();
        O.erase(x);
        int y=*O.begin();
        O.erase(y);
        g(u,x,w,y,0);
    }
}
/*inline void upd4(int u,int v,int u2,int v2){
    o.clear();
    for(int i=1,j=0;j<K-2;++i) if(i!=u&&i!=v&&i!=u2&&i!=v2&&i!=3) o.insert(i),++j;
    //o.insert(3),o.insert(u);
    e.f(o,3,u),upd(3,u);//{3,u}
    //o.erase(3),o.insert(v);
    e.f(o,u,v),upd(u,v);//{u,v}
    //o.erase(u),o.insert(3);
    e.f(o,3,v),upd(3,v);//{3,v}
    //o.erase(v),o.insert(u2);
    e.f(o,3,u2),upd(3,u2);//{3,u2}
    //o.erase(3),o.insert(v2);
    e.f(o,u2,v2),upd(u2,v2);//{u2,v2}
    //o.erase(u2),o.insert(3);
    e.f(o,v2,3),upd(v2,3);//{3,v2}
}*/
inline void upd5(int u,int v,int w,int x,int y){
//if(u==v||u==w||u==x||u==y||v==w||v==x||v==y||w==x||w==y||x==y) cout<<"asdfghjkl "<<u<<" "<<v<<" "<<w<<" "<<x<<" "<<y<<"\n";
    g(u,v,x,y),g(u,w,v,x);
}
void starmap(int n,int m,int k,int p,vector<int> u,vector<int> v) {
    N=n;
    if(k==2){
        memset(f,0,sizeof(f));
        for(int i=0;i<m;++i) f[u[i]][v[i]]=f[v[i]][u[i]]=1;
        report(n*(n-1)/2);
        for(int i=1;i<n;++i) for(int j=i+1;j<=n;++j) if(!f[i][j]) V.clear(),V.push_back(i),V.push_back(j),invert(V);
        return;
    }
    memset(f,0,sizeof(f)),K=k,memset(ot,0,sizeof(ot));
    for(int i=0;i<m;++i) if(u[i]>v[i]) swap(u[i],v[i]);
    for(int i=1;i<=n;++i) ot[i]=n-1;
    for(int i=0;i<m;++i) f[u[i]][v[i]]=f[v[i]][u[i]]=1,--ot[u[i]],--ot[v[i]];
    /*s.clear(),*/e.r.clear(),e2.r.clear(),r=m;
    for(int i=1;i<=n;++i) z[i].clear();
    for(int i=4;i<n;++i) for(int j=i+1;j<=n;++j) if(!f[i][j]) /*s.insert((pii){i,j}),*/z[i].insert(j),z[j].insert(i);
    if(k%2==0){
        if(k%4==2&&(n*(n-1)/2-m)%2==1){V.clear();for(int i=1;i<=k;++i) V.push_back(i);upd2(V);}
        /*Q.clear();
        for(int i=1;i<=n;++i) if(ot[i]&1) Q.insert(i);
        while(Q.size()>=k){
            V.clear();
            for(int i=0;i<k;++i) V.push_back(*Q.begin()),Q.erase(Q.begin());
            upd2(V);
        }
        while(Q.size()>=2){
            V.clear(),B.clear();
            int u=*Q.begin();
            Q.erase(u);
            int v=*Q.begin();
            Q.erase(v);
            for(int i=1,j=0;i<=n,j<k-1;++i) if(i!=u&&i!=v) V.push_back(i),B.push_back(i),++j;
            V.push_back(u),B.push_back(v);
            upd2(V),upd2(B);
        }*/
    }
    int _A=0;
    for(int i=1;i<=n;++i) if(ot[i]&1) ++_A;
    if(k%4==3&&(n*(n-1)/2-m-_A/2)%2==1){V.clear();for(int i=1;i<=k;++i) V.push_back(i);upd2(V);}
//for(int i=1;i<=n;++i) ot[i]=n-1;
//for(int i=0;i<m;++i) --ot[u[i]],--ot[v[i]];
//for(int i=1;i<=n;++i) if(ot[i]&1) cout<<i<<" ";cout<<" aaa\n";
    for(int i=4;i<=n;++i){
        while(z[i].size()>1){
            set<int>::iterator p=z[i].begin();
            int u=*p;
            ++p;
            int v=*p;
            g(u,i,v,1);
        }
        if(z[i].size()==1){
            int u=*z[i].begin();
            int v=1,k=2;
            if(z[u].size()>=2){
                set<int>::iterator p=z[u].begin();
                if(*p==i) ++p;
                v=*p,k=1;
            }
            g(i,u,v,k);
        }
    }
    for(int i=4;i<=n;++i){
        if(!f[1][i]&&!f[2][i]) g(1,i,2,3);
        else if(!f[1][i]) g(2,1,i,3);
        else if(!f[2][i]) g(1,2,i,3);
    }
    if(k==3&&((f[1][2]&&f[2][3])||(f[2][3]&&f[1][3])||(f[1][2]&&f[1][3]))) o.clear(),o.insert(1),o.insert(2),o.insert(3),e2.f(o),upd(1,2),upd(2,3),upd(1,3);
    W.clear();
    for(int i=1;i<=n;++i) if(i!=3&&!f[i][3]) W.insert(i);
    if(k==3){
        if(!f[1][2]){
            f[1][3]?(W.insert(1),0):(W.erase(1),0),f[2][3]?(W.insert(2),0):(W.erase(2),0);
            o.clear(),o.insert(1),o.insert(2),o.insert(3),e2.f(o),upd(1,2),upd(1,3),upd(2,3);
        }
        while(W.size()>=2){
            int u=*W.begin();
            W.erase(u);
            int v=*W.begin();
            W.erase(v);
            o.clear(),o.insert(u),o.insert(v),o.insert(3),e2.f(o),upd(u,v),upd(v,3),upd(3,u);
        }
    }
    else if(k%2==0){
        if(!f[1][2]) f[2][3]?(W.insert(2),0):(W.erase(2),0),upd3(1,2,3);
        while(W.size()>=2){
            int u=*W.begin();
            W.erase(u);
            int v=*W.begin();
            W.erase(v);
            upd3(u,3,v);
        }
    }
    else{
        /*if(!f[1][2]&&!f[1][3]&&W.size()>=2&&(W.size()>=3||f[2][3])){
            set<int>::iterator p=W.begin();
            while(*p==1||*p==2) ++p;
            int u=*p;
            g(2,1,3,u),W.erase(1),W.erase(u);
        }
        if(!f[2][3]&&!f[1][2]&&W.size()>=2&&(W.size()>=3||f[1][3])){
            set<int>::iterator p=W.begin();
            while(*p==1||*p==2) ++p;
            int u=*p;
            g(1,2,3,u),W.erase(2),W.erase(u);
        }
        if(k!=n-2) while(W.size()>=4){
            int u=*W.begin();
            W.erase(u);
            int v=*W.begin();
            W.erase(v);
            int u2=*W.begin();
            W.erase(u2);
            int v2=*W.begin();
            W.erase(v2);
            upd4(u,v,u2,v2);
        }*/
        W.erase(1),W.erase(2);
        stack<pii> S;
        while(W.size()>=4){
            int u=*W.begin();
            W.erase(u);
            int v=*W.begin();
            W.erase(v);
            int u2=*W.begin();
            W.erase(u2);
            int v2=*W.begin();
            W.erase(v2);
            upd5(3,u,v,u2,v2),S.push((pii){u,v}),S.push((pii){u2,v2});
        }
        if((int)!f[1][2]+(int)!f[1][3]+(int)!f[2][3]>=2&&W.size()>=2){
            int u=*W.begin();
            W.erase(u);
            int v=*W.begin();
            W.erase(v);
            upd5(3,1,2,u,v);
        }
        if(!f[1][2]&&!f[1][3]&&!f[2][3]&&W.size()>=1){
            int u=*W.begin();
            W.erase(u);
            int v=4;
            while(v==u) ++v;
            W.insert(v);
            upd5(3,1,2,u,v);
        }
        if(!f[1][2]&&!f[1][3]&&!f[2][3]&&!S.empty()){
            int u=S.top().first,v=S.top().second;
            S.pop(),W.insert(u),W.insert(v);
            upd5(3,1,2,u,v);
        }
        if(!f[1][3]&&W.size()>=3){
            int u=*W.begin();
            W.erase(u);
            int v=*W.begin();
            W.erase(v);
            int u2=*W.begin();
            W.erase(u2);
            upd5(3,1,u,v,u2),S.push((pii){v,u2});
        }
        if(!f[2][3]&&W.size()>=3){
            int u=*W.begin();
            W.erase(u);
            int v=*W.begin();
            W.erase(v);
            int u2=*W.begin();
            W.erase(u2);
            upd5(3,2,u,v,u2),S.push((pii){v,u2});
        }
        if(!f[1][2]&&!f[1][3]&&W.size()>=1){
            int u=*W.begin();
            W.erase(u);
            g(2,1,3,u);
        }
        if(!f[1][2]&&!f[2][3]&&W.size()>=1){
            int u=*W.begin();
            W.erase(u);
            g(1,2,3,u);
        }
        if(!f[1][2]&&!f[1][3]){
            int u=0;
            for(int i=4;i<=n;++i) if(!f[2][i]){u=i;break;}
            if(u) g(3,1,2,u);
        }
        if(!f[1][2]&&!f[2][3]){
            int u=0;
            for(int i=4;i<=n;++i) if(!f[1][i]){u=i;break;}
            if(u) g(3,2,1,u);
        }
        if(!f[1][3]&&!f[2][3]){
            int u=0;
            for(int i=4;i<=n;++i) if(!f[1][i]||!f[2][i]){u=i;break;}
            if(u) g(1,3,2,u);
        }
    }//for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if(!f[i][j]) cout<<i<<" "<<j<<"\n";cout<<r<<" WWW\n";
//cout<<e.r.size()<<" "<<e2.r.size()<<" "<<n<<" "<<p<<"\n";
    report(r);
    for(set<piiii>::iterator i=e.r.begin();i!=e.r.end();++i){
        V.clear();
        int a=(*i).first,b=(*i).second.first,c=(*i).second.second.first,d=(*i).second.second.second;
        if(a!=0){
            for(int j=1,z=0;z<k-2;++j) if(j!=a&&j!=b&&j!=c&&j!=d) ++z,V.push_back(j);
            V.push_back(a),V.push_back(b);
        }
        else if(b!=0){
            for(int j=1,z=0;z<k-1;++j) if(j!=b&&j!=c&&j!=d) ++z,V.push_back(j);
            V.push_back(b);
        }
        else{
            for(int j=1,z=0;z<k;++j) if(j!=c&&j!=d) ++z,V.push_back(j);
        }
        invert(V);
    }
    for(set<vi>::iterator i=e2.r.begin();i!=e2.r.end();++i) invert(*i);
}
/*
153
152
153
153
144
147
147
147
150
148
*/

:::

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