# 数位DP入坑
2024-09-08 00:25:05
Hdu 2089 不要62
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std; typedef long long LL; inline int read()
{
char c=getchar();int num=;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())
num=num*+c-'';
return num;
} const int N=1e6+; int n,m;
int a[],dgt;
int f[][; int dfs(int dep,int pre,int sta,bool lim)
{
if(!dep)
return ;
if(!lim&&f[dep][sta!=-)
return f[dep][sta];
int up=lim?a[dep]:;
int ans=;
for(int i=;i<=up;++i)
{
if(i==) continue;
if(pre==&&i==) continue;
ans+=dfs(dep-,i,i==,lim&&i==a[dep]);
}
if(!lim)
f[dep][sta]=ans;
return ans;
} int solve(int x)
{
for(dgt=;x;a[++dgt]=x%,x/=);
return dfs(dgt,,,);
} int main()
{
while()
{
memset(f,-,sizeof(f));
n=read(),m=read();
if(!n&&!m)
break;
cout<<solve(m)-solve(n-)<<'\n';
}
return ;
}
Hdu 6148 Valley Numer
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std; typedef long long LL; inline int read()
{
char c=getchar();int num=;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())
num=num*+c-'';
return num;
} const int N=;
const int mod=1e9+; int T,n;
char a[N];
int f[N][][]; int dfs(int dep,int pre,int turn,bool lim,bool invalid)
{
if(dep==n+)
return invalid?:;
if(!lim&&f[dep][pre][turn]!=-)
return f[dep][pre][turn];
int up=lim?a[dep]-='':;
int ans=;
for(int i=;i<=up;++i)
{
if(turn==&&i<pre)
continue;
int p=;
if(invalid) p=;
else if(i>pre) p=;
else if(i<pre) p=;
else p=turn;
ans+=dfs(dep+,i,p,lim&&i==a[dep],invalid&&i==);
ans%=mod;
}
if(!lim)
f[dep][pre][turn]=ans;
return ans;
} int main()
{
T=read();
while(T--)
{
memset(f,-,sizeof(f));
scanf("%s",a+);
n=strlen(a+);
cout<<dfs(,,,,)<<'\n';
}
return ;
}
Bzoj 1026: [SCOI2009]windy数
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; typedef long long LL; inline LL read()
{
char c=getchar();LL num=;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())
num=num*+c-'';
return num;
} LL A,B;
LL a[],dgt;
LL f[][]; LL dfs(int dep,int pre,bool lim,bool invalid)
{
if(!dep)
return invalid?:;
if(!lim&&!invalid&&f[dep][pre]!=-)
return f[dep][pre];
int up=lim?a[dep]:;
LL ans=;
for(int i=;i<=up;++i)
{
if(!invalid&&abs(i-pre)<) continue;
ans+=dfs(dep-,i,lim&&i==a[dep],invalid&&i==);
}
if(!lim&&!invalid)
f[dep][pre]=ans;
return ans;
} LL solve(LL x)
{
for(dgt=;x;a[++dgt]=x%,x/=);
return dfs(dgt,,,);
} int main()
{
A=read(),B=read();
memset(f,-,sizeof(f));
cout<<solve(B)-solve(A-);
return ;
}
Poj 3252 Round Numbers
题意:问[l,r]中二进制位1比0少的数有多少个。
Sol: 记录当前层0,1个数。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; typedef long long LL; inline int read()
{
char c=getchar();int num=;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())
num=num*+c-'';
return num;
} int l,r;
int a[],bit;
int f[][][]; int dfs(int dep,int c0,int c1,bool lim,bool invalid)
{
if(!dep)
return (!invalid&&c0>=c1)?:;
if(!lim&&f[dep][c0][c1]!=-)
return f[dep][c0][c1];
int up=lim?a[dep]:;
int ans=;
for(int i=;i<=up;++i)
ans+=dfs(dep-,c0+(i==&&!invalid),c1+(i==),lim&&i==up,invalid&&i==);
if(!lim)
f[dep][c0][c1]=ans;
return ans;
} int solve(int x)
{
for(bit=;x;a[++bit]=x&,x>>=);
return dfs(bit,,,,);
} int main()
{
memset(f,-,sizeof(f));
l=read(),r=read();
cout<<solve(r)-solve(l-);
return ;
}
P2518 [HAOI2010]计数
一个比较假的数位DP?但也是按照数位来做的。
Sol:无。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; typedef long long LL; inline int read()
{
char c=getchar();int num=;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())
num=num*+c-'';
return num;
} char num[];
LL ans;int n,m;
int a[],cnt[]; LL c[][];
void init()
{
c[][]=;
for(int i=;i<=;++i)
{
c[i][]=;
for(int j=;j<=i;++j)
c[i][j]=c[i-][j-]+c[i-][j];
}
} LL C(int n)
{
LL res=;
for(int i=;i<;++i)
if(cnt[i])
res*=c[n][cnt[i]],n-=cnt[i];
return res;
} int main()
{
init();
scanf("%s",num+);
for(n=;num[n];++n)
a[n]=num[n]-'',++cnt[num[n]-''];
m=--n;
for(int i=;i<=n;++i)
{
--m;
for(int j=;j<a[i];++j)
if(cnt[j])
--cnt[j],ans+=C(m),++cnt[j];
--cnt[a[i]];
}
cout<<ans;
return ;
}
最新文章
- 图说C++对象模型:对象内存布局详解
- dba诊断之IO
- Modifiers: virtual, override, new, abstract, sealed, internal
- android 学习随笔十七(服务 )
- Android权限安全(2)给基本组件自定义权限(以activity为例)
- 【转】JavaScript中undefined与null的区别
- JFinal极速开发实战-业务功能开发-通用表单验证器
- AlgorithmsI PA2: Randomized Queues and Deques RandomizedQueue
- 小菜学习Lucene.Net(更新3.0.3版本使用)
- 风雨哈佛路(Homeless to Harvard: The Liz Murray Story)-献给困境中的人
- 在COM组件中调用JavaScript函数
- Saiku图表导出时中文显示问题的解决方法
- 第一次PS练习
- java源码学习(二)Integer
- python爬煎蛋妹子图--20多行代码搞定煎蛋妹子图库
- VirtualBoX虚拟机里安装linux系统,在虚拟系统里安装增强功能报错解决方法
- LeetCode练习4 找出这两个有序数组的中位数
- 一些简单的ajax的特点,方法、属性。以及ajax的创建 请求
- telnet客户端程序
- linux文件句柄数