水题笔记_ virus改二 [拓扑排序]

中午在机房做的…没回宿舍感觉真爽…(我们宿舍没空调啊mmp!!!)

懵逼的 题目

病毒
[问题描述]
  有一天,小y突然发现自己的计算机感染了一种病毒!还好,小y发现这种病毒很弱,只是会把文档中的所有字母替换成其它字母,但并不改变顺序,也不会增加和删除字母。
  现在怎么恢复原来的文档呢!小y很聪明,他在其他没有感染病毒的机器上,生成了一个由若干单词构成的字典,字典中的单词是按照字母顺序排列的,他把这个文件拷贝到自己的机器里,故意让它感染上病毒,他想利用这个字典文件原来的有序性,找到病毒替换字母的规律,再用来恢复其它文档。
  现在你的任务是:告诉你被病毒感染了的字典,要你恢复一个字母串。
[输入格式]
virus.in
  第一行为整数K(≤50000),表示字典中的单词个数。
  以下K行,是被病毒感染了的字典,每行一个单词。
  最后一行是需要你恢复的一串字母。
  所有字母均为小写。
[输出格式]
virus.out
   输出仅一行,为恢复后的一串字母。当然也有可能出现字典不完整、甚至字典是错的情况,这时请输出一个0。
[输入样例]

1
2
3
4
5
6
7
8
  6
  cebdbac
  cac
  ecd
  dca
  aba
  bac
  cedab

[输出样例]

1
  abcde

扯淡的 题解

不会装影子系统嘛不会装影子系统嘛不会装影子系统嘛(划掉)
请忽略那些难看的字体QAQ
思路
大体就是这个意思…以大小关系建图,然后走一遍拓扑排序,得到的就是字母表…emm…然后…翻译就吼辣~
再次安利onenote(逃)

Update: 2017.09.01 意外发现居然传错了代码!QAQ…而且原来的代码不见了!QAQ…
Update: 2017.09.03 码完了…而且过了QAQ
在判错方面增加了改进…记录了图中的所有节点…如果整个图中的节点还比passw的长度小的话就puts("0");居然就解决了…吐槽数据水…

沙茶的 代码

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
96
97
98
99
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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
// virus.cpp : 定义控制台应用程序的入口点。
//

//#include "stdafx.h"
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <string>
#include <queue>
#define MAXS (50000 + 5)
#define MAXN (26 + 5)
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
bool g[MAXN][MAXN];
int du[MAXN];
int totalpha = 0;
bool failed = false;
string srs[MAXS];
string passw;
int keyword[MAXN];
int sn;
void inp();
void init();
void tp();
inline int zh(const char x)
{
return x - 'a' + 1;
}
int main()
{
// freopen("virus.in", "r", stdin);
// freopen("virus.out", "w", stdout);
inp();
/*for (int i = 1; i <= 26; i++)
{
printf("%d ", du[i]);
}
puts("");*/
/*for (int i = 1; i <= sn; i++)
{
cout << srs[i] << endl;
}
cout << passw << endl;*/
totalpha++;
// printf("%d\n\n", totalpha);
if (failed || (totalpha < passw.length()))
{
puts("0");
return 0;
}
tp();
if (failed)
{
puts("0");
return 0;
}
int n = passw.length();
/* for (int i = 1; i <= 26; i++)
{
printf("%d ", keyword[i]);
}
puts("");*/
for (int i = 0; i < n; i++)
{
if (keyword[(int)passw[i] - 'a' + 1] == 0)
{
puts("0");
return 0;
}
}
for (int i = 0; i < n; i++)
{
cout << (char)(keyword[(int)passw[i] - 'a' + 1] + 'a' - 1);
}
return 0;
}
void inp()
{
cin >> sn;
for (int i = 1; i <= sn; i++)
{
cin >> srs[i];
}
cin >> passw;
init();
}
void init()
{
for (int i = 1; i < sn; i++)
{
for (int j = i + 1; j <= i + 1; j++)
{
int dqn = min((srs[i].length()), (srs[j].length()));
if (srs[i] == srs[j])
{
failed = true;
return ;
}
for (int k = 0; k < dqn; k++)
{
if (srs[i][k] != srs[j][k])
{
int fromz = zh(srs[i][k]);
int toz = zh(srs[j][k]);
if (!g[fromz][toz])
{
g[fromz][toz] = true;
du[toz]++;
totalpha++;
}
if (g[toz][fromz])
{
failed = true;
return ;
}
break;
}
}
}
}
}
void tp()
{
int n = 26;
//queue<int> q;
bool v[27];
memset(v, false, sizeof(v));
for (int i = 1; i <= n; i++)
{
int k = 0;
for (int j = 1; j <= n; j++)
{
if (!du[j] && !v[j])
{
if (!k)
{
k = j;
break;
}
else
{
failed = true;
return;
}
}
}
v[k] = true;
if (!k)
{
failed = true;
return ;
}
for (int j = 1; j <= n; j++)
{
if (g[k][j])
{
g[k][j] = false;
du[j]--;
}
}
keyword[k] = i;
}
}
/*
6
cebdbac
cac
ecd
dca
aba
bac
cedab
*/

By 干啥啥不行代码还能传错的 Cansult