NSOqwq

题解 P1127 【词链】

题解 P1127 词链

UPD 2020.9.4:感谢 @太阳起晚了呢,修改了一处 bug,并修改了排版。

题意

给你几个字符串,让你把这个字符串排列组合一下,使得相邻的两个单词中前面一个单词的尾字母等于后面一个单词的首字母。

思路

这道题肯定是一道搜索题。

思路:从任意一个字符串 $s$ 开始,每次在输入的所有字符串中查找首字母与 $s$ 的尾字母相同的字符串,然后用找到的这个字符串继续搜索,直到搜索到 $n$ 个字符串为止。

「每次在输入的所有字符串中查找首字母与 $s$ 的尾字母相同的字符串」这个过程可以在输入的时候就建图,在首、尾字母相同的两个字符串之间建立一条边,然后搜索的时候直接用建好的这些边找就行了。

这个搜索很好做,大概只有黄题的难度,核心代码如下:

std::string a[1001];
std::vector<int> e[1001];

for (int i = 1; i <= n; ++i)
  std::cin >> a[i];
std::sort(a + 1, a + n + 1); // 字典序排序(题目要求)
for (int i = 1; i <= n; ++i)
  for (int j = 1; j <= n; ++j)
    if (i != j && a[i][a[i].length() - 1] == a[j][0]) // 判断两个字符串是否可以相连(前一个字符串的尾字母等于后一个字符串的首字母)
      e[i].push_back(j);

bool used[1001];
// s: 当前字符串的编号(所有字符串按字典序,编号分别为 1 到 n)
// curr: 当前已生成的词链。
// count: 已查找到的字符串个数。
void dfs(int s, std::string curr, int count) {
    if (count == n) {
        curr[curr.length() - 1] = ' '; // 把最后一个 '.' 去掉。
        std::cout << curr;
        exit(0);
    }
    for (auto i : e[s])
        if (!used[i]) {
            used[i] = true;
            dfs(i, curr + a[i] + '.', count + 1);
            used[i] = false;
        }
}

然后用每一个字符串当作第一个单词试一遍,如果可以就直接输出然后结束程序。

这种做法,可以拿到 $80$ 分。

考虑优化

有两个点炸掉了,所以我们要考虑优化。

显然「每一个字符串当作第一个单词试一遍」这个方法效率非常低。

我们需要筛选出一些可能作为词链的第一个单词的词。

如何找到这个单词呢?

观察样例,我们发现:

a----a.a----d.d----g.g----r.r----t.t-----

发现 a 作为词链的第一个字母,它作为单词的首字母的次数为 $2$(它是单词 alohaarachnid 的首字母),作为单词的尾字母的次数为 $1$ (它是 aloha 的尾字母)。首字母次数是尾字母次数加 $1$。

再仔细思考一下,或者自己造几个样例,发现对于每一个合法的词链,它的首字母字符,它作为单词的首字母的次数永远是它作为单词尾字母的次数加上 $1$。

因为从第一个单词的尾字母开始到最后一个单词的首字母结束,每个作为首字母/尾字母的字母的出现次数都是偶数(成对出现)(这个应该很好理解)。

然而第一个单词的首字母多出现了一次,它不是成对出现的。

所以就有了上述结论。

当然,也有特殊情况,就是最后一个单词的尾字母和第一个单词的首字母是一样的(即可以连成一个环)。那么从 $1$ 开始就行了。

int ind[1001]; // 作为首字母的次数
int rnd[1001]; // 作为尾字母的次数

// 所以执行 find() 前要加上这段:
for (int i = 1; i <= n; ++i) {
  ++ind[a[i][0]];
  ++rnd[a[i][a[i].length() - 1]];
}

for (int i = 1; i <= n; ++i)
  if (ind[a[i][0]] == rnd[a[i][0]] + 1) {
    used[i] = true;
    dfs(i, a[i] + '.', 1);
    used[i] = false;
  }
used[1] = true;
dfs(1, a[1] + '.', 1);
used[1] = false; // 不行,就从 1 开始。

代码

int n;
std::string a[1001];
std::vector<int> e[1001];
int ind[1001];
int rnd[1001];
bool used[1001];

void dfs(int s, std::string curr, int count) {
    // 与不优化时同样的 dfs 代码。
}

int main() {
    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
        ++ind[a[i][0]];
        ++rnd[a[i][a[i].length() - 1]];
    }
    std::sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i != j && a[i][a[i].length() - 1] == a[j][0])
                e[i].push_back(j);
    for (int i = 1; i <= n; ++i)
        if (ind[a[i][0]] == rnd[a[i][0]] + 1) {
            used[i] = true;
            dfs(i, a[i] + '.', 1);
            used[i] = false;
        }
    used[1] = true;
    dfs(1, a[1] + '.', 1);
    used[1] = false;
    std::cout << "***";
    return 0;
}

这就是这篇题解的全部内容了,这个解法还是和大部分之前的题解都不一样的,个人认为更好理解一些。


2021-01-03 23:32:52 in 题解