USACO备考冲刺必刷题 | P1467 Runaround Numbers

学习C++从娃娃抓起！记录下USACO（美国信息学奥赛）备考学习过程中的题目，记录每一个瞬间。

附上汇总贴：USACO备考冲刺必刷题 | 汇总-CSDN博客

【题目描述】

循环数是那些不包括 0 且没有重复数字的整数（比如 81362）并且还应同时具有一个有趣的性质, 就像这个例子:

如果你从最左边的数字开始（在这个例子中 8）向右数最左边这个数（如果数到了最右边就回到最左边），你会停止在另一个新的数字（如果停在一个相同的数字上，这个数就不是循环数）。

就像：8 1 3 6 2 从最左边接下去数 8 个数字: 1 3 6 2 8 1 3 6 所以下一个数字是 6

重复这样做 (这次从 6 开始数 6 个数字) 并且你会停止在一个新的数字上: 2 8 1 3 6 2, 也就是 2

再这样做 (这次数两个): 8 1

再一次 (这次一个): 3

又一次: 6 2 8

这时你回到了起点,在经过每个数字一次后回到起点的就是循环数。如果你经过每一个数字一次以后没有回到起点, 你的数字不是一个循环数。

给你一个数字 m ，找出第一个比 m 大的循环数, 输出数据保证结果能用一个无符号长整型数 ∈[0,2^32) 装下。 （追加提醒：循环数每个数位都必须要访问到）

【输入】

仅仅一行, 包括 m。

【输出】

仅仅一行，输出第一个比 m 大的循环数。

【输入样例】

81361

【输出样例】

81362

【代码详解】

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

【运行结果】

81361
81362