C++实现玛雅字典问题
保存
玛雅字典
难度：
时间限制：1s
内存限制：128M
开始编程
【题目描述】
玛雅文明是一个非常神秘的文明，虽然处于新石器时代，却在天文学、数学、农业、艺术等方面都有极高成就，以至于很多人猜测玛雅文明是外星人留下的。
玛雅文不像英文那样用二十六个字母组成，而是使用象形文字，每个字都有四个音节。为了方便表示，可以用单个大写字母代表一个音节，每个象形文字可以用四个大写字母表示出来。
目前语言学家已经成功破译了n个玛雅文字的音节，和这些音节能组成的所有文字，这些文字主要代表一周各天和月份的名称、数目字、方位、颜色以及神祇的名称，但是玛雅文字与组成文字的音节之间的对应关系还是未解之谜。
小玉是一位非常优秀的考古学家，她对玛雅文明有着浓厚的兴趣，最近她发掘了一些玛雅文明的石板，经过仔细的考察，她注意到石板上玛雅文字是按照固定的顺序排列的，这些石板竟然是玛雅人所使用的字典！这意味着她可以确定玛雅文字的字典顺序，对理解玛雅文肯定有很大的帮助！
小玉非常兴奋，但是她还要继续进行发掘工作，因此分析的工作就交给你了。你的任务是对给定的所有石板，求石板出现的所有玛雅文字的一种合理的排布顺序，使其满足所有石板的文字顺序。
【输入格式】
输入第一行，两个整数n和m，表示已经破译的音节数量和小玉发掘的石板数量。
第二到m+1行，第i+1行第一个数d
i
，表示第i个石板上可识别的文字数量，然后输入d
i
个空格分隔的字符串，表示第i个石板的所有可识别文字，输入按石板的文字顺序，保证每个字符串都是由四个大写字母组成，并且同一行的任意两个字符串各不相同。
【输出格式】
如果不存在满足所有石板顺序的单词顺序，请直接输出"No solution."（不含引号），如果存在，请按顺序输出所有出现的文字对应的字符串，每行一个。如果有多种方案，请输出字典序（指英文字母）最小的一种方案。
复制
【说明提示】
【样例解释1】
石板中只出现了5个文字，只有一种顺序可以满足所有石板。
【样例解释2】
不存在任何合法的方案。
【样例解释3】
"ABDB"和"DCCB"都可以作为字典顺序最小的文字，但是考虑到需要英文字典序最小，选择"ABDB"作为第一个文字。
【数据范围】
对于30%的数据，n=2，∑
i=1
m
d
i
≤30。
另有10%的数据，m=1。
对于60%的数据，n≤20，∑
i=1
m
d
i
≤3×10
5
。
对于100%的数据，1≤n≤26，1≤m≤10000，1≤∑
i=1
m
d
i
≤10
6
，保证代表文字的字符串中只会出现大写字母的前n个。
字典序的思路参考
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int i, j;
string s1, s2, s3;
int main() {
cin >> s1 >>s2;
s3 += s1[0];
for (int i = 1; i < s1.size(); i ++ ) {
if(s1[i] < s2[0]) s3 += s1[i];
else break;
}
s3 += s2[0];
cout << s3;
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
int n, m;
int h[N], e[N], ne[N], idx;
int indeg[N], q[N], cnt;
bool st[N];
char str[N];
int order[N];
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
bool topsort() {
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++)
if (!indeg[i])
q[++tt] = i;
while (hh <= tt) {
int t = q[hh ++];
order[cnt ++] = t;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
indeg[j] --;
if (indeg[j] == 0) q[++tt] = j;
}
}
return cnt == n;
}
int main() {
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
while (m --) {
int k;
scanf("%d", &k);
while (k --) {
scanf("%s", str);
for (int i = 0; i < 4; i ++)
st[str[i] - 'A'] = true;
}
for (int i = 1; i < k; i ++)
if (memcmp(str + 4 * (i - 1), str + 4 * i, 4) != 0) {
int a = str[4 * (i - 1)] - 'A';
int b = str[4 * i] - 'A';
if (!st[a]) indeg[a] = 0;
if (!st[b]) indeg[b] = 0;
st[a] = st[b] = true;
add(a, b);
indeg[b] ++;
break;
}
}
if (topsort()) {
for (int i = 0; i < n; i ++)
printf("%c", order[i] + 'A');
} else {
printf("No solution.");
}
return 0;
}
应该是拓扑排序吧。
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int MAX_N = 26 * 26 * 26 * 26 + 10;
int n, m;
vector<int> graph[MAX_N], ans; // 邻接表表示图和拓扑排序结果
int in_degree[MAX_N]; // 入度数组
void topsort() {
queue<int> q;
for (int i = 1; i <= n; ++i) { // 将入度为0的点加入队列
if (in_degree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front(); q.pop();
ans.push_back(u); // 将u加入拓扑排序序列
for (int v : graph[u]) { // 将u的邻接点的入度减1
--in_degree[v];
if (in_degree[v] == 0) { // 如果v的入度为0，加入队列中等待处理
q.push(v);
}
}
}
}
int main()
{
cin >> n >> m;
string s;
string prev = ""; // 保存前一个字符串
vector<string> strs; // 保存所有出现的字符串
for (int i = 0; i < m; ++i) {
int d;
cin >> d;
cin >> s;
strs.push_back(s); // 将当前字符串加入集合中
--d;
while (d--) {
prev = s;
cin >> s;
strs.push_back(s); // 将当前字符串加入集合中
int u = (prev[0] - 'A') * 26 * 26 * 26 + (prev[1] - 'A') * 26 * 26 + (prev[2] - 'A') * 26 + prev[3] - 'A';
int v = (s[0] - 'A') * 26 * 26 * 26 + (s[1] - 'A') * 26 * 26 + (s[2] - 'A') * 26 + s[3] - 'A';
graph[u].push_back(v);
++in_degree[v]; // 更新入度数组
}
}
topsort(); // 进行拓扑排序
if (ans.size() != n) { // 如果存在环，即无法拓扑排序，则输出"No solution."
cout << "No solution." << endl;
} else {
for (int i = 0; i < n; ++i) { // 输出每个节点对应的字符串
int u = ans[i];
cout << strs[(u - 1) / 26 / 26 / 26 % 26 * 26 * 26 + (u - 1) / 26 / 26 % 26 * 26 + (u - 1) / 26 % 26] << endl;
}
}
return 0;
}
基于new bing的参考编写：
#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
// 下面为图的拓扑排序算法
void Topological_Sort(unordered_map<char, vector<char> > &graph, int n)
{
vector<int> inDegree(n, 0); // 记录每个字符的度数
for (auto it = graph.begin(); it != graph.end(); it++) {
for (auto &c : it->second) {
inDegree[c - 'A']++;
}
}
priority_queue<char, vector<char>, greater<char>> Q; // 优先队列用于存放入度为0的所有结点
for (auto it = graph.begin(); it != graph.end(); it++) {
if (inDegree[it->first - 'A'] == 0) {
Q.push(it->first);
}
}
string ans = "";
while (!Q.empty()) {
char cur = Q.top();
Q.pop();
ans += cur;
for (auto &c : graph[cur]) {
if (--inDegree[c - 'A'] == 0) {
Q.push(c);
}
}
}
if (ans.length() == n) {
cout << ans[0];
for (int i = 1; i < n; i++) {
cout << " " << ans[i];
}
cout << endl;
} else {
cout << "No solution." << endl;
}
}
int main()
{
int n, m;
cin >> n >> m;
unordered_map<char, vector<char> > graph;
// 构建初始的拓扑图
for (int i = 0; i < n; i++) {
graph['A' + i] = vector<char>();
}
for (int i = 0; i < m; i++) {
int d;
cin >> d;
vector<string> strs(d);
for (int j = 0; j < d; j++) {
cin >> strs[j];
}
for (int j = 0; j < d - 1; j++) {
string s1 = strs[j], s2 = strs[j + 1];
int k;
for (k = 0; k < 4; k++) {
if (s1[k] != s2[k])
break;
}
if (k == 4) //两个字符串完全相同
continue;
char from = s1[k];
char to = s2[k];
graph[from].push_back(to);
}
}
// 检测是否存在环路，如果有直接输出No solution.
bool hasLoop = false;
for (auto it = graph.begin(); it != graph.end(); it++) {
vector<bool> visited(n, false); // 使用dfs检测是否存在环路
function<bool(char)> dfs = [&](char cur) {
visited[cur - 'A'] = true;
for (auto &c : graph[cur]) {
if (visited[c - 'A'] || dfs(c)) {
return true;
}
}
visited[cur - 'A'] = false;
return false;
};
if (dfs(it->first)) {
hasLoop = true;
break;
}
}
if (hasLoop) {
cout << "No solution." << endl;
} else {
Topological_Sort(graph, n);
}
return 0;
}