CF1303C Perfect Keyboard

我近期在狂刷 CF，好久没写题解了，今天来一发。

思路

通过观察，键盘上每一个字母最多只与两个字母相邻，所以当一个字母与两个以上的不同字母相邻时肯定是无解的，直接输出 NO。

接下来我们进行模拟。因为字母只有

26

个，所以我们可以用邻接矩阵来存储相邻的字母，并使用桶来计算每个字母相邻不同字母的数量。

接下来，我们将每个相邻字母数小于

2

个的字母且没有被访问过的字母跑 DFS，将访问到的字母放进答案中。

为什么是小于

2

个？我们不妨先考虑一组特殊数据：afghjfg。这组数据肯定是无解的，因为其中有环。环中字母的相邻字母数一定不小于

2

个，所以环内的字母无法被访问，可以由此来判断出现环的无解情况。

综上，本题大致思路已经完成。

代码

多组数据，记得清空。

预处理部分

CPP

for (int i = 1; i < n; i++)
{
    if (!g[s[i]][s[i - 1]])                           // 防止重复计算！
    {
        g[s[i]][s[i - 1]] = 1, g[s[i - 1]][s[i]] = 1; // g[u][v]: 是否存在 (u, v) 边
        lk[s[i]]++, lk[s[i - 1]]++;                   // 双向边
        if (lk[s[i]] > 2 || lk[s[i - 1]] > 2)         // lk[i]: 字母 i 的相邻字母数
        {
            cout << "NO\n";
            print = true;
            break;
        }
    }
}

DFS 部分

CPP

void dfs(char u)
{
    if (vis[u])
        return ;
    vis[u] = true;                   // 记录是否访问
    ans += u;                        // ans: 构造结果
    for (int v = 'a'; v <= 'z'; v++)
        if (g[u][v] && v != u)       // g[u][v]: 是否存在 (u, v) 边
            dfs(v);
}

主函数核心部分

CPP

for (int i = 'a'; i <= 'z'; i++)
    if (!vis[i] && lk[i] <= 1)
        dfs(i);
for (int i = 'a'; i <= 'z'; i++)
{
    if (!vis[i]) // 有字母没访问，一定存在环
    {
        cout << "NO\n";
        print = true;
        break;
    }
}

CF1303C Perfect Keyboard 题解

文章操作