P1341 无序字母对 题解

· · 题解

前置知识

你需要了解欧拉(回)路，会判断欧拉(回)路的存在性，会输出任意欧拉(回)路。

题目建模

字符串中两个重合的字母对有一个公共字母，把字母抽象为点，那么字符串就是是图上的路径，因为要一一对应，这条路径必须不重不漏地走完所有的边，即求解**欧拉路**，注意最后不一定回到起点，不一是欧拉回路。 题目还要求输出的路径字典序最小，我们利用以下欧拉路 DFS 算法性质求解： > 在图上从某点 $s$ 出发，在 DFS 中按**字典序不严格递增**的顺序遍历可达邻居，则最终得到的"欧拉路"（对于有向图，这个路径走反边）的逆路径是以 $s$ 为终点且**字典序最小**的欧拉路。 简单理解：最后加入欧拉路的点一定是尽可能小的，否则会在前面被优先遍历，从而被更早加入欧拉路，因此反转后字典序最小，任何可能的字典序更小的正序都会在 DFS 中被优先考虑。 这毕竟是目前唯一把这个结论完整放出来的题解了，详细的形式化证明请查阅相关资料，似乎有些 AI 也会证明这个。 _温馨提示：不要试图不通过反转直接得到正序，别想什么反图之类的东西。_ 注：上述性质基于以下伪代码： ```plain function dfs(x){ for each e in Graph[x]{ if(e 已经被访问){ continue } 标记 e 为已访问 dfs(e.to) } 将 x 加入欧拉路 } ``` 那么如何选择 $s$ 呢？显然原路径中 $s$ 一定出现在最后，反转后的路径中 $s$ 出现在第一个位置，因此要最小化 $s$。 - 对于欧拉回路，$s=t$，选择字典序最小的结点即可。 - 对于非欧拉回路的欧拉路，存在两个奇点 $a,b$，它们中有且仅有一个是 $s$，则 $s$ 应该选择两个奇点中字典序偏小的。 求出图中字典序最小的欧拉路的步骤如下： 1. 找到字典序最小的有效起点开始 DFS。 2. DFS 到点 $i$ 时，按出边指向结点 $j$ 的字典序不严格递增的顺序遍历**未访问**的边 $e$，将 $e$ 标记为**已访问**。 3. 前进：在 2. 遍历完每个 $e$ 后进入 $j$ 进行 DFS。 4. 回溯：在 2. 遍历完全部 $e$ 后，将 $i$ 加入欧拉路。 5. 完成所有 DFS 后，将得到的欧拉路反向即为所求。 上述步骤同时支持有向图和无向图，也能处理重边和自环。 ## 编码 ### 字母-数字转化 本题需要实现字母和数字间的转化，可以直接用 ASCII 值，只不过空间较大，也可以进行压缩，下面的函数实现了这样的转化： ```cpp // a-z -> 1-26 | A-Z -> 27-52 inline int char_int(char c){ if(c>96) return (c^96)+26; else return c^64; } // 1-26 -> a-z | 27-52 -> A-Z inline char int_char(int i){ if(i>26) return (i-26)^96; else return i^64; } ``` 其中 `^64`,`^96` 是非常巧妙的，参见[一些位运算技巧](https://www.luogu.com.cn/article/cwl66duc)。 上述函数假设传入的参数是合法的。 ### 无向图的表示 #### 邻接矩阵 本题使用邻接矩阵编码会比较容易，这种方法的缺点是在 $n$ 较大的稀疏图时空复杂度较大，对于 $n=20000, m=100000$ 这种级别数据不能用邻接矩阵，而本题解中的算法可以在 $O(m\log n)$ 的时间复杂度内解决这一类问题。 对于本题而言，使用邻接矩阵编码是最好的，但作为题解和学习，还是有必要详细讲解邻接表存图的。 题解区有很多用邻接矩阵编码的，这里不再赘述相关编码。 #### 邻接表 本题解用 `std::vector` 表示的邻接表存图，但是由于一条无向边出现了 $2$ 次，遍历无向边时根据当前的 $u\rightarrow v$，要同时标记对应的 $v\rightarrow u$ 已访问，下面给出几种实现方法： 1. 给边加上属性 `id`，对于一一对应的无向边赋予相同的 `id`，这样就可以把对边的标记转化为对 `id` 的标记，判断时也方便。 2. 本题解做法：每条边保存自己的对应边的位置，标记该边时同时标记对应边（或者访问时同时访问对应边），注意不要用 `iterator` 存位置，因为 `vector` 自动扩展长度时可能导致原来的 `iterator` 失效。 3. 对于标记 $u\rightarrow v$，直接在 $v$ 上找 $v\rightarrow u$，可以用 `std::map`,`std::set` 等维护，缺点是处理重边较为麻烦，虽然本题没有。 方法 1. 3. 在本题题解区已经出现。 #### 链式前向星 主要问题也是无向边标记问题，这里稍微讲一下处理方法： 1. 同邻接表的 1.，这篇[题解](https://www.luogu.com.cn/article/pzglmvhy)采用了类似方法。 2. 同邻接表的 2.，有一些细节处理参见下面的分析。 ### 合法性检查 1. 判断图的连通性。 2. 判断奇点数目，同时也需要根据奇点是否存在判断是欧拉(回)路以选择正确的 DFS 起点。 ### 访问顺序的维护 上面的方法需要按字典序递增地访问邻居，如何实现？可以想到对邻接表按边指向点的字典序降序排序。 但是对于邻接表方法 2.，**不能直接在原邻接表上排序**，因为这会破坏原来用"对应边的位置"维护的对应关系。 一种解决方法是维护对应的**映射**，在映射上做排序，这样既不破坏原来的对应关系，也能通过遍历映射按正确的递增顺序访问邻居，具体参加下面的代码。 对于链式前向星 2.，方便的是只需要改变头指针和后继就能不破坏对应关系同时控制遍历顺序，麻烦的是链式前向星是一种链式结构，排序较为困难，请读者自行思考。 ### 欧拉路 DFS 做好上面的预处理已经很简单了，请参考上面提到的步骤和下面的代码。 ### 输出答案 将得到的欧拉路反向输出即可，定长数组（注意分配合理的长度），`std::stack`,`std::vector`,`std::string` 等均可。 ## 代码 [存档](https://www.luogu.com.cn/paste/kqr7sq6m) ```cpp #include <cstdio> #include <vector> #include <algorithm> #include <string> using namespace std; // a-z -> 1-26 | A-Z -> 27-52 inline int char_int(char c){ if(c>96) return (c^96)+26; else return c^64; } // 1-26 -> a-z | 27-52 -> A-Z inline char int_char(int i){ if(i>26) return (i-26)^96; else return i^64; } int n; // 邻接表 struct Edge{ int to, inv; bool visited; }; vector<Edge> g[53]; inline void add_edge(int u, int v){ if(u!=v){ g[u].push_back({v, (int)g[v].size(), false}); g[v].push_back({u, (int)g[u].size()-1, false}); }else{ // 注意自环的处理有点特殊，不要只加入一次，因为判断奇点用到了 size() g[u].push_back({u, (int)g[u].size()+1, false}); g[u].push_back({u, (int)g[u].size()-1, false}); } } bool visited[53]; // 点的访问标记，仅用于 dfs(int) void dfs(int u){ visited[u] = true; for(Edge& e:g[u]){ if(!visited[e.to]) dfs(e.to); } } // 获取连通块数目 inline int get_cc(){ int cnt = 0; for(int i=1; i<=52; ++i){ // 注意图上不存在孤立点，不能计入连通块数目 if(g[i].size() && !visited[i]) dfs(i), ++cnt; } return cnt; } // 映射到 g 上的索引，用于从大到小遍历邻居 vector<int> g2[53]; inline void make_g2(){ for(int i=1; i<=52; ++i){ if(!g[i].size()) continue; g2[i].resize(g[i].size()); for(int j=0; j<(int)g[i].size(); ++j){ g2[i][j] = j; } // 由于比较与 i 有关，使用 lambda 方便处理 // 如果不用 lambda，需要用一些静态变量存 i sort(g2[i].begin(), g2[i].end(), [=](int a, int b){ return g[i][a].to<g[i][b].to; }); } } string ans; // 欧拉路 void euler(int u){ for(int eid:g2[u]){ Edge& e = g[u][eid]; // 关键：这样遍历的 e 满足 e.to 是递增的 if(e.visited) continue; e.visited = true; g[e.to][e.inv].visited = true; euler(e.to); } ans.push_back(int_char(u)); } int main(){ scanf("%d", &n); if(!n){ putchar('A'); return 0; } char buffer[3]; for(int i=0; i<n; ++i){ scanf("%s", buffer); add_edge(char_int(buffer[0]), char_int(buffer[1])); } make_g2(); // 连通块数目只能有 1 个 int cc = get_cc(); if(cc>1){ printf("No Solution"); return 0; } int st = 0, odd = 0; for(int i=1; i<=52; ++i){ if(g[i].size()&1) ++odd; } // 无奇点时，起点=终点，要使起点字典序最小，st字典序应该最小 if(odd==0){ for(int i=1; i<=52; ++i){ if(g[i].size()){ st = i; break; } } }else if(odd==2){ for(int i=1; i<=52; ++i){ if(g[i].size()&1){ st = i; break; } } // 更多奇点时无解 }else{ printf("No Solution"); return 0; } ans.reserve(n+1); euler(st); // 逆序输出 reverse(ans.begin(), ans.end()); printf("%s", ans.c_str()); return 0; } ``` ### 代码扩展 $n=0$ 时，根据题意，应该输出 $\texttt{A}$，而不是 $\texttt{No Solution}$。经检验，在本题解前，本题解区有且仅有[一个](https://www.luogu.com.cn/article/qhiqg8f4)输出 $\texttt{A}$ 的。 ~~点名批评一下用万能头+`using namespace std;`然后用 `std` 保留字现在没法编译的[题解](https://www.luogu.com.cn/article/pzglmvhy)代码~~，更正方法：所有编译器提示的"引用变量歧义"的变量名字前面加上 `::`。~~和代码格式化错误的[题解](https://www.luogu.com.cn/article/6avtcawe)代码~~，更正方法：慢慢改。~~和用 VC 专有头没删的[题解](https://www.luogu.com.cn/article/83kc02wd)代码~~，更正方法：去掉那一行。~~和放出来的代码吧行数放在开头的[题解](https://www.luogu.com.cn/article/09whnq3e)代码~~，更正方法：慢慢改。~~当时题解区怎么和这一段一样乱~~。 本题测试数据中含有自环。 根据题意，图中不存在孤点，代码中已做处理。 上述代码可以直接处理重边，即对于出现 $k$ 次的无序字母对 $(a,b)$ ，输出的字符串中含有 $k$ 对 $(a,b)$ 。 能不能不判断连通性？如果图连通且欧拉路存在，`ans` 的长度为 $n+1$，图不连通时，`ans` 的长度一定小于 $n+1$，可以借此略过连通性检查，转而检查 `ans` 的长度。 能不能不检查奇点？如果只是判断欧拉路的存在性，使用上面的方法可以处理，但是仍需要用奇点来确定 `st`，至少需要知道每个点是否是奇点。 其它问题请参见代码。