题解归档 - cf2225G

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2225G
• 本地来源：problems/cf2225G/idea.md
• 题目链接：https://codeforces.com/contest/2225/problem/G
• 原始标题：cf2225G - Simple Problem

思路

cf2225G - Simple Problem

Pattern

View numbers as vertices. An edge is allowed when the absolute difference is
divisible by at least one k_i. The goal is to output a Hamilton path or prove
none exists.

Necessary

Let g = gcd(k_1, ..., k_m). Every allowed adjacent difference is divisible by
g, so every edge preserves the residue modulo g. If g > 1, the graph has
multiple residue components and cannot contain a path through all 0..n-1.

Construction When g = 1

Let a = min(k_i). Inside each residue class modulo a, consecutive numbers
differ by a, so they are connected because a is one of the allowed divisors.

It remains to order the residue classes modulo a and connect neighboring
classes. Build a graph on residues where two residues are adjacent if they can
differ by one of the k_i modulo a. Since g=1, this residue graph is
connected. The implementation finds a Hamilton path in this small circulant
residue graph:

• if some step is coprime with a, use the simple arithmetic progression;
• otherwise use local Posa-style rotations on the residue graph.

For each adjacent pair of residue classes in that residue path, choose one
outgoing number from the current class and one entry number in the next class
whose difference is exactly some k_i. Since a <= n/3, each residue class
has enough elements to avoid the already reserved entry and still keep the
inside-class chain.

Checks

• python tools/run_exe.py cf2225G produced a valid sample output.
• python tools/stress2.py cf2225G -n 1000 --keep-fail passed against brute
  for small cases.
• 80 additional checker-only random batches with total n<=5000 per batch
  passed; these included large residue graphs and both possible/impossible
  cases.

Risk

The residue Hamilton path finder uses bounded local search for the connected
circulant case where no single generator is coprime with a. It passed local
brute/checker validation, but this part is less direct than the rest of the
construction.

代码

来源：problems/cf2225G/solution.cpp

#include<bits/stdc++.h>
using namespace std;

bool okEdge(int a,int b,const vector<int>&ks){
    int d=abs(a-b);
    for(int k:ks) if(d%k==0) return true;
    return false;
}

vector<int> residuePath(int n,const vector<int>&ks){
    if(n==1) return {0};
    vector<int> steps;
    for(int k:ks){
        int s=k%n;
        if(s&&find(steps.begin(),steps.end(),s)==steps.end()) steps.push_back(s);
    }
    for(int s:steps){
        if(gcd(n,s)==1){
            vector<int> p(n);
            for(int i=0;i<n;i++) p[i]=(long long)i*s%n;
            return p;
        }
    }
    vector<vector<unsigned char>> adj(n,vector<unsigned char>(n,0));
    vector<vector<int>> nei(n);
    auto addEdge=[&](int u,int v){
        if(u==v||adj[u][v]) return;
        adj[u][v]=adj[v][u]=1;
        nei[u].push_back(v);
        nei[v].push_back(u);
    };
    for(int i=0;i<n;i++){
        for(int s:steps){
            addEdge(i,(i+s)%n);
            addEdge(i,(i-s+n)%n);
        }
    }
    for(int seed=0;seed<240;seed++){
        mt19937 rng(712367u+seed*1000003u+n*9176u+steps.size()*37u);
        vector<char> used(n,0);
        vector<int> path;
        int st=rng()%n;
        path.push_back(st);
        used[st]=1;
        int usedCnt=1,fail=0;
        while(usedCnt<n&&fail<80*n){
            int e=path.back();
            vector<int> cand;
            for(int v:nei[e]) if(!used[v]) cand.push_back(v);
            if(!cand.empty()){
                int choose=0;
                if(seed%3==0){
                    int best=INT_MAX;
                    for(int i=0;i<(int)cand.size();i++){
                        int deg=0;
                        for(int y:nei[cand[i]]) if(!used[y]) deg++;
                        if(deg<best){
                            best=deg;
                            choose=i;
                        }
                    }
                }else choose=rng()%cand.size();
                int v=cand[choose];
                path.push_back(v);
                used[v]=1;
                usedCnt++;
                fail=0;
                continue;
            }
            vector<int> ord(path.size()-1);
            iota(ord.begin(),ord.end(),0);
            if(seed%2) shuffle(ord.begin(),ord.end(),rng);
            bool found=false;
            for(int id:ord){
                if(adj[e][path[id]]){
                    int ne=path[id+1];
                    bool can=false;
                    for(int v:nei[ne]) if(!used[v]){
                        can=true;
                        break;
                    }
                    if(can){
                        reverse(path.begin()+id+1,path.end());
                        found=true;
                        break;
                    }
                }
            }
            if(found){
                fail++;
                continue;
            }
            vector<int> rot;
            for(int id:ord) if(adj[e][path[id]]) rot.push_back(id);
            if(rot.empty()) break;
            int id=rot[rng()%rot.size()];
            reverse(path.begin()+id+1,path.end());
            fail++;
        }
        if(usedCnt==n){
            bool good=true;
            for(int i=0;i+1<n;i++) if(!adj[path[i]][path[i+1]]) good=false;
            if(good) return path;
        }
    }
    return {};
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        vector<int> ks(m);
        int g=0;
        for(int&i:ks){
            cin>>i;
            g=gcd(g,i);
        }
        if(g!=1){
            cout<<"-1\n";
            continue;
        }
        int a=*min_element(ks.begin(),ks.end());
        if(a==1){
            for(int i=0;i<n;i++) cout<<i<<(i+1==n?'\n':' ');
            continue;
        }
        vector<int> rp=residuePath(a,ks);
        if((int)rp.size()!=a){
            cout<<"-1\n";
            continue;
        }
        vector<vector<int>> cls(a);
        for(int i=0;i<n;i++) cls[i%a].push_back(i);
        vector<int> entry(a,-1),ans;
        bool fail=false;
        for(int idx=0;idx<a;idx++){
            int r=rp[idx];
            int ent=entry[r];
            int out=-1,in=-1;
            if(idx+1<a){
                int s=rp[idx+1];
                for(int v:cls[r]){
                    if(v==ent) continue;
                    for(int k:ks){
                        int y=v+k;
                        if(y<n&&y%a==s){
                            out=v;
                            in=y;
                            break;
                        }
                        y=v-k;
                        if(y>=0&&y%a==s){
                            out=v;
                            in=y;
                            break;
                        }
                    }
                    if(out!=-1) break;
                }
                if(out==-1){
                    fail=true;
                    break;
                }
                entry[s]=in;
            }
            if(ent!=-1) ans.push_back(ent);
            for(int v:cls[r]) if(v!=ent&&v!=out) ans.push_back(v);
            if(out!=-1) ans.push_back(out);
        }
        if(fail||(int)ans.size()!=n){
            cout<<"-1\n";
            continue;
        }
        vector<int> seen(n,0);
        for(int v:ans) if(v<0||v>=n||seen[v]++) fail=true;
        for(int i=0;i+1<n;i++) if(!okEdge(ans[i],ans[i+1],ks)) fail=true;
        if(fail){
            cout<<"-1\n";
            continue;
        }
        for(int i=0;i<n;i++) cout<<ans[i]<<(i+1==n?'\n':' ');
    }
    return 0;
}