题意:给出n到m的范围,求出一个数在前i位数组成的数字能被i整除。假设存在输出这个数,假设不存在。输出-1.
思路:回溯,每次放第i位,然后推断是否符合题意。这题踩着时间过去的2.6s(看了下别人的题解。能够降低取模次数来节省时间)。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 35; int arr[MAXN]; int n, m, flag; int mod(int d) { int sum = 0; for (int i = 0; i < d; i++) { sum = (sum * 10 + arr[i]) % d; } return sum; } int dfs(int cur) { if (cur == m) return true; for (int i = 0; i <= 9; i++) { arr[cur] = i; if (cur < n - 1 || (cur >= n - 1 && !mod(cur + 1))) { if (dfs(cur + 1)) return true; } } return false; } int main() { int cas, t = 1; scanf("%d", &cas); while (cas--) { scanf("%d%d", &n, &m); flag = 0; for (int i = 1; i <= 9; i++) { arr[0] = i; if (dfs(1)) { flag = 1; break; } } printf("Case %d: ", t++); if (flag) { for (int i = 0; i < m; i++) printf("%d", arr[i]); printf(" "); } else printf("-1 "); } return 0; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。