题解：P17244 [IOI 2026] 魔幻之城 / Magic City

· · 题解

vp 时想到一个简单的 K 为偶数时 12K 为奇数时 13K+O(1) 的做法，由于分很高就没继续做了。赛后发现为奇数的构造一个地方没去重，去重之后就是 12K+O(1)，再卡卡常就过了。

首先观察到当点集很小时直接构造完全图就对了，考虑利用两次分治减小点集。

不难注意到将点集合先分成 L,R 两个部分再分成 L_1,L_2,R_1,R_2 四个部分，当 K 为偶数时这些部分等大小，先构造 (L_1+L_2),(R_1+R_2) 的完全二分图，再构造 (L_1,L_2),(R_1,R_2),(L_1,R_1),(L_2,R_2) 的四组完全二分图（共用点集）和 (L_1,L_2),(R_1,R_2),(L_1,R_2),(L_2,R_1) 的四组完全二分图（共用点集）。随后再构造 (L_1+L_2),(L_1+R_1),(L_1+R_2),(L_2+R_1),(L_2+R_2),(R_1+R_2) 的六组完全图即可。刚好 12K 个点。

当 K 为奇数时会构造出度数为 K+1 的点，怎么办？考虑在构造四组完全二分图时把 R_2 中的 2K-1 取出，在构造六组完全图时在 R_1 中加入 2K-1，最后额外构造一个 L_1+L_2+\{2K-1\} 的完全图即可。这是我 vp 时的做法，需要 13K+O(1) 个点。

注意到最后这个完全图和前面 (L_1+L_2) 的完全图重复了，把前面那个丢掉直接做到 12K+O(1)，对前面卡卡点数（在构造六组完全图时给点颜色去重，以及一开始构造完全二分图时也可以把 2K-1 从 R_2 中去掉）即可卡到恰好 12K 个点。

前面小点懒得拼了。

前面小点还不好拼，考虑退火，显然每种颜色的点数应该一样且所有点度数都是 K，我们先随机染色然后加入交换两点颜色以及将边 (u,v),(x,y) 变成 (u,x),(v,y)。这个可以把 K=3,4 跑出来。至于 K=5 还需要手法，我们加入两个操作：找一个环 L 打乱环上点排列顺序和对于一个缺失的 (a,b,c) 我们找到一个颜色为 b 且邻域缺失 a 颜色或者缺失 c 颜色的点直接用一次 (u,v),(x,y) 变成 (u,x),(v,y) 的调整将其调出来。这样就可以跑出 K=5 了。

