GYM 101889E（dp）

dp[i][j][k]表示第i位填数字k时，与后面的相连模数为j时，后面的数字最小填多少。

测得我提心吊胆还以为复杂度高了，结果出来46ms还是cf评测姬强啊。
#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <ctime>

#include <cctype>

#include <climits>

#include <iostream>

#include <iomanip>

#include <algorithm>

#include <string>

#include <sstream>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <vector>

#include <list>

#include <fstream>

#include <bitset>

#define init(a, b) memset(a, b, sizeof(a))

#define rep(i, a, b) for (int i = a; i <= b; i++)

#define irep(i, a, b) for (int i = a; i >= b; i--)

using namespace std;

typedef double db;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> P;

const int inf = 0x3f3f3f3f;

const ll INF = 1e18;

template <typename T> void read(T &x) {

    x = 0;

    int s = 1, c = getchar();

    for (; !isdigit(c); c = getchar())

        if (c == '-')    s = -1;

    for (; isdigit(c); c = getchar())

        x = x * 10 + c - 48;

    x *= s;

}

template <typename T> void write(T x) {

    if (x < 0)    x = -x, putchar('-');

    if (x > 9)    write(x / 10);

    putchar(x % 10 + '0');

}

template <typename T> void writeln(T x) {

    write(x);

    puts("");

}

const int maxn = 1e3 + 5;

char str[maxn];

int p, st, m;

int dp[maxn][maxn][10], Tenpow[maxn];

int main() {

    scanf("%s%d", str + 1, &p);

    int n = strlen(str + 1);

    for (int i = 1, t = 1; i <= n; i++, t = t * 10 % p) Tenpow[n - i + 1] = t;

    init(dp, -1);

    rep(i, 0, 9)

        dp[n + 1][0][i] = 0;

    irep(i, n + 1, 2)

        irep(j, p - 1, 0) {

            if (i == n + 1 && j)    continue;

            rep(k, 0, 9) {

                if (dp[i][j][k] == -1) continue;

                if (str[i - 1] != '?') {

                    int d = str[i - 1] - '0';

                    dp[i - 1][(d * Tenpow[i - 1] % p + j) % p][d] = k;

                } else {

                    rep(t, 0, 9) {

                        dp[i - 1][(t * Tenpow[i - 1] % p + j) % p][t] = k;

                    }

                }

                break;

            }

        }

    rep(i, 1, 9)

        if (dp[1][0][i] >= 0) {

            st = i;

            break;

        }

    if (st) {

        rep(i, 1, n) {

            printf("%d", st);

            int d = st;

            st = dp[i][m][d];

            m = (m - d * Tenpow[i] % p + p) % p;

        }

    } else  puts("*");

    return 0;

}
巴特西

GYM 101889E（dp）

最新文章

热门文章
