![题解：洛谷 P1467 [USACO2.2] 循环数 Runaround Numbers](http://pic.xiahunao.cn/yaotu/题解：洛谷 P1467 [USACO2.2] 循环数 Runaround Numbers)
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1467 [USACO2.2] 循环数 Runaround Numbers - 洛谷【题目描述】循环数是那些不包括0 00且没有重复数字的正整数比如81362 8136281362并且还应同时具有一个有趣的性质——如果你从最左边的数字开始在8 1362 \color{red}{8}\color{black}136281362中是8 88向右数这个数字对应的次数如果数到了最右边就回到最左边在8 1362 \color{red}{8}\color{black}136281362中是8 88次你会停止在另一个新的数字在8 1362 \color{red}{8}\color{black}136281362中是8 → 1 → 3 → 6 → 2 → 8 → 1 → 3 → 6 \color{red}8\color{black}\to 1\to 3\to 6\to 2\to 8\to 1\to 3\to \color{red}68→1→3→6→2→8→1→3→6如果停在一个相同的数字上这个数就不是循环数。重复这样做如果能在经过每个数位恰好一次后回到最左边那么这个正整数就是循环数。仍然以81362 8136281362为例以下模拟过程证明了81362 8136281362是循环数8 → 1 → 3 → 6 → 2 → 8 → 1 → 3 → 6 \color{red}8\color{black}\to 1\to 3\to 6\to 2\to 8\to 1\to 3\to \color{red}68→1→3→6→2→8→1→3→66 → 2 → 8 → 1 → 3 → 6 → 2 \color{red}6\color{black}\to 2\to 8\to 1\to 3\to 6\to \color{red}26→2→8→1→3→6→22 → 8 → 1 \color{red}2\color{black}\to 8\to \color{red}12→8→11 → 3 \color{red}1\color{black}\to \color{red}31→33 → 6 → 2 → 8 \color{red}3\color{black}\to 6\to 2\to \color{red}83→6→2→8任务给你一个正整数m mm找出最小的比m mm大的循环数m ′ mm′。数据保证m ′ ≤ 2 32 − 1 m \le 2^{32}-1m′≤232−1。【输入】仅仅一行, 包括m mm。【输出】仅仅一行输出最小的比m mm大的循环数m ′ mm′。【输入样例】81361【输出样例】81362【核心思想】问题分析给定正整数m mm要求找到最小的比m mm大的循环数。循环数的定义不含0 00、无重复数字的正整数从最高位开始按当前位数字值向右循环移动到末尾回到开头经过每个数位恰好一次后回到起始位置。算法选择暴力枚举 模拟验证从m 1 m1m1开始逐个枚举对每个数模拟循环数判定过程循环数判定函数包含四个检查条件——不含0 00、无重复数字、模拟移动经过所有位、最终回到起始位关键步骤读入m mm枚举i ii从m 1 m1m1开始递增判定函数find(n)条件 1不含 0将n nn转为字符串若含0返回false条件 2无重复数字用桶数组b[1..9]统计各数字出现次数若存在 1 11返回false条件 3模拟移动初始化mark 0起始位置a数组标记访问状态循环l e n lenlen次l e n lenlen为数字位数a[mark] 1标记当前位已访问mark (mark (s[mark] - 0)) % len计算下一个位置循环结束后检查s[mark] s[0]回到起始位的数字检查a数组是否全为1 11所有位均被访问恰好一次全部满足返回true输出第一个满足find(i)的i ii时间/空间复杂度时间复杂度O ( ( m ′ − m ) ⋅ d ) O((m - m) \cdot d)O((m′−m)⋅d)d dd为数字位数实际循环数密度较高枚举量不大空间复杂度O ( d ) O(d)O(d)字符串和标记数组模拟验证的核心思想循环移动建模用模运算(mark digit) % len实现到末尾回到开头的循环效果访问完整性检查a数组确保每个位置被恰好访问一次防止提前进入小循环回到起点验证循环l e n lenlen次后必须停在起始位的数字上保证路径闭合数字约束前置先排除含0 00和重复数字的数减少无效模拟适用于数字特性模拟、循环路径验证、暴力搜索类问题【解题思路】【算法标签】#普及- #模拟【代码详解】#includebits/stdc.husingnamespacestd;intm,a[35],b[15];// 定义a数组用来存放每个数字的遍历定义b数组用来存放每个数字出现的次数boolfind(intn){memset(a,0,sizeof(a));// 初始化a数组memset(b,0,sizeof(b));// 初始化b数组string sto_string(n);// 将n转为字符串sfor(inti0;is.length();i){// 遍历s字符串if(s[i]0)returnfalse;// 如果其中有字符0则返回false}for(inti0;is.length();i){// 遍历s字符串b[(s[i]-0)];// 使用桶记录每个数字出现的次数}for(inti1;i9;i){// 在1-9中没有0是因为有0就已经退出循环了if(b[i]1)returnfalse;// 如果某个数字的计数大于1说明有重复数字返回false}intmark0;// 其实下标为0for(inti0;is.length();i){// 循环s字符串长度的次数a[mark]1;// 将a数组中对应下标修改为1表示此下标已经遍历过mark(mark(s[mark]-0))%s.length();// 下标加上下标对应的数字的和对长度取余得到新的下标}if(s[mark]!s[0])returnfalse;// 循环完后更新后的mark下标对应的数字如果和开始字符即下标为0的字符相同则符合要求否则返回falsefor(inti0;is.length();i){// 遍历a数组if(a[i]0)returnfalse;// 如果有位置还为0说明对应下标的数字没有被遍历到返回false}returntrue;// 如果以上条件否可以满足则返回true}intmain(){cinm;// 输入mfor(intim1;i1e9;i){// 从m1开始遍历最大数字为1e9if(find(i)){// 判断i是否符合要求coutiendl;// 如果如何要求则输出break;// 并退出循环}}return0;}【运行结果】81361 81362
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1467 [USACO2.2] 循环数 Runaround Numbers - 洛谷【题目描述】循环数是那些不包括0 00且没有重复数字的正整数比如81362 8136281362并且还应同时具有一个有趣的性质——如果你从最左边的数字开始在8 1362 \color{red}{8}\color{black}136281362中是8 88向右数这个数字对应的次数如果数到了最右边就回到最左边在8 1362 \color{red}{8}\color{black}136281362中是8 88次你会停止在另一个新的数字在8 1362 \color{red}{8}\color{black}136281362中是8 → 1 → 3 → 6 → 2 → 8 → 1 → 3 → 6 \color{red}8\color{black}\to 1\to 3\to 6\to 2\to 8\to 1\to 3\to \color{red}68→1→3→6→2→8→1→3→6如果停在一个相同的数字上这个数就不是循环数。重复这样做如果能在经过每个数位恰好一次后回到最左边那么这个正整数就是循环数。仍然以81362 8136281362为例以下模拟过程证明了81362 8136281362是循环数8 → 1 → 3 → 6 → 2 → 8 → 1 → 3 → 6 \color{red}8\color{black}\to 1\to 3\to 6\to 2\to 8\to 1\to 3\to \color{red}68→1→3→6→2→8→1→3→66 → 2 → 8 → 1 → 3 → 6 → 2 \color{red}6\color{black}\to 2\to 8\to 1\to 3\to 6\to \color{red}26→2→8→1→3→6→22 → 8 → 1 \color{red}2\color{black}\to 8\to \color{red}12→8→11 → 3 \color{red}1\color{black}\to \color{red}31→33 → 6 → 2 → 8 \color{red}3\color{black}\to 6\to 2\to \color{red}83→6→2→8任务给你一个正整数m mm找出最小的比m mm大的循环数m ′ mm′。数据保证m ′ ≤ 2 32 − 1 m \le 2^{32}-1m′≤232−1。【输入】仅仅一行, 包括m mm。【输出】仅仅一行输出最小的比m mm大的循环数m ′ mm′。【输入样例】81361【输出样例】81362【核心思想】问题分析给定正整数m mm要求找到最小的比m mm大的循环数。循环数的定义不含0 00、无重复数字的正整数从最高位开始按当前位数字值向右循环移动到末尾回到开头经过每个数位恰好一次后回到起始位置。算法选择暴力枚举 模拟验证从m 1 m1m1开始逐个枚举对每个数模拟循环数判定过程循环数判定函数包含四个检查条件——不含0 00、无重复数字、模拟移动经过所有位、最终回到起始位关键步骤读入m mm枚举i ii从m 1 m1m1开始递增判定函数find(n)条件 1不含 0将n nn转为字符串若含0返回false条件 2无重复数字用桶数组b[1..9]统计各数字出现次数若存在 1 11返回false条件 3模拟移动初始化mark 0起始位置a数组标记访问状态循环l e n lenlen次l e n lenlen为数字位数a[mark] 1标记当前位已访问mark (mark (s[mark] - 0)) % len计算下一个位置循环结束后检查s[mark] s[0]回到起始位的数字检查a数组是否全为1 11所有位均被访问恰好一次全部满足返回true输出第一个满足find(i)的i ii时间/空间复杂度时间复杂度O ( ( m ′ − m ) ⋅ d ) O((m - m) \cdot d)O((m′−m)⋅d)d dd为数字位数实际循环数密度较高枚举量不大空间复杂度O ( d ) O(d)O(d)字符串和标记数组模拟验证的核心思想循环移动建模用模运算(mark digit) % len实现到末尾回到开头的循环效果访问完整性检查a数组确保每个位置被恰好访问一次防止提前进入小循环回到起点验证循环l e n lenlen次后必须停在起始位的数字上保证路径闭合数字约束前置先排除含0 00和重复数字的数减少无效模拟适用于数字特性模拟、循环路径验证、暴力搜索类问题【解题思路】【算法标签】#普及- #模拟【代码详解】#includebits/stdc.husingnamespacestd;intm,a[35],b[15];// 定义a数组用来存放每个数字的遍历定义b数组用来存放每个数字出现的次数boolfind(intn){memset(a,0,sizeof(a));// 初始化a数组memset(b,0,sizeof(b));// 初始化b数组string sto_string(n);// 将n转为字符串sfor(inti0;is.length();i){// 遍历s字符串if(s[i]0)returnfalse;// 如果其中有字符0则返回false}for(inti0;is.length();i){// 遍历s字符串b[(s[i]-0)];// 使用桶记录每个数字出现的次数}for(inti1;i9;i){// 在1-9中没有0是因为有0就已经退出循环了if(b[i]1)returnfalse;// 如果某个数字的计数大于1说明有重复数字返回false}intmark0;// 其实下标为0for(inti0;is.length();i){// 循环s字符串长度的次数a[mark]1;// 将a数组中对应下标修改为1表示此下标已经遍历过mark(mark(s[mark]-0))%s.length();// 下标加上下标对应的数字的和对长度取余得到新的下标}if(s[mark]!s[0])returnfalse;// 循环完后更新后的mark下标对应的数字如果和开始字符即下标为0的字符相同则符合要求否则返回falsefor(inti0;is.length();i){// 遍历a数组if(a[i]0)returnfalse;// 如果有位置还为0说明对应下标的数字没有被遍历到返回false}returntrue;// 如果以上条件否可以满足则返回true}intmain(){cinm;// 输入mfor(intim1;i1e9;i){// 从m1开始遍历最大数字为1e9if(find(i)){// 判断i是否符合要求coutiendl;// 如果如何要求则输出break;// 并退出循环}}return0;}【运行结果】81361 81362
