补题日记：26-1-12

Table of Contents

• 前言：
  
• Problem B1032 NOIP 2002 字符变换
  
  
  • 题目大意：
    
  • WriteUp：
    
  
  
• Problem D1120 [CERC 1995] 小木棍
  
  
  • 题目大意：
    
  • WriteUp：
    
  
  
• 后记：
  

Powered by GhostFace's Emacs.

前言：

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 B1032 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)\) ,其中的 \(可达状态数  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 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  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());    // 预处理：构建跳过相同长度的next数组    nextIdx.resize(totalSticks);    for (int i = 0; i < totalSticks; i++) {        int j = i;        while (j < totalSticks && stickLengths[j] == stickLengths) {            j++;        }        for (int k = i; k < j; k++) {            nextIdx[k] = j;        }        i = j - 1; // 跳过已处理区间    }    // 枚举目标棒长度（必须是totalLength的约数）    for (int targetLen = maxLength; targetLen