P2657 [SCOI2009] windy 数

题意

不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 windy 数。求在 $[a,b]$ 区间的 windy 数数量。

$1≤a≤b≤2×10^9$ 。

点击查看题解

题解

首先一个不很关键的结论：如果我们知道 $[1,a]$ 和 $[1,b]$ 范围内有多少 windy 数，我们就可以算出 $[a,b]$ 范围内有多少 windy 数（作差法）。

我们设 dp[i][j] 代表 $i$ 位且第 $i$ 位数字是 $j$ 的 windy 数的个数。

首先， $[1,9]$ 都是 windy 数。递推出数据范围内的 dp 值。

然后分别算出 $[1,a]$ 和 $[1,b+1]$ 范围内的 windy 数个数。以下以 $a$ 为例。

数位比 $a$ 少的 windy 数都是范围内的 windy 数。
数位和 $a$ 相等，最高位数字比 $a$ 的最高位数字小的 windy 数都是范围内的 windy 数。
数位和 $a$ 相等，前几位数字和 $a$ 的相等，但只要后面有一个数位上的数字比 $a$ 的小的 windy 数，都是范围内的 windy 数。
和 $a$ 相等的 windy 数也是范围内的 windy 数。

作差输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	int a,b,dp[20][20];
	
	int cnt(int x)
	{
		int ans=0,len=0,n[20];
		memset(n,0,sizeof(n));
		while(x) n[++len]=x%10,x/=10;
		
		for(int i=1;i<len;i++)
			for(int j=1;j<=9;j++)
				ans+=dp[i][j];
		for(int i=1;i<n[len];i++)
			ans+=dp[len][i];
		for(int i=len-1;i>=1;i--)
		{
			for(int j=0;j<=n[i]-1;j++)
		   		if(abs(j-n[i+1])>=2)
				   ans+=dp[i][j];
			if(abs(n[i+1]-n[i])<2) break;
		}
		return ans;
	}
	void yzmain()
	{
		scanf("%d%d",&a,&b);
		for(int i=0;i<=9;i++) dp[1][i]=1;
		
		for(int i=2;i<=10;i++)
			for(int j=0;j<=9;j++)
				for(int k=0;k<=9;k++)
					if(abs(j-k)>=2)
						dp[i][j]+=dp[i-1][k];
		printf("%d",cnt(b+1)-cnt(a));
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P4124 [CQOI2016]手机号码

题意

合法号码是不含前导零的 $11$ 位的数字，要出现至少 $3$ 个相邻的相同数字；号码中不能同时出现 $8$ 和 $4$ 。

给定 $l$ 和 $r$ （不含前导零， $11$ 位），求 $[l,r]$ 区间的合法号码数量。

点击查看题解

题解

七度空间

我们定义七维的 dp[i][i][i][0/1][0/1][0/1][0/1] ，分别表示第 $i$ ， $i+1$ ， $i+2$ 位数字，是否出现过至少 $3$ 个相邻的相同数字，是否当前数字小于 $n$ ，是否出现过 $4$ ， $8$ 。

使用记忆化搜索来 dp。共有 $10^3 \times 2^4=16000$ 个状态，不会 TLE。其实，搜索到的状态是要小于这个数的，比如不能同时出现 $4$ 和 $8$ 。

详见代码。

还记得解决 windy 数问题时用的一个结论吗？我们直接两个区间相减就能得到答案。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	long long l,r,num[20],
	dp[20][20][20][2][2][2][2];//各维意义: 第几位 上一位数字 上两位数字 连过? <n? 4? 8?
	long long dfs(int step,int pr1,int pr2,bool lkd,bool stn,bool ap4,bool ap8)
	{
		long long ans=0,limit;
		if(ap4&&ap8) return 0;//不能同时出现 4 和 8
		if(step<=0) return lkd;//搜索到头，返回这个数是否合法。本句相当于同时判断两个条件。实际上，只有这个和前面的那一句条件满足，答案才合法。
		if(dp[step][pr1][pr2][lkd][stn][ap4][ap8])
			return dp[step][pr1][pr2][lkd][stn][ap4][ap8];//记忆化
		if(stn) limit=9; else limit=num[step];//保证枚举的数字<=n
		
		for(long long i=0;i<=limit;i++)//枚举算符
			ans+=dfs(step-1,i,pr1, lkd||(pr1==pr2&&pr1==i) , stn||(i<num[step]) , ap4||i==4 , ap8||i==8);
		
		return dp[step][pr1][pr2][lkd][stn][ap4][ap8]=ans;
	}
	
	long long solve(long long x)
	{
		long long len=0,ans=0;
		
		if(x<10000000000) return 0;
		
		memset(dp,0,sizeof(dp));
		memset(num,0,sizeof(num));
		
		while(x) num[++len]=x%10,x/=10;
		
		for(long long i=1;i<=num[len];i++)//从高位
			ans+=dfs(10,i,0,0,i<num[len],i==4,i==8);
		
		return ans;
	}
	
	void yzmain()
	{
		scanf("%lld%lld",&l,&r);
		printf("%lld",solve(r)-solve(l-1));
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/68a12257f01f/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 动态规划一些数位 DP

最后更新：2023-08-21, 23:18:21

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158