10624 - Super Number

题意：给出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("\n");

        }

        else

            printf("-1\n");

    }

    return 0;

}