1 条题解

  • 0
    @ 2026-6-11 23:47:40

    // 欧拉路径 O(nlogn)
    #include<bits/stdc++.h>
    using namespace std;
    
    int n,du[52];
    int g[52][52];
    vector<int> path;
    vector<vector<int>> e(52); //邻接表
    int p[52]; //p[x]表示点x当前处理到第几条出边,初始值为0,相当于全局指针
    
    void dfs(int x){
      for(int i=p[x]; i<e[x].size(); i=p[x]){
        p[x]=i+1; //指向下一条边
        int y=e[x][i];
        if(g[x][y]){
          g[x][y]--; g[y][x]--; //删除正反边
          dfs(y);
        }
      }
      path.push_back(x);
    }
    int main(){
      ios::sync_with_stdio(0);cin.tie(0);
      cin>>n;
      for(int i=1,a,b;i<=n;i++){
        string s; cin>>s;
        if(s[0]>='A' && s[0]<='Z') a=s[0]-'A';
        else a=s[0]-'a'+26;
        if(s[1]>='A' && s[1]<='Z') b=s[1]-'A';
        else b=s[1]-'a'+26;
        e[a].push_back(b); 
        e[b].push_back(a); //无向边
        g[a][b]++; g[b][a]++;
        du[a]++; du[b]++;
      }
    
      for(int i=0; i<52; i++)if(!e[i].empty())
        sort(e[i].begin(),e[i].end()); //按邻接点排序
      
      int start=53,cnt=0;
      for(int i=0; i<52; i++)if(du[i]&1){ //如果度为奇数
        start=min(start,i);
        cnt++;
      }
      if(!(cnt==0||cnt==2)) //如果奇点数非0非2,则无解
        return cout<<"No Solution\n",0;
      
      if(start==53)for(int i=0; i<52; i++)
        if(du[i]){start=i; break;} //找出环的起点
        
      dfs(start);
      
      if(path.size()-1!=n) //如果不连通,则无解
        return cout<<"No Solution\n",0;
      
      reverse(path.begin(),path.end());
      for(auto i:path){
        if(i>=0 && i<26) cout<<(char)(i+'A');
        else cout<<(char)(i-26+'a');
      }
    }
    
    • 1

    信息

    ID
    12483
    时间
    1000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    50
    已通过
    16
    上传者