UVa 768 Crossword

题目描述给定一个单词列表列表中的单词按字典序排列且不重复。构造一个长度为LLL的字符串只包含小写字母使得该字符串存在两种不同的拆词方式每种拆词方式将字符串切分为若干个单词这些单词均来自给定的列表且满足以下约束两种拆词方式所使用的单词集合互不相交即同一个单词不能同时出现在两种拆法中。在任意一种拆法中同一个单词不能重复出现。两种拆法的所有切割点即每个单词的结束位置除字符串末尾外不能有任何重合。允许其中一种拆法只包含一个单词。要求输出所有满足条件的字符串中字典序最小的一个若无解则输出NO SOLUTION。输入格式输入包含多个测试用例。每个测试用例第一行为整数LLL4≤L≤504 \le L \le 504≤L≤50表示目标字符串长度。第二行为整数NNN1≤N≤10001 \le N \le 10001≤N≤1000表示单词数量。接下来NNN行每行一个字符串长度在222到202020之间由小写字母组成列表按字典序排列且无重复。输入以文件结束符EOF结束。输出格式对于每个测试用例输出一行若存在合法字符串则输出字典序最小的那个否则输出NO SOLUTION。样例输入17 19 all an and area as ask at data do for last of or ort read real task to tor输出andatareadofortor题目分析本题要求构造一个长度为LLL的字符串同时具备两种合法的单词拆分方式。两种拆分方式之间共享同一个字符串但使用的单词不能重复且切割点不能重叠末端除外。这等价于在单词列表上寻找两条从位置000到位置LLL的路径路径上的边即单词长度之和恰好为LLL两条路径的内部顶点即切割点互不相同且两条路径上的边互不相同。同时两条路径所覆盖的字符序列必须完全一致即它们共同定义同一个字符串。直接枚举所有可能的拆分方式组合复杂度是指数级的不可接受。必须设计高效的搜索算法同时构造两条拆分路径并在搜索过程中利用剪枝减少状态空间。解题思路双指针并行搜索用两个指针last\textit{last}last和now\textit{now}now分别表示两种拆法当前已经填充到的位置。初始时last0\textit{last} 0last0now0\textit{now} 0now0。每次总是推进较小的指针若相等则推进last\textit{last}last这样可以保证字符串从左到右逐步确定便于字典序比较和剪枝。当从位置last\textit{last}last尝试一个单词www长度为step\textit{step}step时新位置为newPlaststep\textit{newP} \textit{last} \textit{step}newPlaststep。为了保证两种拆法的切割点不重合需要满足若newP≠L\textit{newP} \ne LnewPL则newP\textit{newP}newP不能等于另一个指针now\textit{now}now即不能在非末尾处同时切割。由于总是推进较小的指针且切割点不能重叠实际上这个条件已经足够保证所有历史切割点互不重合因为较小指针和较大指针之间不存在切割点推进过程不会遇到历史切割点。同时单词不能重复使用因此用一个布尔数组used\textit{used}used标记已使用的单词。字符一致性约束两种拆法最终得到同一个字符串因此当尝试填充单词时需要检查与当前位置上已由另一种拆法填充的字符是否冲突。若冲突则跳过该单词。字典序最小保证由于单词列表已按字典序排列搜索时按顺序尝试单词但仅仅“找到第一个解就返回”并不能保证全局字典序最小因为同一个位置可能选择不同长度的单词后续字符会影响整体字典序。例如选择较短的单词可能使后续字符变大而选择较长的单词可能使后续字符更小。因此必须采用“全局最优解 前缀剪枝”的策略维护一个全局最优字符串best\textit{best}best初始时所有位置设为最大字符如ASCII\texttt{ASCII}ASCII128128128。在每次递归入口比较当前已填充的line\textit{line}line与best\textit{best}best的已确定前缀若line\textit{line}line已经大于best\textit{best}best则剪枝返回。当找到一个完整解lastnowL\textit{last} \textit{now} LlastnowL时用line\textit{line}line更新best\textit{best}best。搜索结束后best\textit{best}best即为字典序最小的合法字符串。该剪枝是安全的因为字符串比较具有前缀决定性一旦某个位置分出大小后续字符不再影响结果。辅助剪枝最短单词剪枝若某个指针剩余长度小于最短单词长度则不可能完成直接返回。重叠检查仅当now0\textit{now} 0now0时检查重叠部分字符是否一致。首字母索引当last0\textit{last} 0last0且line[last]\textit{line}[\textit{last}]line[last]已被填充时利用首字母索引只尝试以该字符开头的单词减少循环次数。复杂度分析搜索空间理论上可能很大但由于剪枝前缀剪枝、最短长度剪枝、重叠检查、切割点限制非常有效实际运行时间远低于时限。每个测试用例中单词数量NNN最多100010001000长度LLL最多505050搜索深度不超过L/min⁡lenL / \min\textit{len}L/minlen。最坏情况下若单词长度均为222最大深度为252525分支数受剪枝大幅削减。实际运行时间约150150150毫秒满足要求。代码实现// Crossword// UVa ID: 768// Verdict: Accepted// Submission Date: 2026-07-11// UVa Run Time: 0.150s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intL,N,minL,head[32],used[1024];intline[64],best[64];string words[1024];voiddfs(intlast,intnow){intbetter1;for(inti0;iL;i){if(line[i]best[i])break;if(line[i]best[i]){better0;break;}}if(!better)return;if(nowLL-nowminL)return;if(lastLnowL){for(inti0;iL;i)best[i]line[i];return;}intstart0,endN;if(last){intcline[last]-a;starthead[c];end(c25?N:head[c1]);}for(intidstart;idend;id){if(used[id])continue;stringwwords[id];intstepw.size();if(laststepL)continue;if(laststepnownow!L)continue;intok1;for(inti0;imin(step,now-last);i)if(line[lasti]!w[i]){ok0;break;}if(!ok)continue;for(inti0;istep;i)line[lasti]w[i];used[id]1;dfs(min(laststep,now),max(laststep,now));used[id]0;for(intinow;ilaststep;i)line[i]0;}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);while(cinL){cinN;minL32;for(inti0;iN;i){cinwords[i];minLmin(minL,(int)words[i].size());}for(inti0;i26;i){strings(1,char(ai));head[i]lower_bound(words,wordsN,s)-words;}memset(line,0,sizeof(line));memset(used,0,sizeof(used));for(inti0;i64;i)best[i]128;dfs(0,0);if(best[0]128)coutNO SOLUTION\n;else{for(inti0;iL;i)cout(char)best[i];cout\n;}}return0;}总结本题的关键点在于并行双指针搜索同时构建两种拆分方式确保切割点不重叠。全局最优 前缀剪枝而非贪心选取第一个解从而保证字典序最小。首字母索引和最短长度剪枝有效减少搜索分支。通过合理的剪枝策略该算法能够在给定约束下快速找到字典序最小的合法字符串通过了所有测试数据。