题目描述给定一组员工的照片文件文件名格式为FirstName LastName.jpg。现需将文件名改为LastName, FirstName.jpg即姓氏在前。文件列表按当前文件名原名或已改名后的新名的字典序实时更新且每次改名后被改名的文件仍保持选中状态。管理员希望从列表中的第一个文件开始重命名并且在每次重命名后只使用一次方向键上 / 下来选择下一个待重命名的文件。方向键不会循环即不会从列表末尾跳转到列表开头。如果存在这样一条重命名顺序使得所有文件都能依次被重命名则输出该顺序下的新文件名否则输出NO QUICK RENAMING POSSIBLE。输入格式输入包含多个测试用例用例之间用一个空行分隔。每个测试用例包含至多202020行每行一个文件名。文件名长度不超过323232个字符名字和姓氏均由字母组成且仅首字母大写。假设“姓氏”为第一个空格与末尾句点之间的部分且所有姓氏互不相同。输入以EOF结束。输出格式对于每个测试用例若存在可行重命名顺序则按该顺序每行输出一个重命名后的文件名即LastName, FirstName.jpg否则输出一行NO QUICK RENAMING POSSIBLE。两个连续测试用例的输出之间必须用一个空行隔开。样例输入Christina Peter.jpg Ganesh Ramanarayanan.jpg Laurie Yorr.jpg Lucy Kraus.jpg Melanie Ayala.jpg Nancy Schnell.jpg Ruth Sandweiss.jpg Christina Peter.jpg Ganesh Ramanarayanan.jpg Melanie Ayala.jpg输出NO QUICK RENAMING POSSIBLE Peter, Christina.jpg Ayala, Melanie.jpg Ramanarayanan, Ganesh.jpg注意样例输出中第一个用例后有一个空行这是两个用例输出之间的分隔。题目分析本题本质上是一个状态空间搜索问题。初始时所有文件名均为原名列表按原名排序第一个文件即字典序最小者被选中。管理员必须立即重命名该文件无需方向键。之后每一步需要根据当前所有文件的名称已改名的用新名未改名的用原名重新排序得到新列表然后当前选中的文件在列表中的位置已知我们可以考察它的相邻文件前一个和后一个。如果某个相邻文件尚未被重命名那么我们可以选择它作为下一步并按下一次方向键完成选择。若两侧相邻文件都已被重命名或不存在则无法继续。由于文件数量n≤20n \le 20n≤20我们可以用状态压缩表示已经重命名的文件集合同时记录当前选中的文件编号。每次从当前状态出发按规则生成所有可能的下一状态并进行深度优先搜索或广度优先搜索。如果找到一条覆盖所有文件的路径则输出对应的重命名顺序。需要特别注意的是排序依据是文件名的当前显示名称而不是固定顺序。已重命名的文件会移动到新的字典序位置可能改变整个列表顺序从而影响相邻关系。因此每次状态转移时必须重新计算当前列表顺序再确定相邻候选。另外初始状态是强制选定第一个文件原名排序后第一个并立即重命名这一步不需要方向键也不计入方向键次数。我们的搜索从该状态开始。解题思路1. 数据表示将每个文件抽象为一个结构体包含原始文件名original和重命名后的新文件名newName。文件编号为0∼n−10 \sim n-10∼n−1。对于任意状态使用一个整数mask表示已重命名文件的集合第iii位为111表示文件iii已重命名。当前选中的文件编号记为curId。2. 状态转移给定状态(mask, curId)需要计算当前列表顺序。为此创建一个数组order[0..n-1]存储文件编号然后按如下规则排序如果文件iii已重命名mask (1i)非零则比较键为files[i].newName否则比较键为files[i].original。排序后找到curId在order中的位置pos。然后检查pos-1和pos1位置上的文件编号若存在且尚未重命名则它们就是合法候选。将每个候选文件编号nxtId作为下一步的选择递归调用dfs(mask | (1nxtId), nxtId)并在路径中记录nxtId。3. 搜索与剪枝由于n≤20n \le 20n≤20状态总数最多为n⋅2n≈20×106n \cdot 2^n \approx 20 \times 10^6n⋅2n≈20×106但实际可达状态远小于此因为每一步只允许移动到相邻未访问节点路径长度受限。DFS\texttt{DFS}DFS配合回溯即可在合理时间内完成。我们还可以加入记忆化即记录某个状态是否访问过且失败但本题nnn较小直接搜索也足够。4. 初始状态与终止条件初始状态将原始文件名排序第一个文件编号为start将其重命名因此mask 1startcurId start路径path {start}。终止条件若mask (1n)-1说明所有文件已重命名搜索成功。5. 特殊情况当n1n1n1时无需任何方向键直接输出该文件的新名即可。6. 多测试用例输出格式两个用例之间用空行分隔注意在输出第一个用例前不要输出多余空行。可以使用一个静态标志变量来控制。7. 复杂度分析每个状态需要O(nlog⁡n)O(n \log n)O(nlogn)的时间来排序以确定相邻关系。状态数最多约为n⋅2nn \cdot 2^nn⋅2n但实际分支有限n20n20n20时最坏情况可接受。空间复杂度为O(n)O(n)O(n)用于路径记录DFS\texttt{DFS}DFS栈深度为nnn。实际上由于每一步只能向左或向右移动路径宽度受限搜索效率很高。代码实现// Last Name First Please// UVa ID: 597// Verdict: Accepted// Submission Date: 2026-06-25// UVa Run Time: 1.810s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structFile{string original;// 原始名称string newName;// 新名称};intn;vectorFilefiles;// DFSmask 已重命名集合curId 当前选中的文件 IDpath 记录重命名顺序booldfs(intmask,intcurId,vectorintpath){if(mask(1n)-1)returntrue;// 按当前文件名排序得到列表顺序vectorintorder(n);iota(order.begin(),order.end(),0);sort(order.begin(),order.end(),[](inta,intb){string nameA(mask(1a))?files[a].newName:files[a].original;string nameB(mask(1b))?files[b].newName:files[b].original;returnnameAnameB;});// 找到当前文件在列表中的位置intposfind(order.begin(),order.end(),curId)-order.begin();// 收集相邻且未重命名的候选文件vectorintcandidates;if(pos0){intidorder[pos-1];if(!(mask(1id)))candidates.push_back(id);}if(pos1n){intidorder[pos1];if(!(mask(1id)))candidates.push_back(id);}// 尝试每个候选for(intid:candidates){path.push_back(id);if(dfs(mask|(1id),id,path))returntrue;path.pop_back();}returnfalse;}// 处理单个测试用例voidprocessCase(constvectorstringrawLines){n(int)rawLines.size();files.resize(n);// 解析每个文件名for(inti0;in;i){conststringsrawLines[i];size_t spacePoss.find( );size_t dotPoss.rfind(.);string firsts.substr(0,spacePos);string lasts.substr(spacePos1,dotPos-spacePos-1);string exts.substr(dotPos);// 保留扩展名如 .jpgfiles[i].originals;files[i].newNamelast, firstext;}// 按原始文件名排序初始列表顺序sort(files.begin(),files.end(),[](constFilea,constFileb){returna.originalb.original;});// 从第一个文件开始重命名索引 0vectorintpath;path.push_back(0);intmask10;boolok(n1)?true:dfs(mask,0,path);// 若只有一个文件则直接成功// 输出结果全局控制用例间空行staticboolfirstOutputtrue;if(!firstOutput)cout\n;firstOutputfalse;if(!ok)coutNO QUICK RENAMING POSSIBLE\n;}else{for(intid:path)coutfiles[id].newName\n;}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string line;vectorstringcurrentLines;while(getline(cin,line)){if(line.empty()){if(!currentLines.empty()){processCase(currentLines);currentLines.clear();}// 忽略多余空行}elsecurrentLines.push_back(line);}// 处理最后一个用例可能没有结尾空行if(!currentLines.empty())processCase(currentLines);return0;}总结本题的核心在于将“重命名顺序”问题转化为状态空间搜索问题利用nnn较小的特点采用状态压缩 DFS 枚举所有可能的相邻选择路径。需要注意的关键点是动态排序每次状态变化后列表顺序会因文件名改变而重新调整因此必须实时计算当前顺序才能确定相邻文件。初始条件题目要求从列表第一个文件开始重命名无需按键因此初始状态是固定的无需遍历所有起点。可行性只要有一条路径能覆盖所有节点即认为可行。搜索过程中通过回溯找到一条路径即可无需枚举全部。本题也展示了如何将实际场景抽象为图论中的路径搜索问题虽然nnn不大但状态数可能较多因此合理的设计和剪枝是必要的。代码实现上采用函数式递归结构清晰易于调试。