hiho一下第273周《古老数字》题目分析

2
0

《古老数字》题目分析

本题是一道比较简单的DP题目,只不过除了记录子问题的最优解,还需要记录子问题的决策以还原整个路径。

首先我们可以假设所有的?都是0,计算出这个数字模X的余数,设为r。

然后从低位到高位提取出来所有的?,假设一共有m个,其中第i个处于第p[i]位。

我们用bool f[i][j]表示前i个(从低到高)问号是否有选法能使得N模X的余数为j。int a[i][j]表示如果f[i][j] == true,那么第i位最小的选择是0-9哪个数字。

边界条件是f[0][r] = true,递推方程是:

f[i][j] = Vf[i-1][j-d*10^p[i]] | d = 0/1 .. 9 (如果第i个问号是N的首位,则从1开始;否则从0开始)

a[i][j] = 最小的d满足 f[i-1][j-d*10^p[i]] == true

其中V表示多个布尔值的或和。

如果f[m][Y]==true即表示有解,这时依照a[][]数组的值倒推即可得出所有问号的取值。

3 answer(s)

1

MLE了。。。

1

请教一下各位大佬,我这份代码那里有问题啊???

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 2e5+25;
int dp[205][maxn],Pow[205],x,y;
char s[205];
int main(){
    scanf("%s %d %d",s,&x,&y);
    int len = strlen(s);
    if(s[0]=='0') {
        if(len > 1) puts("No solution");
        else if(y == 0) puts("0");
        else puts("No solution");
        return 0;
    }
    dp[len][0] = 1; Pow[len] = 1;
    for(int i = len-1; ~i; --i){
        Pow[i] = Pow[i+1] * 10 % x;
        if(s[i] == '?'){
            for(int k = 0;k < 9; ++k){
                for(int j = 0;j < x; ++j){
                    if(dp[i+1][j]) dp[i][(k*Pow[i+1]+j)%x] = 1;
                }
            }
        }else{
            for(int j = 0;j < x; ++j){
                if(dp[i+1][j]) dp[i][(j+(s[i]-'0')*Pow[i+1])%x] = 1;
            }
        }
    }
    string ans = ""; int val = 0; bool flag = true;
    for(int i = 0;i < len && flag; ++i){
        if(s[i] == '?'){
            int low = (i == 0)?1:0, vis = 0;
            for(int j = low;j < 9; ++j){
                if(dp[i+1][(y-(val+j*Pow[i+1])%x+x)%x]){
                    ans += (char)(j+'0'); vis = 1;
                    val = (val + j*Pow[i+1])%x;
                    break;
                }
            }
            if(vis == 0) flag = false;
        }
        else{
            val = (val+(s[i]-'0')*Pow[i+1])%x;
            if(dp[i+1][(y-val+x)%x] == 0) flag = false;
            else ans += s[i];
        }
    }
    if(flag) cout << ans << '\n';
    else puts("No solution");
    return 0;
}
0

请问一下,我的代码那里会有问题啊??? **#include

using namespace std; typedef long long LL; const int maxn = 2e5+25; int dp[205][maxn],Pow[205],x,y; char s[205]; int main(){ scanf("%s %d %d",s,&x,&y); int len = strlen(s); if(s[0]=='0') { if(len > 1) puts("No solution"); else if(y == 0) puts("0"); else puts("No solution"); return 0; } dp[len][0] = 1; Pow[len] = 1; for(int i = len-1; ~i; --i){ Pow[i] = Pow[i+1] * 10 % x; if(s[i] == '?'){ for(int k = 0;k < 9; ++k){ for(int j = 0;j < x; ++j){ if(dp[i+1][j]) dp[i][(k*Pow[i+1]+j)%x] = 1; } } }else{ for(int j = 0;j < x; ++j){ if(dp[i+1][j]) dp[i][(j+(s[i]-'0')*Pow[i+1])%x] = 1; } } } string ans = ""; int val = 0; bool flag = true; for(int i = 0;i < len && flag; ++i){ if(s[i] == '?'){ int low = (i == 0)?1:0, vis = 0; for(int j = low;j < 9; ++j){ if(dp[i+1][(y-(val+j*Pow[i+1])%x+x)%x]){ ans += (char)(j+'0'); vis = 1; val = (val + j*Pow[i+1])%x; break; } } if(vis == 0) flag = false; } else{ val = (val+(s[i]-'0')Pow[i+1])%x; if(dp[i+1][(y-val+x)%x] == 0) flag = false; else ans += s[i]; } } if(flag) cout << ans << '\n'; else puts("No solution"); return 0; }*

write answer 切换为英文 切换为中文


转发分享