题解 CF1478B 【Nezzar and Lucky Number】

qinyihao · 2021-01-29 02:50:57 · 题解

思路

对于任何给定的d，我们可以观察到如下信息：

• 定义k=10d+9是该种数字的最大值。对于任何大于k的x，我们可以持续用d减去x，x就会渐渐达到有d作为其数位的范围。

所以，对于任何大于k的x，他们总是可达到的。对于小于等于k-10的x，也就是k \leq 109时，我们可以运行标准的动态规划（即动规），dp[x]暗示了x是否可行。如果dp[x]可行，那么下面中有且仅有一条是对的：

• x=0
• 在某些y<x的情况下，dp[y]可行且x-y有d作为一个数位。

除了动规，单纯的暴力也能轻松通过本题。

code1-动规版 时间复杂度O((10d)^2)

#include<bits/stdc++.h>
using namespace std;
const int maxn=207;
int t,d,q;
bool dp[maxn];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>t;
    while (t--){
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        cin>>q>>d;
        if (!d) d+=10;
        int mx=d*10;
        for (int i=0;10*i+d<=mx;++i){
            for (int j=0;10*i+d+j<=mx;++j){
                dp[10*i+d+j]|=dp[j];
            }
        }
        while (q--){
            int u;
            cin>>u;
            if (u>=mx||dp[u]) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
    return 0;
}

code2-暴力版（没算时间复杂度）

#include <bits/stdc++.h>
using namespace std;
int n, cnt, m, a[100010], ans, flag;
bool p(int x, int k)
{
    while (x)
    {
        if (x % 10 == k)
            return 1;
        x /= 10;
    }
    return false;
}
bool pa(int x, int k)
{
    if (p(x, k) || x == 0)
        return true;
    for (int i = 1; i <= x; ++i)
    {
        if (p(i, k) && pa(x - i, k))
            return true;
    }
    return false;
}
int main()
{
    cin >> flag;
    while (flag--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            if (pa(a[i], m))
                puts("YES");
            else
                puts("NO");
        }
    }
    return 0;
}