程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 508D Tanya and Password

Codeforces 508D Tanya and Password

編輯：C++入門知識

Codeforces 508D Tanya and Password

題意：

n（10^5）個串每個串3個字符兩個串abc、xyz能拼在一起前提是b=x&&c=y 它們能拼成ab(x)c(y)z 求n個串品在一起的串

思路：

將串abc變成ab->bc的一條邊則原題變成了有向圖的歐拉路徑問題

有向圖歐拉路徑算法就是遍歷因為歐拉路徑其實就是“每條邊走一遍”

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef unsigned long long ULL;
#define N 3850

int n,m;
int in[N],out[N],Edge[N][N],ans[200010];

int get(char a){
    if(a>='0'&&a<='9') return a-'0';
    if(a>='A'&&a<='Z') return a-'A'+10;
    return a-'a'+36;
}
char put(int a){
    if(a>=0&&a<=9) return '0'+a;
    if(a>=10&&a<=35) return 'A'+a-10;
    return 'a'+a-36;
}

void dfs(int x){
    for(int i=0;i1){
            can=0;
            break;
        }else if(tmp==1){
            if(ed==-1) ed=i;
            else{
                can=0;
                break;
            }
        }else if(tmp==-1){
            if(st==-1) st=i;
            else{
                can=0;
                break;
            }
        }
    }
    if(can){
        if(st==-1){
            for(int i=0;i=0;i--){
                if(i!=m-1) printf("%c",put(ans[i]%62));
                else printf("%c%c",put(ans[i]/62),put(ans[i]%62));
            }
            puts("");
        }else puts("NO");
    }
    else puts("NO");
    return 0;
}