企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、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→6
6 → 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→2
2 → 8 → 1 \color{red}2\color{black}\to 8\to \color{red}12→8→1
1 → 3 \color{red}1\color{black}\to \color{red}31→3
3 → 6 → 2 → 8 \color{red}3\color{black}\to 6\to 2\to \color{red}83→6→2→8

任务：

给你一个正整数m mm，找出最小的比m mm大的循环数m ′ m'm′。

数据保证m ′ ≤ 2 32 − 1 m' \le 2^{32}-1m′≤232−1。

【输入】

仅仅一行, 包括m mm。

【输出】

仅仅一行，输出最小的比m mm大的循环数m ′ m'm′。

【输入样例】

81361

【输出样例】

81362

【核心思想】

1. 问题分析：给定正整数m mm，要求找到最小的比m mm大的循环数。循环数的定义：不含0 00、无重复数字的正整数，从最高位开始，按当前位数字值向右循环移动（到末尾回到开头），经过每个数位恰好一次后回到起始位置。

2. 算法选择：

   • 暴力枚举 + 模拟验证：从m + 1 m+1m+1开始逐个枚举，对每个数模拟循环数判定过程
   • 循环数判定函数：包含四个检查条件——不含0 00、无重复数字、模拟移动经过所有位、最终回到起始位

3. 关键步骤：

   • 读入：m mm
   • 枚举：i ii从m + 1 m+1m+1开始递增
   • 判定函数find(n)：
     • 条件 1（不含 0）：将n nn转为字符串，若含'0'返回false
     • 条件 2（无重复数字）：用桶数组b[1..9]统计各数字出现次数，若存在> 1 >1>1返回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

4. 时间/空间复杂度：

   • 时间复杂度：O ( ( m ′ − m ) ⋅ d ) O((m' - m) \cdot d)O((m′−m)⋅d)，d dd为数字位数，实际循环数密度较高，枚举量不大
   • 空间复杂度：O ( d ) O(d)O(d)，字符串和标记数组

5. 模拟验证的核心思想：

   • 循环移动建模：用模运算(mark + digit) % len实现"到末尾回到开头"的循环效果
   • 访问完整性检查：a数组确保每个位置被恰好访问一次，防止提前进入小循环
   • 回到起点验证：循环l e n lenlen次后必须停在起始位的数字上，保证路径闭合
   • 数字约束前置：先排除含0 00和重复数字的数，减少无效模拟
   • 适用于数字特性模拟、循环路径验证、暴力搜索类问题

【解题思路】

【算法标签】

#普及- #模拟

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intm,a[35],b[15];// 定义a数组用来存放每个数字的遍历，定义b数组用来存放每个数字出现的次数boolfind(intn){memset(a,0,sizeof(a));// 初始化a数组memset(b,0,sizeof(b));// 初始化b数组string s=to_string(n);// 将n转为字符串sfor(inti=0;i<s.length();i++){// 遍历s字符串if(s[i]=='0')returnfalse;// 如果其中有字符'0'，则返回false}for(inti=0;i<s.length();i++){// 遍历s字符串b[(s[i]-'0')]++;// 使用桶记录每个数字出现的次数}for(inti=1;i<=9;i++){// 在1-9中（没有0，是因为有0就已经退出循环了）if(b[i]>1)returnfalse;// 如果某个数字的计数大于1，说明有重复数字，返回false}intmark=0;// 其实下标为0for(inti=0;i<s.length();i++){// 循环s字符串长度的次数a[mark]=1;// 将a数组中对应下标修改为1，表示此下标已经遍历过mark=(mark+(s[mark]-'0'))%s.length();// 下标加上下标对应的数字的和，对长度取余，得到新的下标}if(s[mark]!=s[0])returnfalse;// 循环完后，更新后的mark下标对应的数字如果和开始字符，即下标为0的字符相同，则符合要求，否则返回falsefor(inti=0;i<s.length();i++){// 遍历a数组if(a[i]==0)returnfalse;// 如果有位置还为0，说明对应下标的数字没有被遍历到，返回false}returntrue;// 如果以上条件否可以满足，则返回true}intmain(){cin>>m;// 输入mfor(inti=m+1;i<=1e9;i++){// 从m+1开始遍历，最大数字为1e9if(find(i)){// 判断i是否符合要求cout<<i<<endl;// 如果如何要求则输出break;// 并退出循环}}return0;}

【运行结果】

81361 81362