codeforces 510 C. Fox And Names

2015年12月9日 0 作者 CrazyKK

http://codeforces.com/contest/510/problem/C

题意：给定n个字符串。问是否存在一种字母顺序，使得这n个字符串的顺序满足字典序（自定义的）。如果有多种顺序，输出字典序（标准的）最小的。

思路：将字符串的关系处理成边的关系。每次对于第i个和第i+1个字符串，从前往后扫，直到不相等的那一位，设为k,然后连边，指向i+1。表明第i个字符串的第k位大于第i+1个字符串的第k位。如果没有不想等的。说明其中一个是另一个的字串。如果前者是后者的字串，那么不影响。如果后者是前者的字串，则不存在满足条件的字典序。然后做拓扑排序。由于有多种输出字典序（标准的）最小的方案。所以存点的时候用优先队列存。




/* ***********************************************
Author :111qqz
Created Time :2015年12月06日 星期日 15时16分50秒
File Name :code/cf/problem/510C.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;



using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=105;
int n;
char st[N][N];
int p[30];
int offset[30];
bool conc[30][30];
int in[N];
int ans[N];
struct node
{
    int x;
    node(int xx)
    {
	x=xx;
    }
    bool operator <(const node a)const{
	return x>a.x;
    }
};
bool getconc( int x,int y)
{
    int lx = strlen(st[x]);
    int ly = strlen(st[y]);
    int len = min(lx,ly);
    for ( int i =  0; i < len ; i++)
    {
	if (st[x][i]!=st[y][i])
	{
	    conc[st[x][i]-'a'][st[y][i]-'a'] = true;
	    return true;
	}
    }
  //  if (lx>ly) return false;
    return true;
}
bool pre()
{
    ms(conc,false);
    ms(in,0);
    scanf("%d",&n);
    for ( int i = 0 ;i  < n ; i++) scanf("%s",st[i]);

    bool ok = true;
    for ( int i = 0 ; i < n-1 ; i++)
    {
	ok = getconc(i,i+1);
	if (!ok) break;
    }
    if (ok) return true;
    return false;
}

bool topo()
{
    priority_queue<node>q;
    for ( int i = 0 ; i < 26 ; i++)
	if (in[i]==0)  q.push(i);
    
    int cnt = 0 ;

    while (!q.empty())
    {
	node v = q.top();q.pop();
	cnt++;
	ans[cnt]=v.x;
	for ( int i = 0 ; i < 26 ; i++)
	{
	    if (!conc[v.x][i]) continue;
	    in[i]--;
	    if (in[i]==0) q.push(i);
	}
    }
    if (cnt<26) return false;
    return true;
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	if (pre())
	{
	    for ( int i = 0 ; i < 26 ; i++)
		for ( int j = 0 ; j < 26 ; j++)
		    if (conc[i][j]) in[j]++;
	    if (topo())
	    {
		for (int i = 1 ; i <= 26 ; i++)
		    printf("%c",char(ans[i]+'a'));
		puts("");
	    }
	    else
	    {
		puts("Impossible");
	    }
	}
	else
	{
	    puts("Impossible");
	}


  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

/* ***********************************************

Author :111qqz

Created Time :2015年12月06日星期日 15时16分50秒

File Name :code/cf/problem/510C.cpp

************************************************ */

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <cstdlib>

#include <ctime>

#define fst first

#define sec second

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define ms(a,x) memset(a,x,sizeof(a))

typedef long long LL;

using namespace std;

const double eps = 1E-8;

const int dx4[4]={1,0,0,-1};

const int dy4[4]={0,-1,1,0};

const int inf = 0x3f3f3f3f;

const int N=105;

int n;

char st[N][N];

int p[30];

int offset[30];

bool conc[30][30];

int in[N];

int ans[N];

struct node

{

int x;

node(int xx)

{

x=xx;

}

bool operator <(const node a)const{

return x>a.x;

}

};

bool getconc( int x,int y)

{

int lx = strlen(st[x]);

int ly = strlen(st[y]);

int len = min(lx,ly);

for ( int i = 0; i < len ; i++)

{

if (st[x][i]!=st[y][i])

{

conc[st[x][i]-'a'][st[y][i]-'a'] = true;

return true;

}

// if (lx>ly) return false;

return true;

}

bool pre()

{

ms(conc,false);

ms(in,0);

scanf("%d",&n);

for ( int i = 0 ;i < n ; i++) scanf("%s",st[i]);

bool ok = true;

for ( int i = 0 ; i < n-1 ; i++)

{

ok = getconc(i,i+1);

if (!ok) break;

}

if (ok) return true;

return false;

}

bool topo()

{

priority_queue<node>q;

for ( int i = 0 ; i < 26 ; i++)

if (in[i]==0) q.push(i);

int cnt = 0 ;

while (!q.empty())

{

node v = q.top();q.pop();

cnt++;

ans[cnt]=v.x;

for ( int i = 0 ; i < 26 ; i++)

{

if (!conc[v.x][i]) continue;

in[i]--;

if (in[i]==0) q.push(i);

}

if (cnt<26) return false;

return true;

}

int main()

{

#ifndef ONLINE_JUDGE

freopen("code/in.txt","r",stdin);

#endif

if (pre())

{

for ( int i = 0 ; i < 26 ; i++)

for ( int j = 0 ; j < 26 ; j++)

if (conc[i][j]) in[j]++;

if (topo())

{

for (int i = 1 ; i <= 26 ; i++)

printf("%c",char(ans[i]+'a'));

puts("");

}

else

{

puts("Impossible");

}

else

{

puts("Impossible");

}

#ifndef ONLINE_JUDGE

fclose(stdin);

#endif

return 0;

}

分类目录codeforces

标签图论拓扑排序

关于作者

CrazyKK

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！