Chengrui's Blog

0%

发表于 分类于 ， Disqus：

输入国家的个数，建造大楼使的每两个国家都有办公室相连。

例题书上给了很巧妙的思路，建造两层的n*n的大楼，第一层的第i行的都是国家i，第二层的第j列都是国家j。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
#include<map>
using namespace std;
map<int,char> c;
int main(){
    for(int i=0;i<26;++i)
        c[i]='A'+i;
    for(int i=26;i<52;++i)
        c[i]='a'+i-26;
    int n;
    while(~scanf("%d",&n)){
        printf("2 %d %d\n",n,n);
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j)
                printf("%c",c[i]);
            printf("\n");
        }
        printf("\n");
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j)
                printf("%c",c[j]);
            printf("\n");
        }
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出n个点，m条边的无向图，每条边有一种颜色，求从结点1到结点n颜色字典序最小的最短路径。

例题，书上给了思路，首先反向BFS，记录结点到n最短距离，然后从起点BFS，每次优先选择字典序最小的颜色的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100010;
const int inf=1<<30;
int n,vis[maxn],d[maxn];
vector<int> g[maxn],ans;
struct way{
    int u,v,c;
    way(int u=0,int v=0,int c=0):u(u),v(v),c(c){}
};
vector<way> ways;
void build(int u,int v,int c){//储存边。
    ways.push_back(way(u,v,c));
    int i=(int)ways.size()-1;
    g[u].push_back(i);
}
void rev_bfs(){//反向BFS，记录距离。
    memset(vis,0,sizeof(vis));
    d[n-1]=0;
    vis[n-1]=true;
    queue<int> q;
    q.push(n-1);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int i=0;i<g[v].size();++i){
            int e=g[v][i];
            int u=ways[e].v;
            if(!vis[u]){
                vis[u]=true;
                d[u]=d[v]+1;
                q.push(u);
            }
        }
    }
}
void bfs(){
    memset(vis,0,sizeof(vis));
    ans.clear();
    vis[0]=true;
    vector<int> next;
    next.push_back(0);
    for(int i=0;i<d[0];++i){
        int min_color=inf;
        for(int j=0;j<next.size();++j){
            int u=next[j];
            for(int k=0;k<g[u].size();++k){
                int e=g[u][k];
                int v=ways[e].v;
                if(d[u]==d[v]+1)
                    min_color=min(min_color,ways[e].c);
            }
        }
        ans.push_back(min_color);
        vector<int> next2;
        for(int j=0;j<next.size();++j){
            int u=next[j];
            for(int k=0;k<g[u].size();++k){
                int e=g[u][k];
                int v=ways[e].v;
                if(d[u]==d[v]+1&&!vis[v]&&ways[e].c==min_color){
                    vis[v]=true;
                    next2.push_back(v);
                }
            }
        }
        next=next2;
    }
    printf("%d\n",(int)ans.size());
    for(int i=0;i<ans.size();++i){
        if(i) printf(" ");
        printf("%d",ans[i]);
    }
    printf("\n");
}
int main(){
    int u,v,c,m;
    while(~scanf("%d%d",&n,&m)){
        ways.size();
        for(int i=0;i<n;++i)
            g[i].clear();
        while(m--){
            scanf("%d%d%d",&u,&v,&c);
            build(u-1,v-1,c);
            build(v-1,u-1,c);
        }
        rev_bfs();
        bfs();
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

输入n种边上带标号的正方形，特定标号可以相连，判断能否铺成无限大的结构。

书上的例题，给出了思路。将标号转化为点，将正方形看作边，得到有向图，对其进行拓扑排序，判断是否形成环即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=52;
int c[maxn];
bool g[maxn][maxn];
int id(char a1,char a2){//给每个标号分配id。
    return (a1-'A')*2+(a2=='+'?0:1);
}
void connect(char a1,char a2,char b1,char b2){//将输入的正方形和标号转化为有向图。
    if(a1=='0'||b1=='0') return;
    int u=id(a1,a2)^1,v=id(b1,b2);
    g[u][v]=true;
}
bool toposort(int u){//拓扑排序。
    c[u]=-1;
    for(int v=0;v<maxn;++v)
        if(g[u][v]){
            if(c[v]<0) return true;
            else if(!c[v]&&toposort(v)) return true;
        }
    c[u]=1;
    return false;
}
bool cycle(){
    memset(c,0,sizeof(c));
    for(int i=0;i<maxn;++i)
        if(!c[i]) if(toposort(i)) return true;
    return false;
}
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        memset(g,0,sizeof(g));
        while(n--){
            char s[10];
            scanf("%s",s);
            for(int i=0;i<4;++i)
                for(int j=0;j<4;++j)
                    if(i!=j) connect(s[i*2],s[i*2+1],s[j*2],s[j*2+1]);
        }
        printf("%s\n",cycle()?"unbounded":"bounded");//形成环不可拼出无限大。
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

模拟执行各种指令，很久之前的一道例题，书上给出了思路。

使用双端队列储存程序，根据相应的指令对队列进行调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
using namespace std;
const int maxn=1010;
bool locked;
char pro[maxn][10];
int n,tq,c[5],var[26],ip[maxn];
deque<int> ready;
queue<int> block;
void run(int pid){
    int q=tq;
    while(q>0){
        char *p=pro[ip[pid]];
        switch(p[2]){
            case '=':
                var[p[0]-'a']=isdigit(p[5])?(p[4]-'0')*10+p[5]-'0':p[4]-'0';
                q-=c[0];
                break;
            case 'i':
                printf("%d: %d\n",pid+1,var[p[6]-'a']);
                q-=c[1];
                break;
            case 'c':
                if(locked){block.push(pid);return;}
                locked=true;
                q-=c[2];
                break;
            case 'l':
                locked=false;
                if(!block.empty()){
                    int pid2=block.front();
                    block.pop();
                    ready.push_front(pid2);
                }
                q-=c[3];
                break;
            case 'd':
                return;
        }
        ++ip[pid];
    }
    ready.push_back(pid);
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d%d%d%d\n",&n,&c[0],&c[1],&c[2],&c[3],&c[4],&tq);
        memset(var,0,sizeof(var));
        int line=0;
        for(int i=0;i<n;++i){
            fgets(pro[line++],maxn,stdin);
            ip[i]=line-1;
            while(pro[line-1][2]!='d')
                fgets(pro[line++],maxn,stdin);
            ready.push_back(i);
        }
        locked=false;
        while(!ready.empty()){
            int pid=ready.front();
            ready.pop_front();
            run(pid);
        }
        if(t) printf("\n");
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出一个真分数，把它分解成最少的埃及分数的和。同时给出了k个数，不能作为分母出现，要求解的最小的分数的分母尽量大。

使用IDA*算法解决，在例题求埃及分数的基础上，加上禁用限制就可以了，一开始禁用限制没加好，一直WA。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
typedef long long LL;
const int maxn=10010;
int maxd,t,tt;
set<LL> sk;
LL ans[maxn],v[maxn];
LL gcd(LL a,LL b){
    return b?gcd(b,a%b):a;
}
LL get_first(LL a,LL b){
    return b/a+1;
}
bool better(int d){
    for(int i=d;i>=0;--i)
        if(v[i]!=ans[i]) return ans[i]==-1||v[i]<ans[i];
    return false;
}
bool dfs(int d,LL from,LL a,LL b){
    if(d==maxd){
        if(b%a) return false;
        v[d]=b/a;
        if(sk.count(b/a)) return false;
        if(better(d)) memcpy(ans,v,sizeof(LL)*(d+1));
        return true;
    }
    bool ok=false;
    for(LL i=max(from,get_first(a,b));;++i){
        if(b*(maxd+1-d)<=i*a) break;
        if(sk.count(i)) continue;
        v[d]=i;
        LL b2=b*i;
        LL a2=a*i-b;
        LL g=gcd(a2,b2);
        if(dfs(d+1,i+1,a2/g,b2/g)) ok=true;
    }
    return ok;
}
int main(){
    scanf("%d",&t);
    while(t--){
        LL a,b,k,sk0;
        sk.clear();
        scanf("%lld%lld%lld",&a,&b,&k);
        while(k--) scanf("%lld",&sk0),sk.insert(sk0);
        for(maxd=0;;++maxd){
            memset(ans,-1,sizeof(ans));
            if(dfs(0,get_first(a,b),a,b)) break;
        }
        printf("Case %d: %lld/%lld=",++tt,a,b);
        for(int i=0;i<=maxd;++i){
            if(i) printf("+");
            printf("1/%lld",ans[i]);
        }
        printf("\n");
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出一串数字，加上＋、－、＊使得结果等于2000。

数字上限9个，直接进行暴力即可，感觉STL写起来快，居然还过了。

反正也挺简单的，就不想再用字符数组重写了，用字符数组应该会快好多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<algorithm>
#include<string>
#include<set>
#include<vector>
#include<cctype>
#include<map>
using namespace std;
const string sign[]={"*","+","-",""};
set<string> ans;
map<char,int> dict;
bool cal(string s){//计算字符串表示的值。
    int t=0,p=0,q=0;
    vector<int> num,sg;
    while(1){
        int num0=0,sg0=0;
        while(isdigit(s[p])) num0*=10,num0+=s[p++]-'0';
        num.push_back(num0);
        if(s[p]=='=') break;
        sg0=dict[s[p++]];
        sg.push_back(sg0);
        ++q;
    }
    for(int i=0;i<sg.size();++i){
        if(sg[i]==1){
            num[i+1]*=num[i];
            num.erase(num.begin()+i);
            sg.erase(sg.begin()+i);
            --i;
        }
    }
    t=num[0];
    for(int i=0;i<sg.size();i++){
        if(sg[i]==2) t+=num[i+1];
        else t-=num[i+1];
    }
    return t==2000;
}
void dfs(string s,int pos,bool flag){
    if(pos==s.size()-1){
        if(cal(s)) ans.insert(s);
        return;
    }
    for(int i=0;i<4;++i){
        if(!flag&&i==3) continue;
        string s0=s;
        if(s[pos]!='0') dfs(s0.insert(pos,sign[i]),i==3?pos+1:pos+2,true);
        else dfs(s0.insert(pos,sign[i]),i==3?pos+1:pos+2,i==3);
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    int t=0;
    string s;
    dict['*']=1,dict['+']=2,dict['-']=3;
    while(cin>>s){
        ans.clear();
        if(s[0]=='=') break;
        dfs(s,1,s[0]!='0');
        cout<<"Problem "<<++t<<endl;
        if(!ans.size()||s=="2000=") cout<<"  IMPOSSIBLE"<<endl;//至少要加一个符号。
        else for(set<string>::iterator it=ans.begin();it!=ans.end();++it)
            cout<<"  "<<*it<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

有n个结点，一个结点上有机器人，其余结点有的有障碍物，给出结点之间的通路，求最少经过多少步才能让机器人到达目标结点。

很像书上八数码的那道例题，使用一个vis数组保存所有状态，然后进行BFS。不同的是，这这道题要进行状态压缩，否则会超时。

将每个结点是否为空用一个整数记录，然后用另一个记录机器人的位置，只有(1<<maxn)*maxn数量级的数据，就不会超时了。

找到之后递归打印解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=15;
const int maxstate=(1<<maxn)*maxn+10;
int n,m,s,t;
int fa[maxstate],dist[maxstate];
bool vis[1<<maxn][maxn],g[maxn][maxn];
typedef int go[2];
typedef int state[2];
state st[maxstate];
go k[maxstate];
void read(){
    memset(g,0,sizeof(g));
    memset(k,0,sizeof(k));
    memset(fa,0,sizeof(fa));
    memset(st,0,sizeof(st));
    memset(vis,0,sizeof(vis));
    memset(dist,0,sizeof(dist));
    scanf("%d%d%d%d",&n,&m,&s,&t);
    st[1][1]=s-1,st[1][0]|=1<<(s-1);//记录初始状态机器人的位置。
    for(int i=0;i<m;++i){
        int k;
        scanf("%d",&k);
        st[1][0]|=1<<(k-1);//障碍物的位置。
    }
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u-1][v-1]=g[v-1][u-1]=true;
    }
    return;
}
int bfs(){
    int front=1,rear=2;
    while(front<rear){
        state& s=st[front];
        if(s[1]==t-1) return front;
        for(int i=0;i<n;++i){
            if(!(s[0]&(1<<i))) continue;
            for(int j=0;j<n;++j){
                if((s[0]&(1<<j))||!g[i][j]) continue;
                state& t=st[rear];
                memcpy(&t,&s,sizeof(s));
                if(s[1]==i) t[1]=j;
                t[0]^=1<<i|1<<j;//交换位置。
                k[rear][0]=i+1,k[rear][1]=j+1;
                dist[rear]=dist[front]+1,fa[rear]=front;//记录父状态。
                if(!vis[t[0]][t[1]]) vis[t[0]][t[1]]=true,++rear;
            }
        }
        ++front;
    }
    return 0;
}
void print_ans(int a){
    if(!fa[a]) return;//递归至初始状态。
    print_ans(fa[a]);
    printf("%d %d\n",k[a][0],k[a][1]);
    return;
}
int main(){
    int t,tt=0;
    scanf("%d",&t);
    while(t--){
        read();
        int a=bfs();
        printf("Case %d: %d\n",++tt,a?dist[a]:-1);
        print_ans(a);
        printf("\n");
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出一个数，进行加减运算，可以使用中途计算的结果，最少经过多少次可以获得目标值。中途的运算不能出现负数。

按照书上说的，每次只去最后生成的数进行运算，当那个数乘2^(maxd-d)小于目标值时，剪枝。

PS：提交时可以进行打表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<cstring>
using namespace std;
int a[35],n,i;
bool dfs(int v,int d,int maxd){
    if(d>maxd) return 0;
    if((a[d]=v)<<(maxd-d)<n) return 0;
    if(v==n||v<<(maxd-d)==n) return 1;
    for(int i=0;i<=d;++i){
        if(dfs(v+a[i],d+1,maxd)) return 1;
        if(v-a[i]>0&&dfs(v-a[i],d+1,maxd)) return 1;
    }
    return 0;
}
int main(){
    while(~scanf("%d",&n)&&n){
        for(i=0;;++i) if(dfs(1,0,i)) break;
        printf("%d\n",i);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出一些木棍的长度，把这些木棍拼成长度相同的长木棍，求最短的长度。

首先对所有木棍进行降序排序，然后开始枚举，枚举下界是小木棍长度的最大值，上界是小木棍长度之和的一半。

在枚举的过程中必须进行剪枝，否则会超时。

1、当前枚举的长木棍长度不是小木棍长的和的因数时跳过。

2、与当前小木棍长度相同的小木棍没有使用，当前小木棍也不会使用。

3、当前是拼新的长木棍的第一个小木棍，而最后无法拼成的，直接回溯。

4、一根木棍补足长木棍剩余所需长度，而最后无法拼成的，直接回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int a[maxn],n,len,num;
bool vis[maxn];
bool cmp(int a,int b){return a>b;}
bool dfs(int l,int cur,int cnt){
    if(cnt==num) return true;
    for(int i=cur;i<n;++i){
        if(vis[i]||(i&&a[i]==a[i-1]&&!vis[i-1])) continue;//前一个相同长度的木棍未使用，当前的也不会使用。
        if(a[i]+l==len){
            vis[i]=true;
            if(dfs(0,0,cnt+1)) return true;
            vis[i]=false;
            return false;//正好拼上最后的长度，而后面拼不好，回溯。
        }
        if(a[i]+l<len){
            vis[i]=true;
            if(dfs(a[i]+l,i+1,cnt)) return true;
            vis[i]=false;
            if(!l) return false;//新木棍的第一根，后面无法拼成，回溯。
        }
    }
    return false;
}
int main(){
    while(~scanf("%d",&n)&&n){
        memset(vis,0,sizeof(vis));
        int sum=0;
        for(int i=0;i<n;++i)
            scanf("%d",&a[i]),sum+=a[i];
        sort(a,a+n,cmp);
        int i=a[0];
        for(;i<=sum/2;++i){
            if(sum%i) continue;//只枚举sum的因数。
            len=i,num=sum/i;
            if(dfs(0,0,0)) break;
        }
        if(i<=sum/2) printf("%d\n",len);//在max~sum/2之间没有找到解，则只能是sum。
        else printf("%d\n",sum);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 Disqus：

这次比赛做的比上次好多了，pretest过了三道，除了A题脑残CE了一次，B、C都是一次过了的。系统测试C题WA了，最后是出了2道，上了140分，又变成蓝名 了。

510A - Fox And Snake：

输出蛇形图案，简单题，一开始头文件搞错了，CE了一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    bool p=1;
    for(int i=1;i<=n;++i){
        if(i&1){
            for(int j=0;j<m;++j)
                cout<<"#";
        }
        else{
            if(!p) cout<<"#";
            for(int j=0;j<m-1;++j)
                cout<<".";
            if(p) cout<<"#";
            p=!p;
        }
        cout<<endl;
    }
    return 0;
}

510B - Fox And Two Dots：

再给出的图案中，判断有没有环。DFS判环解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=55;
char g[maxn][maxn];
int vis[maxn][maxn];
int go[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int dfs(int x,int y,int px,int py,int t){
    vis[x][y]=t;
    for(int i=0;i<4;++i){
        if(vis[x+go[i][0]][y+go[i][1]]){
            if(vis[x+go[i][0]][y+go[i][1]]==t&&(x+go[i][0]!=px||y+go[i][1]!=py))//成环。
                return 1;
            else continue;
        }
        if(g[x+go[i][0]][y+go[i][1]]&&g[x+go[i][0]][y+go[i][1]]==g[x][y])
            if(dfs(x+go[i][0],y+go[i][1],x,y,t)) return 1;
    }
    return 0;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin.get();
        for(int j=1;j<=m;++j)
            cin>>g[i][j];
    }
    int t=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
            if(!vis[i][j])
                if(dfs(i,j,-1,-1,++t)){
                    cout<<"Yes"<<endl;
                    return 0;
                }
    }
    cout<<"No"<<endl;
    return 0;
}

510C - Fox And Names：

输入按字典序排好的名字，输出一个字母表使排序成立。

拓扑排序的题，照着书上的代码敲的过了pretest，忽略了一种很坑的情况。当后面的串是前面的前缀时，怎么改字母表都是没有用的，只能是“Impossible” 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int g[30][30];
int topo[30],c[30],t;
string s[110];
bool dfs(int u){
    c[u]=-1;
    for(int v=0;v<26;++v)
        if(g[u][v]){
            if(c[v]<0) return false;
            else if(!c[v]&&!dfs(v)) return false;
        }
    c[u]=1;
    topo[--t]=u;
    return true;
}
bool toposort(){//拓扑排序。
    t=26;
    memset(c,0,sizeof(c));
    for(int u=0;u<26;++u)
        if(!c[u]) if(!dfs(u)) return false;
    return true;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;++i)
        cin>>s[i];
    for(int i=0;i<n;++i){
        for(int j=i+1;j<n;++j){
            int p=0,ok=1;
            while(s[i][p]==s[j][p]){
                p++;
                if(s[i].length()==p||s[j].length()==p){
                    if(s[i].length()>s[j].length()){//一开始忽略的情况。
                        cout<<"Impossible"<<endl;
                        return 0;
                    }
                    ok=0;
                    break;
                }
            }
            if(ok) g[s[i][p]-'a'][s[j][p]-'a']=1;
        }
    }
    if(toposort())
        for(int i=0;i<26;++i)
            cout<<(char)(topo[i]+'a');
    else cout<<"Impossible";
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **