补题日记：26-1-12-洪萨配资

前言：
Problem B:P1032 NOIP 2002 字符变换
1. 题目大意：
2. WriteUp：
Problem D:P1120 [CERC 1995] 小木棍
1. 题目大意：
2. WriteUp：
后记：

前言：

Ctorch诞生的第178天，小小的庆祝一下。

厚颜无耻的宣传我们团队的项目：https://github.com/ShengFlow/CTorch/tree/feature-nn.Module

这是一次比赛的赛后补题记录&题解（Part 1，因为全部的题目太多了，我准备分两篇）。

主要涉及到的算法就是搜索，但是需要一些技巧才能全部AC。

推荐几篇本人的文章：

1.设计LUTM时与Deepseek的对话：https://chat.deepseek.com/share/wednovjlp5sa013j4q
2.文章：《恭喜自己，挑战成功》————CSP-J省一获奖感言：https://www.cnblogs.com/SilverGo/p/19223328
3.文章：《逆袭导论·初中生的宝书》：https://www.cnblogs.com/SilverGo/p/19284999
4.文章：《矩阵乘法优化》：https://www.cnblogs.com/SilverGo/p/19019364
5.Ctorch的github：https://github.com/ShengFlow/CTorch/tree/feature-nn.Module?tab=contributing-ov-file

本文由 Emacs 29.0 Org-mode 写成，在此感谢GNU做出的开源软件运动。

Problem B:P1032 NOIP 2002 字符变换

难度：普及+

题目大意：

给出\(A,B\)两个字符串，\(N\)个变换规则，其中\(A.len,B.len \leq 20\)，\(N \leq 6\).

WriteUp：

其实赛时跳过这道题的主要原因是本蒟蒻看到了几道更可做的题目，因此就先跳过了。

以下是题解：
显然，由于我们有深度限制，使用广搜是更好的选择，我们只需要使用一个变量记录当前深度就可以，而且不会丢解。

又因为BFS的特性，第一次找到的解一定是最优解。

简单做一下复杂度分析，我们就会发现：
1.朴素BFS的复杂度为\(O((L \cdot M)^{10})\)（当然，不精确，精确的复杂度如下：首先，我们定义\(b = \Theta(L \cdot M)\),随后，整体的复杂度就是\(O(b^{10})\)）.

2.上述的上界是很悲观的，事实上，由于种种限制，我们的复杂度将远低于\(O(b^{10})\)，而是近似于\(O(可达状态数 \times L \times M)\),其中的\(可达状态数 << b^{10}\).

3.双向BFS的上界为\(O((L \cdot M)^{5})\),显然使用双向BFS会更优，然而，在该题的低强度数据下，朴素BFS加上一些卡常是可以AC的。

常见的技巧：

使用STL可以大幅缩短代码复杂度（另外，貌似普遍认为STL的性能不如手写的好，实际上，STL的算法都是经过精细打磨的，除非是非常小的数据规模，一些常数因子几乎可以忽略不计）。
在使用双向BFS时，一般是选择较小一侧扩展（这一点在《信息学奥赛一本通·提高篇》中有详细的讲解，很推荐大家阅读）。
推荐大家研究一些STL的代码，比较出名的就是STL的 sort 函数，这不是普通的排序，它结合了快排、堆排、插入排序等算法，确保不会出现纯快排的最坏情况。
良好的码风很重要，具体来讲：
变量名清晰、注释完善、易读、冷热代码分区（这一点在OI Wiki中有讲到，这样做可以便于编译器优化）、简化实现（如使用lambda函数）、“一个函数只做好一件事”（俗称的「GNU开发准则」）。
基于范围的 for 很好用，尤其是在STL容器的遍历中，省时省力，但是请注意，仅适用于0-based下标（即从0开始的下标）。

代码如下：

