AcWing 1366. 循环数
原题链接
中等
作者:
sy123
,
2021-01-26 18:14:57
,
所有人可见
,
阅读 378
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int m, ans = 1e9;
string path;
bool st[N], used[N];
int Stoi(string x){
int res;
stringstream ss;
ss<<x;
ss>>res;
return res;
}
bool check()
{
memset(used,0,sizeof used);
int n=path.size();
int t=0;
int x;
for(int i=0;i<path.size()-1;i++){//循环这么多次
x=path[t]-'0';
t=(t+x)%n;
if(used[t])return false;
used[t]=true;
}
x=path[t]-'0';
t=(t+x)%n;
if(used[t]||t!=0)return false;//特判最后一个数
return true;
}
void dfs(int u)
{
if (path.size()) {
int t=Stoi(path);
if(check()&&t>m)ans=min(ans,t);
}
//暴力枚举所有方案合法的大概就是几十万种
for (int i = 1; i <= 9; ++i){
if(!st[i]){
path += i+'0';
st[i]=true;
dfs(u + 1);
path.pop_back();//回溯
st[i]=false;//回溯
}
}
}
int main()
{
cin >> m;
dfs(0);
cout<<ans<<endl;
return 0;
}