题目

{% fold 点击显/隐题目 %}

罗塞塔石碑（Rosetta Stone，又译为罗塞达碑），是一块制作于公元前 196 年的花岗闪长岩石碑，原本只是一块刻有古埃及法老托勒密五世（Ptolemy V）诏书的石碑，但由于这块石碑同时刻有同一段内容的三种不同语言版本，使得近代的考古学家得以有机会对照各语言版本的内容后，解读出已经失传千余年的埃及象形文之意义与结构，而成为今日研究古埃及历史的重要里程碑。罗塞塔石碑最早是在 1799 年时由法军上尉皮埃尔·弗朗索瓦·札维耶·布夏贺（Pierre-François Xavier Bouchard）在一个埃及港湾城市罗塞塔（Rosetta，今日亦称为拉希德）发现，但在英法两国的战争之中辗转到英国手中，自 1802 年起保存于大英博物馆中并公开展示。 但你可能不知道的是，解读这上面的文字却费尽了历代考古学者的心血。在公元 4 世纪结束后不久，尼罗河文明式微、不再使用的埃及象形文之读法与写法彻底失传，虽然之后有许多考古与历史学家极尽所能，却一直解读不了这些神秘文字的结构与用法。直到时隔 1400 年之后罗塞塔石碑出土，它独特的三语对照写法，意外成为解码的关键，因为三种语言中的古希腊文是近代人类可以阅读的，利用这关键来比对分析碑上其他两种语言的内容，就可以了解这些失传语言的文字与文法结构。 在许多尝试解读罗塞塔石碑的学者中，19 世纪初期的英国物理学家托马斯·杨（Thomas Young）是第一个证明碑文中曾多次提及“托勒密”这人名的发音者。至于法国学者尚-佛罕索瓦·商博良（Jean-François Champollion）则是第一个理解到，一直被认为是用形表义的埃及象形文，原来也是具有表音作用的，这重大发现之后成为解读所有埃及象形文的关键线索。也正是因为这缘故，罗塞塔石碑会被称为了解古埃及语言与文化的关键基础。 解读石碑的关键在于：找到语言与语言之间的匹配规则，然后尝试应用这些匹配规则，来解读文字。这些匹配规则可能需要被反复调整，以至于最终，我们所得到的文字能变成完整的一句话。今天，通过计算机，我们可以重现这个过程。为了避免处理难以输入的埃及文字，我们使用英文小写字母来代替。 给出 m 条匹配规则，每条匹配规则都表示一个字母可以被译成另一个字母。一个字母可能适用于多条规则，也可能不适用于任何规则。你可以运用多次。例如，如果 `a` 可以变成 `e`，`e` 可以变成 `i`，那么，`a` 也可以译为 `i`。 再有 n 对单词，请输出每对单词中的第一个能否译为第二个。在翻译过程中，你不能对字母进行增删。
第一行两个整数 $m$,$n$ (1≤$m$≤500,1≤$n$≤50)。 接下来 $m$ 行匹配规则，每行两个字母用一个空格隔开 $a$ $b$，表示 $a$ 可以被译成 $b$。 接下来 $n$ 行，每行一对单词，用一个空格隔开，单词长度不超过 $50$。 规则和单词中只会出现小写字母。
如果可以输出 `yes`，否则输出 `no`
9 5 c t i r k p o c r o t e t f u h w p we we can the work people it of out the

3 3
a c
b a
a b
aaa abc
abc aaa
acm bcm

yes no no yes yes

yes
no
yes

{% endfold %}

题解

数据比原题弱,用set水过,原题大概要用字符串hash

代码

{% fold 点击显/隐代码 %}```cpp 罗塞塔石碑 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
#include
#include
using namespace std;

const int maxn = 30;
#define Log(format, ...) // printf(format, ##VA_ARGS)

vector<pair<char, char>> vec;
set s[maxn];

void init() {
vec.clear();
for (int i = 0; i < maxn; ++i) {
s[i].clear();
s[i].insert(i);
}
};

void add(int a, int b) {
s[a].insert(b);
for (int t : s[b]) {
if (s[a].count(t) == 0) {
add(a, t);
}
}
}

bool calc(string a, string b) {
int lena = a.size();
int lenb = b.size();
bool ok = false;
if (lena == lenb) {
ok = true;
for (int i = 0; i < lena && ok; ++i) {
if (s[a[i] - 'a'].count(b[i] - 'a') == 0)
ok = false;
}
}
return ok;
}

int main() {
cin.tie(0);
cin.sync_with_stdio(false);
int n, m;
while (cin >> n >> m) {
init();
for (int i = 0; i < n; ++i) {
char a, b;
cin >> a >> b;
vec.push_back(make_pair(a, b));
}

    for (int i = 0; i < n; ++i) {
        add(vec[i].first - 'a', vec[i].second - 'a');
    }
    for (int i = n - 1; i >= 0; --i) {
        add(vec[i].first - 'a', vec[i].second - 'a');
    }
    for (int i = 0; i < n; ++i) {
        add(vec[i].first - 'a', vec[i].second - 'a');
    }
    for (int i = n - 1; i >= 0; --i) {
        add(vec[i].first - 'a', vec[i].second - 'a');
    }



    // for (int i = 0; i < 26; ++i) {
    //     cout << char('a' + i) << ":";
    //     for (auto it : s[i])
    //         cout << " " << char('a' + it);
    //     cout << endl;
    // }

    for (int j = 0; j < m; ++j) {
        string a, b;
        cin >> a >> b;
        cout << (calc(a, b) ? "yes" : "no") << endl;
    }
}
return 0;

}

{% endfold %}