【洛谷P3413】萌数

题目大意：求区间 [l,r] 内萌数的个数，其中萌数定义为数位中存在长度至少为 2 的回文子串的数字。

题解：l, r 都是 1000 位级别的数字，显然是一道数位 dp 的题目，暴力直接去世。

发现萌数的定义是一个存在性命题，并不好去求解。利用补集思想，将存在性命题转化成任意性命题，即：求区间 [l,r] 中有多少个数不是萌数。发现只需维护当前位的前两位的数值即可判断是不是萌数，即：若一个数是萌数，当且仅当存在形如 "aa" 或 "aba" 类型的子串。利用数位 dp 统计即可。

另外，注意数组下标，若是负数需要单独判断一下。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int mod=1e9+7;

typedef long long LL;

char l[1010],r[1010];

int digit[1010],tot;

LL dp[1010][10][10];

LL dfs(int cur,int pre2,int pre1,bool lead,bool limit){

	if(cur==tot+1)return 1;

	if(!limit&&!lead&&dp[cur][pre2][pre1]!=-1&&pre2!=-1&&pre1!=-1)return dp[cur][pre2][pre1];

	LL ret=0;

	int bit=limit?digit[cur]:9;

	for(int i=0;i<=bit;i++){

		if(!i&&lead)ret=(ret+dfs(cur+1,-1,-1,1,limit&&i==bit))%mod;

		else if(i&&lead)ret=(ret+dfs(cur+1,-1,i,0,limit&&i==bit))%mod;

		else{

			if(i==pre2||i==pre1)continue;

			ret=(ret+dfs(cur+1,pre1,i,0,limit&&i==bit))%mod;

		}

	}

	if(!limit&&!lead&&pre2!=-1&&pre1!=-1)dp[cur][pre2][pre1]=ret;

	return ret;

}

LL part(char *s){

	tot=strlen(s+1);

	memset(digit,0,sizeof(digit));

	for(int i=1;i<=tot;i++)digit[i]=s[i]-'0';

	memset(dp,-1,sizeof(dp));

	return dfs(1,-1,-1,1,1);

}

void solve(){

	LL ret=part(r)-part(l)+1;

	int lenl=strlen(l+1),lenr=strlen(r+1);

	for(int i=2;i<=lenl;i++){

		if(l[i]==l[i-1]||l[i]==l[i-2]){

			--ret;

			break;

		}

	}

	ret=(ret+mod)%mod;

	LL retl=0,retr=0;

	for(int i=1;i<=lenl;i++)retl=(retl*10+l[i]-'0')%mod;

	for(int i=1;i<=lenr;i++)retr=(retr*10+r[i]-'0')%mod;

	LL ans=((retr-retl+1-ret)%mod+mod)%mod;

	printf("%lld\n",ans);

}

int main(){

	scanf("%s%s",l+1,r+1);

	solve();

	return 0;

}

巴特西

【洛谷P3413】萌数

最新文章

热门文章