题目描述一个NNN位循环数runaround number\texttt{runaround number}runaround number具有以下特征它是一个恰好有NNN位的整数每位数字在111到999之间不含000数字形成这样一个序列每个数字指示序列中下一个数字的位置。具体做法是从当前数字开始向右数该数字所表示的位数到达的下一个数字即为序列中的下一个数字。如果必要计数从最右边绕回最左边。数字的最左边是序列的第一个数字序列必须在使用完所有数字恰好一次后返回到这个起始数字数字中不会出现重复数字例如考虑数字813628136281362从最左边的数字888开始8 1 3 6 28\ 1\ 3\ 6\ 281362向右数888位结束于666绕回8 1 3 6 28\ 1\ 3\ 6\ 281362向右数666位结束于2228 1 3 6 28\ 1\ 3\ 6\ 281362向右数222位结束于1118 1 3 6 28\ 1\ 3\ 6\ 281362向右数111位结束于3338 1 3 6 28\ 1\ 3\ 6\ 281362向右数333位结束于888回到起点8 1 3 6 28\ 1\ 3\ 6\ 281362所有555位数字各使用一次后回到了起点因此813628136281362是一个循环数。输入格式输入包含多行每行有一个整数RRR222到777位。最后一行只包含数字000。输出格式对于每个输入数字除了最后的000输出大于等于RRR的最小循环数。样例输入12 123 1234 81111 82222 83333 911111 7654321 0样例输出Case 1: 13 Case 2: 147 Case 3: 1263 Case 4: 81236 Case 5: 83491 Case 6: 83491 Case 7: 913425 Case 8: 8124956题目分析问题的本质这是一个数字生成与搜索问题。需要找到所有满足循环数性质的数字然后对每个查询输出第一个大于等于RRR的循环数。循环数的性质数字不包含000所有数字互不相同从第一位开始按照“向右移动当前数字指示的步数”的规则经过NNN步后恰好回到起点且每个位置都被访问一次搜索策略由于最大位数为777且每位数字为1∼91 \sim 91∼9总搜索空间为所有排列但需要满足上述条件。一种高效的方法是使用深度优先搜索DFS\texttt{DFS}DFS生成所有循环数从第000位最左边开始每次选择一个未使用过的数字计算下一步的位置如果该位置未被访问则继续当所有位置都被访问且回到起点时得到一个循环数预处理由于输入包含多个查询且数字范围有限最多777位可以预先计算所有循环数存入集合中然后对于每个查询使用二分查找lower_bound找到答案。解题思路步骤一DFS\texttt{DFS}DFS生成循环数voiddfs(intdepth,intposition,intlength){if(visited[position])// 如果当前位置已被访问{// 如果已经访问了所有位置且回到了起点position0if(depthlengthposition0)candidates.insert(stoi(digits));}else{// 枚举下一个数字1-9 中未使用过的for(intdigit1;digit9;digit)if(used[digit]false){digits[position]0digit;used[digit]true;visited[position]true;// 递归下一步位置 (当前位置 步数) % 长度dfs(depth1,(positiondigit)%length,length);used[digit]false;visited[position]false;}}}步骤二预先生成所有循环数对于长度lenlenlen从222到777执行DFS\texttt{DFS}DFS生成该长度下的所有循环数。for(intlength2;length7;length){digits.assign(length,0);fill(visited.begin(),visited.end(),false);fill(used.begin(),used.end(),false);dfs(0,0,length);}步骤三查询对于每个输入nnn使用set::lower_bound找到第一个≥n\geq n≥n的循环数。while(cinn,n)coutCase cases: (*candidates.lower_bound(n))endl;参考代码// Run Run Runaround Numbers// UVa ID: 347// Verdict: Accepted// Submission Date: 2016-07-02// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;string digits;// 当前数字字符串setintcandidates;// 存储所有循环数vectorboolused(10);// 数字是否已使用vectorboolvisited(10);// 位置是否已访问// 深度优先搜索生成循环数// depth: 已访问的位置数// position: 当前位置// length: 数字长度voiddfs(intdepth,intposition,intlength){if(visited[position])// 遇到已访问的位置{// 如果所有位置都已访问且回到起点这是一个有效的循环数if(depthlengthposition0)candidates.insert(stoi(digits));}else{// 枚举下一个数字1-9 中未使用过的for(intdigit1;digit9;digit)if(used[digit]false){digits[position]0digit;used[digit]true;visited[position]true;// 下一步位置 (当前位置 步数) % 长度dfs(depth1,(positiondigit)%length,length);used[digit]false;visited[position]false;}}}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);// 预先生成所有 2-7 位的循环数for(intlength2;length7;length){digits.assign(length,0);fill(visited.begin(),visited.end(),false);fill(used.begin(),used.end(),false);dfs(0,0,length);}intn,cases0;while(cinn,n)coutCase cases: (*candidates.lower_bound(n))endl;return0;}