科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇以 leetcode/weekly/211/b/1625.md 这篇题解为主体结合仓库内对应的 Go 实现 与 测试用例完整讲解 LeetCode 第 211 场周赛 T2「执行操作后字典序最小的字符串」1625 题的两大核心技巧用裴蜀定理Bézout 定理推导累加操作可达的最小值以及按 $\gcd(b,n)$ 枚举轮转结果。读完你不仅能独立写出该题的 Python/Java/C/C/Go/JavaScript/Rust 七语言解法还能掌握「取模 数论恒等式」这一类周赛中高频出现的最小字典序问题的通用分析框架。问题描述与前置约定给定一个长度为偶数$n$ 的十进制字符串 $s$仅含数字以及两个正整数 $a$、$b$。可以执行任意次以下两种操作顺序任意、次数任意累加将 $s$ 中所有奇数下标从 $0$ 开始的数字加上 $a$轮转将 $s$ 向右轮转 $b$ 个位置。求经过任意次操作后能够得到的字典序最小的字符串。关于取模的约定题干中「数字一旦超过 $9$ 就会变成 $0$」的意思是数字 $x$ 加上 $a$ 后会变成 $(xa)\bmod 10$。也就是说所有数字始终停留在 $[0,9]$ 区间内这一点是整个推导的基础。不轮转先分析只累加的情况从特殊到一般先考虑只累加、不轮转的情况。为了让字典序尽量小第一个奇数下标 $1$ 上的数字 $s_1$ 越小越好。一旦我们确定了 $s_1$ 的最终值就确定了一共累加的值由于所有奇数下标都要累加同一个数所以也就确定了其余奇数下标的值。因此问题的关键收敛到$s_1$ 最小可以变成多少用两个例子直观感受$s_15,\ a2$变化轨迹为 $5\to 7\to 9\to 1\to 3\to 5\to\cdots$此时 $s_1$ 只能变成奇数最小是 $1$$s_15,\ a3$变化轨迹为 $5\to 8\to 1\to 4\to 7\to 0\to 3\to 6\to 9\to 2\to 5\cdots$此时 $s_1$ 可以变成 $[0,9]$ 中的任意整数最小是 $0$。用裴蜀定理给出严格结论一般地设累加操作执行了 $k\ (k\ge 0)$ 次那么 $s_1$ 变成$$ r (s_1 ak)\bmod 10 $$即存在整数 $q$使得$$ s_1 ak - 10q r $$变形得$$ ak - 10q r-s_1 $$裴蜀定理指出方程 $ak - 10q r-s_1$ 有整数解当且仅当 $r-s_1$ 是 $g\gcd(a,10)$ 的倍数即$$ r \equiv s_1 \pmod g $$其中 $\equiv$ 是同余符号。上式表明$s_1$ 通过累加操作变成的数必须与 $s_1$ 关于模 $g$ 同余所以 $s_1$ 可以变成的最小值为$$ s_1\bmod g $$从 $s_1$ 到 $s_1\bmod g$一共要累加的值为$$ s_1\bmod g - s_1 10 $$其中 $10$ 保证减法结果非负。回到两个例子$a2$ 时 $g\gcd(2,10)2$$5\bmod 21$最小值为 $1$$a3$ 时 $g\gcd(3,10)1$$5\bmod 10$最小值为 $0$。与直观观察完全吻合。枚举轮转到最左边的下标现在把轮转操作也纳入考虑。轮转只会改变字符串的起始位置而字典序的比较是从左到右的所以最靠前的数字越小字典序越小——这决定了我们必须枚举「哪一个下标能轮转到最左边」。例如 $s\texttt{012345}$$b4$执行轮转操作$$ \texttt{012345}\to\texttt{234501}\to\texttt{450123}\to\texttt{012345}\to\cdots $$可以看到只有 $s_0,s_2,s_4$ 可以轮转到最左边。仿照上文的裴蜀定理思路可以轮转到最左边的下标必须是 $\textit{step}\gcd(b,n)$ 的倍数其中 $n$ 是 $s$ 的长度。因此只需枚举$$ i 0,\ \textit{step},\ 2\cdot\textit{step},\ 3\cdot\textit{step},\dots $$作为轮转到最左边的下标。分类讨论奇数下标与偶数下标是否都能累加如果 $\gcd(b,n)$ 是偶数无论如何轮转奇数下标的位置始终是奇数因此我们只能对奇数下标执行累加操作如果 $\gcd(b,n)$ 是奇数轮转一次后原来的偶数下标会变成奇数下标。于是可以先轮转一次、执行累加、再轮转到想要的位置——这等价于我们获得了「对偶数下标执行累加操作」的能力。因此对每个轮转起点 $i$先对奇数下标做累加若 $\textit{step}$ 为奇数再对偶数下标做累加最后与当前最优答案比较取字典序最小者。modify 核心逻辑对某一类下标奇数或偶数整体累加时只需要关注该类下标中最靠前的数字$ch$在字符串最左边、对字典序影响最大$ch$ 能变成的最小值是 $ch\bmod g$$g\gcd(a,10)$从 $ch$ 到 $ch\bmod g$ 需要增加 $\textit{inc}ch\bmod g - ch 10$$10$ 保证非负循环中再 $%10$ 保证结果落在 $[0,9]$其余同奇偶性的下标加上同样的 $\textit{inc}$ 即可因为所有同奇偶下标都共享同一个累加量优化当 $\textit{inc}0$ 时例如 $ch5,g5$$5\bmod 50$ 但 $ch$ 本身已是最小这些下标的值不变无需执行循环。一个验证例子$ch5$$g2$则 $\textit{inc}5\bmod 2 - 5 10 1-5106$$(56)\bmod 101$即 $5$ 经过 $6$ 次累加变成 $1$如注释所述$ch222$模 $10$后变成 $1$不可能变得更小。完整代码七种语言以下解法均遵循「枚举轮转起点 modify 整体累加」的统一框架可直接提交至 LeetCode。class Solution: def findLexSmallestString(self, s: str, a: int, b: int) - str: s list(map(int, s)) n len(s) step gcd(b, n) g gcd(a, 10) ans [inf] def modify(start: int) - None: ch t[start] # 最靠前的数字越小越好 # ch 可以变成的最小值为 ch%g # 例如 ch5g2那么 ch222模 10后变成 1不可能变得更小 # 从 ch 到 ch%g需要增加 inc循环中会 %10 保证结果在 [0,9] 中 inc ch % g - ch if inc: # 优化inc 为 0 时t[j] 不变无需执行 for 循环 for j in range(start, n, 2): t[j] (t[j] inc) % 10 for i in range(0, n, step): t s[i:] s[:i] # 轮转 modify(1) # 累加操作所有奇数下标 if step % 2: # 能对偶数下标执行累加操作 modify(0) # 累加操作所有偶数下标 ans min(ans, t) return .join(map(str, ans))class Solution { public String findLexSmallestString(String S, int a, int b) { char[] s S.toCharArray(); int n s.length; char[] t new char[n]; int step gcd(b, n); int g gcd(a, 10); String ans null; for (int i 0; i n; i step) { // t s[i,n) s[0,i) System.arraycopy(s, i, t, 0, n - i); System.arraycopy(s, 0, t, n - i, i); modify(t, 1, g); // 累加操作所有奇数下标 if (step % 2 0) { // 能对偶数下标执行累加操作 modify(t, 0, g); // 累加操作所有偶数下标 } String str new String(t); if (ans null || str.compareTo(ans) 0) { ans str; } } return ans; } private void modify(char[] t, int start, int g) { int ch t[start] - 0; // 最靠前的数字越小越好 // ch 可以变成的最小值为 ch%g // 例如 ch5g2那么 ch222模 10后变成 1不可能变得更小 // 从 ch 到 ch%g需要增加 inc其中 10 保证 inc 非负循环中会 %10 保证结果在 [0,9] 中 int inc ch % g - ch 10; for (int j start; j t.length; j 2) { t[j] (char) (0 (t[j] - 0 inc) % 10); } } private int gcd(int a, int b) { while (a ! 0) { int tmp a; a b % a; b tmp; } return b; } }class Solution { public: string findLexSmallestString(string s, int a, int b) { int n s.size(); int step gcd(b, n); int g gcd(a, 10); string ans; for (int i 0; i n; i step) { string t s.substr(i) s.substr(0, i); // 轮转 auto modify - void { int ch t[start] - 0; // 最靠前的数字越小越好 // ch 可以变成的最小值为 ch%g // 例如 ch5g2那么 ch222模 10后变成 1不可能变得更小 // 从 ch 到 ch%g需要增加 inc其中 10 保证 inc 非负循环中会 %10 保证结果在 [0,9] 中 int inc ch % g - ch 10; for (int j start; j n; j 2) { t[j] 0 (t[j] - 0 inc) % 10; } }; modify(1); // 累加操作所有奇数下标 if (step % 2) { // 能对偶数下标执行累加操作 modify(0); // 累加操作所有偶数下标 } if (ans.empty() || t ans) { ans move(t); } } return ans; } };int gcd(int a, int b) { while (a) { int tmp a; a b % a; b tmp; } return b; } void modify(char* t, int n, int start, int g) { int ch t[start] - 0; // 最靠前的数字越小越好 // ch 可以变成的最小值为 ch%g // 例如 ch5g2那么 ch222模 10后变成 1不可能变得更小 // 从 ch 到 ch%g需要增加 inc其中 10 保证 inc 非负循环中会 %10 保证结果在 [0,9] 中 int inc ch % g - ch 10; for (int j start; j n; j 2) { t[j] 0 (t[j] - 0 inc) % 10; } } char* findLexSmallestString(char* s, int a, int b) { int n strlen(s); int step gcd(b, n); int g gcd(a, 10); char* ans malloc((n 1) * sizeof(char)); ans[0] CHAR_MAX; ans[1] \0; char* t malloc((n 1) * sizeof(char)); t[n] \0; for (int i 0; i n; i step) { // t s[i,n) s[0,i) strncpy(t, s i, n - i); strncpy(t n - i, s, i); modify(t, n, 1, g); // 累加操作所有奇数下标 if (step % 2) { // 能对偶数下标执行累加操作 modify(t, n, 0, g); // 累加操作所有偶数下标 } if (strcmp(t, ans) 0) { strcpy(ans, t); } } free(t); return ans; }func findLexSmallestString(s string, a int, b int) string { n : len(s) step : gcd(b, n) g : gcd(a, 10) var ans []byte for i : 0; i n; i step { t : []byte(s[i:] s[:i]) // 轮转 modify : func(start int) { ch : t[start] - 0 // 最靠前的数字越小越好 // ch 可以变成的最小值为 ch%g // 例如 ch5g2那么 ch222模 10后变成 1不可能变得更小 // 从 ch 到 ch%g需要增加 inc其中 10 保证 inc 非负循环中会 %10 保证结果在 [0,9] 中 inc : ch%byte(g) 10 - ch for j : start; j n; j 2 { t[j] 0 (t[j]-0inc)%10 } } modify(1) // 累加操作所有奇数下标 if step%2 0 { // 能对偶数下标执行累加操作 modify(0) // 累加操作所有偶数下标 } if ans nil || bytes.Compare(t, ans) 0 { ans t } } return string(ans) } func gcd(a, b int) int { for a ! 0 { a, b b%a, a } return b }var findLexSmallestString function(s, a, b) { const arr s.split().map(ch parseInt(ch)); const n arr.length; const step gcd(b, n); const g gcd(a, 10); let ans null; function modify(t, start) { const ch t[start]; // 最靠前的数字越小越好 // ch 可以变成的最小值为 ch%g // 例如 ch5g2那么 ch222模 10后变成 1不可能变得更小 // 从 ch 到 ch%g需要增加 inc循环中会 %10 保证结果在 [0,9] 中 let inc ch % g - ch 10; if (inc 0) { // 优化inc 为 0 时t[j] 不变无需执行 for 循环 return; } for (let j start; j n; j 2) { t[j] (t[j] inc) % 10; } } for (let i 0; i n; i step) { const t arr.slice(i).concat(arr.slice(0, i)); // 轮转 modify(t, 1); // 累加操作所有奇数下标 if (step % 2) { // 能对偶数下标执行累加操作 modify(t, 0); // 累加操作所有偶数下标 } if (ans null || compareArray(t, ans) 0) { ans t; } } return ans.join(); }; function gcd(a, b) { while (a) { [a, b] [b % a, a]; } return b; } function compareArray(a, b) { const n a.length; for (let i 0; i n; i) { if (a[i] ! b[i]) { return a[i] - b[i]; } } return 0; }impl Solution { pub fn find_lex_smallest_string(s: String, a: i32, b: i32) - String { let n s.len(); let step gcd(b, n as i32) as usize; let g gcd(a, 10) as u8; let mut ans vec![u8::MAX]; let modify |t: mut [u8], start: usize| { let ch t[start] - b0; // 最靠前的数字越小越好 // ch 可以变成的最小值为 ch%g // 例如 ch5g2那么 ch222模 10后变成 1不可能变得更小 // 从 ch 到 ch%g需要增加 inc其中 10 保证 inc 非负循环中会 %10 保证结果在 [0,9] 中 let inc ch % g 10 - ch; for j in (start..n).step_by(2) { t[j] b0 (t[j] - b0 inc) % 10; } }; for i in (0..n).step_by(step) { let mut t format!({}{}, s[i..], s[..i]).into_bytes(); // 轮转 modify(mut t, 1); // 累加操作所有奇数下标 if step % 2 ! 0 { // 能对偶数下标执行累加操作 modify(mut t, 0); // 累加操作所有偶数下标 } ans ans.min(t); } unsafe { String::from_utf8_unchecked(ans) } } } fn gcd(mut a: i32, mut b: i32) - i32 { while a ! 0 { (a, b) (b % a, a); } b }复杂度分析时间复杂度$\mathcal{O}\left(\dfrac{n^2}{\gcd(b,n)}\right)$其中 $n$ 是 $s$ 的长度。轮转起点共有 $n/\gcd(b,n)$ 个每个起点构造字符串并执行两次整体累加至多 $\mathcal{O}(n)$加上同级的字典序比较总体即 $\mathcal{O}(n^2/\gcd(b,n))$。空间复杂度$\mathcal{O}(n)$主要用于保存轮转后的临时字符串。补充注记本题还可以枚举奇数下标的累加值、偶数下标的累加值然后借助最小表示法的思想在固定累加值的情况下计算轮转后的最小字典序时间复杂度可优化到 $\mathcal{O}(D^2n)$其中 $D10$ 是十进制数字的取值范围。本解法的枚举轮转思路更易理解作为周赛 T2 已经足够。仓库实践Go 实现、测试用例与运行方式实现文件仓库中的 leetcode/weekly/211/b/b.go 与题解中的 Go 版本完全一致findLexSmallestString内先计算step : gcd(b, n)与g : gcd(a, 10)再以for i : 0; i n; i step枚举轮转起点闭包modify负责对指定奇偶性的下标整体累加inc最后用bytes.Compare维护字典序最小的答案。文件底部同时给出了手写的gcd实现欧几里得算法循环求余。测试用例与验证leetcode/weekly/211/b/b_test.go 内置了 6 组官方示例覆盖了各种边界形态输入输出5525,a9,b2205074,a5,b1240011,a4,b2001143987654,a7,b300553311593290172167,a7,b4206658319916863376891476,a4,b9005790033890其中0011, 4, 2恰好是「轮转后原字符串已是最优、且累加无法改善」的样例74, 5, 1则是长度 $n2$、$\gcd(b,n)1$ 的最小规模样例。测试文件底部标注了题目出处weekly-contest-211 第 2 题。测试借助仓库自研的通用评测框架 leetcode/testutil/leetcode.go 中的RunLeetCodeFuncWithExamples实现位于该文件 L237该函数通过反射解析函数签名把examples中每行的输入字符串如5525、9、2逐一解析为实参并调用目标函数同时自动检测超时isTLE并比对期望输出targetCaseNum 0时只跑指定用例为0时全量运行。这也体现了仓库「题解 实现 测试」三位一体的组织方式每个周赛目录如 leetcode/weekly/211按 a/b/c/d 存放各题.md题解与.go实现、.go测试同目录放置便于对照阅读。如何运行在仓库根目录下直接执行go test -v ./leetcode/weekly/211/b即可运行上述全部 6 个用例若只想验证单条用例可临时把targetCaseNum设为对应序号-1表示最后一个用例见 leetcode.go 中的说明。该测试框架支持「单个用例失败后继续全量回归」的递归回退逻辑L319-L323方便迭代调试。总结这类题的分析套路LeetCode 1625 是「轮转 累加」双操作求最小字典序的代表题其套路可抽象为三步适用于大量类似题固定轮转、分析累加把第一个关键位置最靠前、影响字典序最大的下标作为突破口用裴蜀定理判断累加操作的可达值集合得出「最小可达值 原值对 $\gcd(a,10)$ 取模」固定累加、枚举轮转轮转可达的起始下标集合由 $\gcd(b,n)$ 决定只需枚举 $n/\gcd(b,n)$ 个起点合并两种操作的能力边界由 $\gcd(b,n)$ 的奇偶性判断偶数下标能否参与累加从而决定是否调用第二次modify。数论在此处的作用是把「可无限重复的取模操作」转化为「同余类」这一简洁表述避免直接模拟无穷状态这也是 copypasta 这类算法竞赛模板库中常把gcd、取模与数论工具独立封装的原因——它们在高频周赛题中反复出现值得单独记忆与复用。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 仓库实战力扣双周赛 168 A 题「反转后字典序最小字符串」的暴力与后缀数组解法codeforces go 仓库实战力扣双周赛 168 A 题「反转后字典序最小字符串」的暴力与后缀数组解法 导读 本文以 leetcode/biweekly科学计算LeetCode-Go 题解 1202并查集求解 Smallest String With Swaps 字典序最小交换字符串LeetCode Go 题解 1202并查集求解 Smallest String With Swaps 字典序最小交换字符串 本文以 LeetCode 第 1示例工程最小表示法全解O(n) 求循环同构字符串的最小字典序 —— 以 LogicStack-LeetCode 仓库 LeetCode 899「有序队列」为例最小表示法全解O n 求循环同构字符串的最小字典序 —— 以 LogicStack LeetCode 仓库 LeetCode 899「有序队列」为例 最小表示教程文档上一篇掌握浏览器Cookie的终极隐私保护方案Get cookies.txt LOCALLY深度指南下一篇3步掌握本地Cookie安全导出Get cookies.txt LOCALLY完全指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考