大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
http://acm.hdu.edu.cn/showproblem.php?
大致题意：”B-number“即一个整数含有子串”13″且被13整除。求1-n之间这种数的个数。
思路：有两个限制条件：含有子串“13”和能被13整除。
那么设dp[site][mod][flag]。表示到第site位对13取余为mod且标记为flag的数的个数。flag表示是否含有子串”13″。
然后进行记忆话搜索。
#include <stdio.h> #include <iostream> #include <map> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL long long #define _LL __int64 #define eps 1e-8 #define PI acos(-1.0) using namespace std; int dp[15][15][5]; int dig[15]; //flag = 0表示前一个不是1，flag = 1表示前一个是1。flag = 2表示出现"13"。int dfs(int site, int mod, int flag, int up){ if(site == 0) return mod == 0 && flag == 2; //当mod为0且有"13"时。返回1 if(!up && dp[site][mod][flag] != -1)//记忆化 return dp[site][mod][flag]; int len = up ?
dig[site] : 9; int ans = 0; for(int i = 0; i <= len; i++) { int tmod = (mod*10 + i) % 13; int tflag = flag; if(flag == 1 && i == 3) tflag = 2; else if(flag == 0 && i == 1) tflag = 1; else if(flag == 1 && i != 1) tflag = 0; ans += dfs(site-1, tmod, tflag, up && (i == len) ); } if(!up) dp[site][mod][flag] = ans; return ans;}int cal(int n){ int cnt = 0; while(n) { dig[++cnt] = n % 10; n /= 10; } memset(dp,-1,sizeof(dp)); return dfs(cnt,0,0,1);}int main(){ int n; while(~scanf("%d",&n)) { printf("%d\n",cal(n)); } return 0;}
版权声明：本文博客原创文章，博客，未经同意，不得转载。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/117499.html原文链接：https://javaforall.net
