ecnu 3323.罗塞塔石碑

906


题目


点击显/隐题目

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




题解


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

代码


点击显/隐代码
#include <cstdio>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

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

vector<pair<char, char>> vec;
set<int> 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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论