HDU 3652 B-number (数位DP,入门)
2024-08-26 00:13:24
题意:
如果一个整数能被13整除,且其含有子串13的,称为"B数",问[1,n]中有多少个B数?
思路:
这题不要用那个DFS的模板估计很快秒了。
状态设计为dp[位数][前缀][模13][是否含13],前缀这一维还是有必要的(由于只有前缀1和其他不同,所以也可以用01来表示是否前缀为1)。递归出口是:出现"13"且mod=0。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define INF 0x7f3f3f3f
#define LL long long
#define ULL unsigned long long
using namespace std;
const double PI = acos(-1.0);
const int N=; int f[N][N][][], bit[N];
//[位数][前缀][模13的余数][是否包含13] int dfs(int i,int pre,int mod,bool B,bool e)
{
if(i==) return !mod&&B;
if(!e && ~f[i][pre][mod][B]) return f[i][pre][mod][B]; int ans=, m=;
int u= e? bit[i]: ;
for(int d=; d<=u; d++)
{
m=(mod*+d)%;
if( pre==&&d== )
ans+=dfs(i-, d, m, true, e&&d==u);
else
ans+=dfs(i-, d, m, B, e&&d==u);
}
return e? ans: f[i][pre][mod][B]=ans;
} int cal(int n)
{
int len=;
while(n) //拆数
{
bit[++len]=n%;
n/=;
}
return dfs(len, , , false, true);
} int main()
{
//freopen("input.txt","r",stdin);
memset(f,-,sizeof(f));
int n;
while( ~scanf("%d",&n) )
printf("%d\n",cal(n) ); return ;
}
AC代码
最新文章
- 决策树及R语言实现
- WIN SERVER 2008 R2 VPN
- mysql 连接空闲超8小时自动断开连接问题(linux)
- 解决mysql数据库连接问题
- Bootstrap 基本用法
- PHP读取xml方法讲解
- Linux 命令 - ls: 列出目录内容
- GCC交叉编译链命名
- UVA 1617 Laptop
- APP性能测试工具
- [COGS 1065] 绿豆蛙的归宿
- websocket(一)--握手
- 第1章 背景 - Identity Server 4 中文文档(v1.0.0)
- python条件表达式:多项分支,双向分支
- 使用@Autowired时,取值为null
- SVN:linux下搭建svn服务器
- JSTL的比较运算符有哪些,用例说说它们的作用
- 代理服务 SQUID 测试
- 如何移除 input type=";number"; 时浏览器自带的上下箭头?
- ES6 学习笔记之四 对象的扩展