蒟蒻求助!90分 TAT~
查看原帖
蒟蒻求助!90分 TAT~
136596
尤斯蒂亚楼主2021/3/21 10:37
#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
#include<cmath>
using namespace std;
typedef long long LL;

LL dp[51][10];
LL full[51];
LL s(0),t=0;
LL n,m;
	
inline LL solve(LL me)
{
	LL save=me;
	LL pos[51];
	LL len=0;
	LL sum=0;
	
	if (me==0) return 1;
	
	for (LL i=0;i<=50;i++)
	pos[i]=0;
	
	while (save)
	{
		len++;
		pos[len]=save%10;
		save=save/10;
	}
	
	sum=sum+full[len];
	for (LL i=1;i<pos[len];i++)
	sum+=dp[len][i];
	len--;
	
	LL judge=0;
	
	for (LL i=len;i>=1;--i)
	{
		for (LL j=0;j<pos[i];++j)
		{
			if (abs(pos[i+1]-j)>=2) judge=1;
			else judge=0;
			
			if (judge==1) sum=sum+dp[i][j];
		}
		if (abs(pos[i+1]-pos[i])<2) break;
	}
	
	//cout<<endl; 
	return sum;
}

int main()
{
	cin>>n>>m;
	for (LL i=0;i<=50;i++)
	for (LL j=0;j<=9;j++)
	dp[i][j]=0;
	
	for (LL i=0;i<=9;i++)
	dp[1][i]=1;
	
	for (LL i=2;i<=50;i++)
	{
		dp[i][0]-=dp[i-1][1];
	for (LL j=1;j<=9;j++)
	{
		dp[i][0]+=dp[i-1][j];
		for (LL k=0;k<=9;k++)
		if (abs(j-k)>=2)
		dp[i][j]+=dp[i-1][k];
	}
	}
	
	for (LL i=1;i<=50;i++)
	full[i]=0;
	full[1]=1;
	
	for (LL i=2;i<=50;i++)
	{
		full[i]+=full[i-1];
	for (LL j=1;j<=9;j++)
		full[i]+=dp[i-1][j];
	}
	
/*	for (LL i=1;i<=50;i++)
	{
	for (LL j=0;j<=9;j++)
	cout<<"@#-"<<dp[i][j]<<endl; 
	cout<<"&^"<<full[i]<<endl;
	cout<<endl;
	}*/
	
	s=solve(n-1);
	t=solve(m);
	
	//cout<<"!"<<s<<" "<<t<<endl; 
	if (n==m and n==1) cout<<"1";
	else cout<<abs(s-t);
	return 0;
} 
2021/3/21 10:37
加载中...