USACO-2-2-3-Runaround-模拟

感觉到这里其实到自己的瓶颈了，每一道题都要想一段时间才能做出来。

这道题挺暴力的，让我比较意外。毕竟上面刚刚一道01背包求方案数233。 不过为什么暴力能过，我还是想了挺久的。

题意: 挺难描述的，这里贴洛谷的翻译(应该是nocow翻译过来的) >循环数是那些不包括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 (在1到9位之间), 找出第一个比 M大的循环数, 输出数据保证结果能用一个无符号长整型数（21亿）装下。 >（追加提醒：循环数每个数位都必须要访问到）

---

一开始想了下暴力。 然后如何判断一开始觉得直接模拟太麻烦了，于是考虑了一下。 错误的以为，是对每位数都执行这样的操作，然后计算出来操作后得到的下标。只要下标互不重复，也就表示是循环数了。

于是进一步想过后得到，对于第\(i\)个数而言，只要$ ( i + a_{i-1} ) % n $ 各不相同(应该算是一个完全剩余系？)，就可以了。

于是只要注意( i - 1 < 0 ) ? ( a.size() - 1 ) : ( i - 1 ) 就可以了。

虽然在当时很快想到了这个如何去检测一个数字是否是循环数的比较好写的写法，但是一直有一个问题困扰着我。

就是答案中暗示可能数据有\(2e9\)那么大，那么会不会出现连续\(1e9\)个数字里都找不到满足条件的数导致超时？

想了很久，没什么头绪。 只是想的是，如果遍历\(1e5\)，大概有6位就会被遍历了，改变对于9位数来说也有不少了，那么会不会出现不了这种情况呢？

因为不会证明。

于是就按这个想法交了一发。 发现WA了。

WA的数据是\(738192\). 如果按题目中要求，会是一个不停在7和1中循环的数列，无法遍历到其他数中。但是按照我的想法，却会是成立的。

于是最后还是得暴力模拟。 模拟主要方法就是，有多少位模拟多少次， 然后最后在统计一下有没有重复出现过的下标或者没出现过的下标即可。

提交后，竟然A了。

---

事后发现自己想多了。

这道题时间复杂度应该是 \(O(9!)\) ， 因为是各不相同且没有\(0\)的数字，所以应该去生成全排列。而不是逐一枚举。 逐一枚举的话，时间复杂度就是玄学了。

代码：

code

 
/*
ID:xiekeyi1
PROG:runround
LANG:C++
*/

#include<bits/stdc++.h>
using namespace std ;

typedef long long ll ; 

bool judge( ll n )
{
    int digit = 0 ;
    ll t = n ;
    while( t != 0 )
        t /= 10 , digit++; // 计算位数
    
    vector<ll> a ;

    // 计算是否有重复和和0
    int d[10] = {0} ; 
    for( int i = digit - 1 ; i >= 0 ; i-- )
    {
        int t =  static_cast<int> ( ( n /  pow( 10 , i )  ) )   % 10 ; 
        if(  d[t] != 0 || t == 0 )
            return false ;
        else
        {
            d[t]++;
            a.push_back( t ) ; 
        }
    }

    // 模拟
    int tt =  0 ; 
    int b[15] = {0} ; 
    for( int i = 1 ; i <= digit ; i++)
    {
        tt = ( a[  ( tt - 1 < 0 ) ? ( a.size() - 1 ) : ( tt - 1 ) ] +  tt ) % digit ; 
        b[a[tt]]++;
    }

    for( int i = 0 ; i < a.size() ; i ++ )
    {
        if( b[ a[i] ] != 1 )
            return false ;
    }
    return true ;
}
int main()
{
    freopen("runround.in","r",stdin);
    freopen("runround.out","w",stdout);
    ll m ;
    cin >> m ;
    m++;
    while( true )
    {
        if( judge( m ) )
        {
            cout << m << endl ; 
            return 0 ;
        }
        else
            m++;
    }
    return 0; 
}