B. Nezzar and Lucky Number

Link

Solution

老年痴呆复健计划。

题意：先给定一个d，称含有d的数字为lucky数字，然后给一串数字然后问每个数字是否能表达成多个lucky数字的和或者自己本身就是lucky数字，是输出yes，否输出no

我一开始只想到了事实上只需要考虑小于10*d的情况，也就是说需要考虑的数字范围不超过90，但该怎么预处理这个小于90的范围就不会了（当然理论上你可以暴力把1-9小于90的合法数据打个表），还是dp水平太差orz，最后看了题解补上那三行（题解还花里胡哨的整了个或等于，研究了半天才意识到这整个dp数组里不就只有0和1么？）

设dp[i]为i是否可表达，那么dp[i]为true当且仅当存在j < i，dp[j]为true且i-j是一个含d的数字（事实上在小于10*d的范围内含d就意味着只有d、1d、2d…(d-1)d这么几个数字，即代码中的(10*i + d)）

Code

const int maxn = 1e4 + 10;

int ans[maxn];
int dp[110];

int main()
{
    int t, q, d, tmp;
    cin >> t;
    while (t--) {
        memset(ans, 0, sizeof(ans));
        memset(dp, 0, sizeof(dp));
        cin >> q >> d;
        dp[0] = 1;
        for (int i = 0; 10 * i + d <= 10 * d; ++i)
            for (int j = 0; 10 * i + d + j <= 10 * d; ++j)
                if(!dp[10 * i + d + j])dp[10 * i + d + j] = dp[j]; //tutorial here: dp[10 * i + d + j] |= dp[j];
        for (int i = 0; i < q; ++i) {
            cin >> tmp;
            if (tmp >= 10 * d) ans[i] = 1;
            else
                ans[i] = dp[tmp];
        }
        for (int i = 0; i < q; ++i) cout << (ans[i] ? "YES" : "NO") << "\n";
    }

    return 0;
}