/* by 01130.hk - online tools website : 01130.hk/zh/urlthunder.html */ #include <bits/stdc++.h> using namespace std; struct Node { string s; int step; }; queue<Node> q[2]; unordered_map<string, int> vis[2]; int extend(int dir, vector<pair<string,string>>& rules) { Node cur = q[dir].front(); q[dir].pop(); for (auto& r : rules) { string from = dir ? r.second : r.first; string to = dir ? r.first : r.second; size_t pos = 0; while ((pos = cur.s.find(from, pos)) != string::npos) { string nxt = cur.s.substr(0, pos) + to + cur.s.substr(pos + from.length()); if (nxt.length() > 20) { ++pos; continue; } if (vis[dir].count(nxt)) { ++pos; continue; } if (vis[1-dir].count(nxt)) { return cur.step + 1 + vis[1-dir][nxt]; } vis[dir][nxt] = cur.step + 1; q[dir].push({nxt, cur.step + 1}); ++pos; } } return -1; } int main() { string A, B; cin >> A >> B; vector<pair<string,string>> rules; string a, b; while (cin >> a >> b) rules.push_back({a, b}); q[0].push({A, 0}); vis[0][A] = 0; q[1].push({B, 0}); vis[1][B] = 0; while (!q[0].empty() && !q[1].empty()) { // 选择较小一侧扩展 if (q[0].size() > q[1].size()) { int ans = extend(1, rules); if (ans != -1 && ans <= 10) { cout << ans; return 0; } else if (ans > 10) break; } else { int ans = extend(0, rules); if (ans != -1 && ans <= 10) { cout << ans; return 0; } else if (ans > 10) break; } } cout << "NO ANSWER!"; return 0; }

Problem D:P1120 [CERC 1995] 小木棍

难度：提高+/省选（但是本人觉得也就是个普及）

题目大意：

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 50 。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

WriteUp：

一些简要的经验、分析：

这道题目的正解就是DFS（但是需要很多剪枝）。
纯DFS会TLE（我之前曾经在loj上做过这道题目）。
这道题在《一本通提高篇》中有，而且是例题。
即便是加入了各种优化，也不会AC（不知道有没有大佬做出AC的解法，至少本蒟蒻的没有AC）。

一般来说，一道搜索的题目会先考虑问题的维度。
为什么呢，我们入门搜索时，一般都是什么「子集」、「马的遍历」等题目。

很明显，我们事实上是在移动一个“高维空间中的点”（你也可以理解为高维向量），一旦这个点坐标满足我们所说的「解的要求」，那么这就是一个解。

子集就是在移动一个可变集合，里面的元素就是已经选择的，每次更新其中的一个元素，就是移动了该点，改变了这个点的坐标。

对于这道题，我们就是在移动一个点，它的坐标就是选择的各个木棍（做一下离散化，事实上，坐标是选择的各个木棍的序号）。

那么解的条件自然就是：得到的原始木棍一样长，我们需要在这些解中找到最短的一个。

那么是否每个点都应该探索一下呢，显然不是的。
我们可以排除一些不会影响最终答案的点（或者说「空间」），降低复杂度。
这就是「剪枝」：剪去搜索树中一些不会产生最优解的枝条（子树），同样，也是去除一些不必要的搜索状态空间。
这两种理解方式没有优劣，但是结合起来能更好的理解搜索的本质，也方便对搜索进行改造。

什么样的点不需要探索呢？

我们需要在dfs外枚举可能的原始木棍长度，那么它的范围是什么呢（这种通过减少搜索范围的剪枝，称作「上下界剪枝」）。
显然，最小是最长的一根木棍（此时这根木棍恰好是原来的一根木棍）；而最多是所有木棍的长度之和。
当原始长度不能被所有木棍的长度之和整除时，我们跳过；（这种通过跳过一些不可行的方案的剪枝，称作「可行性剪枝」）。
短的木棍更灵活，更容易凑出目标长度，因此我们将木棍降序排序；（这个不算是剪枝，优化的一种，称为「优化搜索顺序」）。
假如目前的dfs刚刚尝试了长度为\(m\)的木棍无法完成拼接，那么下一个长度为\(m\)的木棍仍然无法完成，跳过所有的这个长度的木棍；（这种方法称为「排除等效冗余」）
由于我们的目标长度是由小到大枚举的，因此只要找到解就可以直接返回，此时一定是最优解（这种跳过一些不优的解的剪枝，称作「最优性剪枝」）。
输入时忽略长度大于50的木棍。

