37pts求救
查看原帖
37pts求救
812227
Sunrise_beforeglow楼主2024/7/9 19:51
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,t;
int v[20],cnt,kkk[20];
int dp[20][15][15][2][2][2];
//dfs(数位,step-2位,step-1位,是否是回文串,是否出现过第i个数位<v[i],是否是前导0)
int dfs(int step,int la,int lb,int all,int limit,int k)
{
	if(all)return dp[step][la][lb][all][limit][k]=0;
	if(step>t)return dp[step][la][lb][all][limit][k]=1;
	if(dp[step][la][lb][all][limit][k]!=-1)return dp[step][la][lb][all][limit][k];
	int g=9;
	if(limit)g=v[step];
	int sum=0;
	for(int i=0;i<=g;i++)
	{
		kkk[step]=k&&(i==0);
		int nxt_all=all;
		if(kkk[step-1])nxt_all=all;
		else if(kkk[step-2])nxt_all|=(i==lb);
		else nxt_all|=(i==lb)||(i==la);
		int nxt_limit=limit&&(i==v[step]);
		sum+=dfs(step+1,lb,i,nxt_all,nxt_limit,kkk[step]);
		kkk[step]=k;
	}
	return dp[step][la][lb][all][limit][k]=sum;
}
void solve(int x)
{
	t=0;
	while(x)
	{
		v[++t]=x%10;
		x/=10;
	}
	reverse(v+1,v+t+1); 
	memset(dp,-1,sizeof(dp));
	kkk[0]=1;
	cnt+=dfs(1,0,0,0,1,1);
}
signed main()
{
	cin>>a>>b;
	solve(a-1);
	cnt=-cnt;
	solve(b);
	cout<<cnt;
	return 0;
}
2024/7/9 19:51
加载中...