#include<bits/stdc++.h>
using namespace std;
std::pair<std::vector<int>, std::vector<std::pair<int, int>>> construct(int K) {
    if(K==1){
        return {{0,1},{{0,1}}};
    }else if(K==2){
        return {{0,1,2,3,0,1,2,3,0,1,2,3},{{0,1},{1,3},{3,2},{2,0},{4,5},{5,6},{6,7},{7,4},{8,10},{8,11},{9,10},{9,11}}};
    }else if(K==3){
        return {{5,5,0,1,2,4,1,0,3,0,4,2,3,5,5,4,3,0,2,1,1,4,2,3},{{0,15},{0,20},{0,7},{1,21},{1,16},{1,11},{2,14},{2,18},{2,12},{3,13},{3,23},{3,15},{4,14},{4,19},{4,16},{5,8},{5,9},{5,22},{6,12},{6,11},{6,9},{7,19},{7,10},{8,13},{8,17},{9,11},{10,16},{10,19},{12,18},{13,22},{14,23},{15,18},{17,20},{17,21},{20,22},{21,23}}};
    }else if(K==4){
        return {{7,6,1,4,2,3,5,3,6,6,1,6,5,1,0,5,1,4,4,5,4,2,3,5,0,2,0,2,7,3,3,2,7,7,1,6,0,0,4,7},{{0,22},{0,19},{0,20},{0,10},{1,37},{1,32},{1,15},{1,16},{2,24},{2,19},{2,9},{2,4},{3,11},{3,4},{3,39},{3,26},{4,11},{4,15},{5,26},{5,33},{5,8},{5,19},{6,20},{6,16},{6,9},{6,14},{7,21},{7,35},{7,23},{7,18},{8,13},{8,25},{8,12},{9,17},{9,28},{10,36},{10,15},{10,27},{11,39},{11,30},{12,24},{12,31},{12,30},{13,29},{13,38},{13,28},{14,35},{14,34},{14,27},{15,33},{16,17},{16,22},{17,33},{17,22},{18,34},{18,27},{18,37},{19,26},{20,31},{20,30},{21,39},{21,35},{21,24},{22,37},{23,32},{23,38},{23,25},{24,28},{25,32},{25,36},{26,33},{27,28},{29,36},{29,31},{29,39},{30,34},{31,34},{32,37},{35,38},{36,38}}};
    }else if(K==5){
        return {{7,3,0,6,9,4,2,1,1,8,9,5,4,3,9,0,1,4,4,9,0,2,8,3,5,6,7,6,1,5,2,3,4,7,5,8,8,7,0,3,2,9,6,6,8,0,7,5,2,1},{{0,13},{0,14},{0,20},{0,22},{0,28},{1,10},{1,11},{1,18},{1,22},{1,30},{2,5},{2,19},{2,21},{2,42},{2,46},{3,17},{3,29},{3,33},{3,48},{3,49},{4,6},{4,12},{4,15},{4,27},{4,36},{5,8},{5,21},{5,31},{5,34},{6,8},{6,20},{6,23},{6,24},{7,12},{7,20},{7,25},{7,40},{7,47},{8,19},{8,31},{8,34},{9,11},{9,18},{9,20},{9,23},{9,28},{10,17},{10,24},{10,28},{10,46},{11,12},{11,16},{11,21},{12,15},{12,37},{13,14},{13,40},{13,42},{13,44},{14,22},{14,34},{14,38},{15,27},{15,36},{15,49},{16,26},{16,30},{16,32},{16,44},{17,36},{17,39},{17,40},{18,25},{18,46},{18,48},{19,30},{19,35},{19,43},{20,47},{21,35},{21,37},{22,34},{22,49},{23,41},{23,45},{23,49},{24,25},{24,39},{24,46},{25,36},{25,37},{26,41},{26,43},{26,45},{26,48},{27,30},{27,31},{27,44},{28,42},{28,45},{29,31},{29,38},{29,41},{29,48},{30,44},{31,33},{32,35},{32,38},{32,42},{32,47},{33,35},{33,40},{33,47},{34,43},{35,45},{36,37},{37,39},{38,39},{38,43},{39,43},{40,41},{41,42},{44,47},{45,48},{46,49}}};
    }
    std::vector<int> T;
    std::vector<std::pair<int, int>> E;
    vector<int> L,R;
    for(int i=0;i<K;i++){
        T.push_back(i);
    }
    for(int i=K;i<2*K;i++){
        if((K&1)&&i==2*K-1) continue;
        T.push_back(i);
    }
    for(int i=0;i<K;i++){
        for(int j=K;j<2*K;j++){
            if((K&1)&&j==2*K-1) continue;
            E.push_back({i,j});
        }
    }
    vector<int> L1,L2,R1,R2;
    for(int i=0;i<K;i++){
        T.push_back(i);
        if(i<K/2) L1.push_back(T.size()-1);
        else L2.push_back(T.size()-1);
    }
    for(int i=K;i<2*K;i++){
        if((K&1)&&i==2*K-1) continue;
        T.push_back(i);
        if(i-K<K/2) R1.push_back(T.size()-1);
        else R2.push_back(T.size()-1);
    }
    for(int x:L1){
        for(int y:L2) E.push_back({x,y});
    }
    for(int x:R1){
        for(int y:R2) E.push_back({x,y});
    }
    for(int x:L1){
        for(int y:R1) E.push_back({x,y});
    }
    for(int x:L2){
        for(int y:R2) E.push_back({x,y});
    }
    L1.clear(),L2.clear(),R1.clear(),R2.clear();
    for(int i=0;i<K;i++){
        T.push_back(i);
        if(i<K/2) L1.push_back(T.size()-1);
        else L2.push_back(T.size()-1);
    }
    for(int i=K;i<2*K;i++){
        if((K&1)&&i==2*K-1) continue;
        T.push_back(i);
        if(i-K<K/2) R1.push_back(T.size()-1);
        else R2.push_back(T.size()-1);
    }
    for(int x:L1){
        for(int y:L2) E.push_back({x,y});
    }
    for(int x:R1){
        for(int y:R2) E.push_back({x,y});
    }
    for(int x:L1){
        for(int y:R2) E.push_back({x,y});
    }
    for(int x:L2){
        for(int y:R1) E.push_back({x,y});
    }
    L1.clear(),L2.clear(),R1.clear(),R2.clear();
    vector<int> col[4];
    for(int i=0;i<K;i++){
        if(i<K/2) col[0].push_back(i);
        else col[1].push_back(i);
    }
    for(int i=K;i<2*K;i++){
        if(i-K<K/2) col[2].push_back(i);
        else col[3].push_back(i);
    }
    if(K&1) col[2].push_back(2*K-1);
    for(int i=0;i<4;i++){
        for(int j=0;j<i;j++){
            vector<int> vec;
            if((K&1)&&i==1&&j==0) continue;
            for(int x:col[i]){
                T.push_back(x);
                vec.push_back(T.size()-1);
            }
            for(int x:col[j]){
                if(i==3&&j==2&&x==2*K-1) continue;
                T.push_back(x);
                vec.push_back(T.size()-1);
            }
            for(int x=0;x<(int)vec.size();x++){
                for(int y=0;y<x;y++) E.push_back({vec[x],vec[y]});
            }
        }
    }
    if(K&1){
        vector<int> vec;
        for(int i=0;i<K;i++){
            T.push_back(i);
            vec.push_back(T.size()-1);
        }
        T.push_back(2*K-1);
        vec.push_back(T.size()-1);
        for(int i=0;i<(int)vec.size();i++){
            for(int j=0;j<i;j++) E.push_back({vec[i],vec[j]});
        }
        vec.clear();
    }
    return {T, E};
}