加上如上的6个剪枝后，便能够通过本题，代码如下：

/* by 01130.hk - online tools website : 01130.hk/zh/urlthunder.html */ #include <bits/stdc++.h> int totalSticks; // 木棍总数 std::vector<int> stickLengths; // 木棍长度列表 std::vector<bool> used; // 使用标记 std::vector<int> nextIdx; // 跳过相同长度的优化数组 int totalLength = 0; // 木棍总长度 int maxLength = 0; // 最长单根木棍 int numTargetSticks = 0; // 目标棒数量 int bestAnswer = INT_MAX; // 最优解 bool foundSolution = false; // 是否已找到解 // DFS搜索 // @param completed: 已完成的棒子数量 // @param lastIdx: 从哪个木棍索引开始尝试 // @param targetLen: 目标棒长度 // @param currentLen: 当前棒已拼长度 void dfs(int completed, int lastIdx, int targetLen, int currentLen) { // 剪枝1: 成功完成所有棒子 if (completed == numTargetSticks - 1) { bestAnswer = std::min(bestAnswer, targetLen); foundSolution = true; return; } // 剪枝2: 当前棒已拼完，开始下一根 if (currentLen == targetLen) { dfs(completed + 1, 0, targetLen, 0); return; // 重要：必须return，避免继续循环 } // 尝试拼接 for (int i = lastIdx; i < totalSticks && !foundSolution; ) { if (!used[i] && currentLen + stickLengths[i] <= targetLen) { // 选择当前木棍 used[i] = true; dfs(completed, i + 1, targetLen, currentLen + stickLengths[i]); // 回溯 used[i] = false; if (foundSolution) return; // 剪枝3: // - 如果当前棒为空，这根木棍无法用，后面的更短也无法用 // - 如果这根木棍正好填满当前棒但失败，说明此路不通 if (currentLen == 0 || currentLen + stickLengths[i] == targetLen) { return; } i = nextIdx[i]; // 跳过相同长度的木棍 } else { i++; } } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; if (!(std::cin >> n)) return 0; stickLengths.reserve(70); // 读取输入，过滤过长木棍 for (int i = 0; i < n; i++) { int len; std::cin >> len; if (len > 50) continue; // 单根木棍不超过50 stickLengths.push_back(len); totalLength += len; maxLength = std::max(maxLength, len); } totalSticks = stickLengths.size(); used.resize(totalSticks, false); // 从长到短排序，优先尝试长木棍 std::sort(stickLengths.begin(), stickLengths.end(), std::greater<int>()); // 预处理：构建跳过相同长度的next数组 nextIdx.resize(totalSticks); for (int i = 0; i < totalSticks; i++) { int j = i; while (j < totalSticks && stickLengths[j] == stickLengths[i]) { j++; } for (int k = i; k < j; k++) { nextIdx[k] = j; } i = j - 1; // 跳过已处理区间 } // 枚举目标棒长度（必须是totalLength的约数） for (int targetLen = maxLength; targetLen <= totalLength; targetLen++) { if (totalLength % targetLen != 0) continue; numTargetSticks = totalLength / targetLen; std::fill(used.begin(), used.end(), false); foundSolution = false; dfs(0, 0, targetLen, 0); if (foundSolution) break; } std::cout << bestAnswer << '\n'; return 0; }

P.S. 上面代码中使用了一些奇怪的注释：如“// @param completed:”，这是Doxygen注释，广泛使用于大型软件项目，用于自动生成项目文档，不过这种代码没必要使用，这是作者习惯。

另外，这种风格的代码极其类似AI的代码风格，因此，锻炼码风的一个好方法就是跟着AI学习，这也是本蒟蒻使用的训练方法。