InTheBloodHorse

每日一题(9) HDU3652

字数统计: 247阅读时长: 1 min
2018/09/19 Share

题目地址
题意:
输入n,问在区间[1,n]里面有数字13且能被13整除的数字有多少个。
思路:
数位dp模版题,pos代表位数,mod 代表当前数字对13取余数,done表示是否已经有数字13,pre代表上一个数字
AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
int a[20];
int dp[20][20][3][15];
// 位数 %13 是否有13 上一位
int dfs(int pos,int mod,int done,int pre,bool lim){
if(pos<0) return done && (!mod);
if(!lim && dp[pos][mod][done][pre]!=-1) return dp[pos][mod][done][pre];
int up = lim ? a[pos]:9,ans=0;
for(int i=0;i<=up;i++){
ans += dfs(pos-1,(mod*10+i)%13,done || (pre==1 && i==3),i,lim && i==a[pos]);
}
if(!lim) dp[pos][mod][done][pre]=ans;
return ans;
}
int solve(int x){
int pos=0;
while(x){
a[pos++]=x%10;
x/=10;
}
return dfs(pos-1,0,0,0,true);
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
memset(dp,-1,sizeof(dp));
printf("%d\n",solve(n));
}
}

原文作者:InTheBloodHorse

原文链接:http://pyking.cn/2018/09/19/每日一题-9-HDU3652/

发表日期:September 19th 2018, 9:22:46 pm

更新日期:September 19th 2018, 9:28:58 pm

版权声明:Have a fun

CATALOG