P4124 [CQOI2016]手机号码

应该到复习阶段了。

题目介绍

题目来源：重庆省选 第一天第三题

评测链接 ：https://www.luogu.com.cn/problem/P4124
评测链接 ：https://loj.ac/p/2044

形式化题意：给定一个区间 ，求出该区间内满足以下条件的数的个数：

1. 至少三个相邻的相同数字；
2. 和 不能同时出现。

一道中规中矩的数位 题，考虑用记忆化的形式求解。

题目给定了三个条件：

• 要求数字为 位；
• 要求至少三个相邻相同数字；
• 要求 和 不能同时出现。

那我们的状态如此设计：

dfs(int pos,int fir,int sec,bool cnt,bool _4,bool _8,bool limit)

其中 表示当前在第多少位（还剩多少位）， 分别表示上一个和上上个选择的数， 表示当前是否满足了条件二， 分别表示 和 出现过没有， 为数位 常规操作，表示当前是否已经满足了不会越位。

然后就好做了。

AC Code

// ----- Eternally question-----
// Problem: P4124 [CQOI2016]手机号码
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4124
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2022-12-28 10:21:55
// ----- Endless solution-------

#include<bits/stdc++.h>
typedef long long ll;
const int MAXN=11;
int Dp[MAXN][MAXN][MAXN][2][2][2][2];
int Nums[MAXN];
ll dfs(int pos,int fir,int sec,bool cnt,bool four,bool eight,bool out)
{
	if(four&&eight) return 0;
	if(!pos) return cnt;
	if(~Dp[pos][fir][sec][cnt][four][eight][out]) return Dp[pos][fir][sec][cnt][four][eight][out];
	ll ret=0;
	int res=out?9:Nums[pos];
	for(int i=0;i<=res;++i)
		ret+=dfs(pos-1,i,fir,cnt|(i==fir&&i==sec),four|(i==4),eight|(i==8),out|(i<res));
	return Dp[pos][fir][sec][cnt][four][eight][out]=ret;
}
ll L,R,M;
inline ll calc(ll x)
{
	if(x<1e10) return 0;
	std::memset(Dp,-1,sizeof(Dp));
	ll ret=0;
	int len;
	for(len=0;x;x/=10) Nums[++len]=x%10;
	for(int i=1;i<=Nums[len];++i) ret+=dfs(len-1,i,-1,0,(i==4),(i==8),(i<Nums[len]));
	return ret;
}
int main()
{
	std::cin>>L>>R;
	std::cout<<calc(R)-calc(L-1);
	return 0;
}