题意: 给你一个长度为 1000 的串以及一个数 n 让你将串中的'?'填上数字 使得该串是 n 的倍数而且最小 (没有前导零)
题解: dp, 令 dp[len][mod] 为是否出现过 填到第 len 位, 余数为 mod 的状态 (dp=0 or 1)
用记忆化搜索来实现, dfs 返回 1 或 0.
如果搜到最后一位并且余数为 0, 返回 1.
如果搜到已经更新过的 dp 状态, 直接返回 0.
将 mod 作为全局变量, 不断更新 mod. 对于每一位 的'?' 暴力枚举 0~9
- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- #include<algorithm>
- #include<iostream>
- #include<math.h>
- #include<ctime>
- #include<vector>
- #include<queue>
- #include<stack>
- #include<list>
- #include<string>
- using namespace std;
- #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
- #define per(i,j,k) for(int i = (int)j;i>= (int)k;i --)
- #define debug(x) cerr<<#x<<"="<<(x)<<endl
- #define mmm(a,b) memset(a,b,sizeof(a))
- #define pb push_back
- typedef double db;
- typedef long long ll;
- const int maxn = 1000+5;
- const int MAXN = (int)3e5 + 7;
- const int N = (int)3e5 + 7;
- const int INF = (int)0x3f3f3f3f;
- //const ll mod = 1e9 + 7;
- string s;
- int n;
- int mod = 0;
- int dp[maxn][maxn];
- int ans[maxn];
- bool dfs(int x) {
- if (x == s.length())return mod==0;
- if (dp[x][mod] == 1)return 0;
- if (s[x] == '?') {
- int i = 0;
- if (x == 0) i = 1;
- for (; i <= 9; i++) {
- int md = mod;
- mod *= 10, mod += i, mod %= n,ans[x]=i;
- if(dfs(x + 1)) return 1;
- mod = md;
- }
- dp[x][mod] = 1;
- }
- else {
- int md = mod;
- mod *= 10, mod += s[x] - '0', mod %= n,ans[x]=s[x]-'0';
- return dfs(x + 1);
- dp[x][mod] = 1;
- mod = md;
- }
- return 0;
- }
- int main() {
- cin>> s>> n;
- if (dfs(0)) {
- int len = s.length();
- rep(i, 0, len - 1)cout <<ans[i];
- }
- else puts("*");
- //cin>> s;
- }
- /*
- */
来源: http://www.bubuko.com/infodetail-2795798.html