WA 62
查看原帖
WA 62
120438
Lacrymabre楼主2021/12/19 13:25
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>

#define ll long long
#define _it set<node>::iterator
#define MAX 0x7fffffff
#define init inline int
#define INF 0X3fffffff
#define N 400001>>1


using namespace std;

inline long long read(){
	ll f=1,s=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
	return s*f;
}

const int mod = 1000000007;
ll n,m,len,a[2001];
ll f[1001][20][20];

int dfs(ll pos,ll last,ll lastt,ll t,ll lead,ll limit){
	if(!pos) return t>0?0:1;
	if(!limit&&f[pos][last][t]!=-1) return f[pos][last][t];
	ll res=limit?a[pos]:9;
	ll cnt=0;
	for(int i=0;i<=res;i++) cnt=(cnt+dfs(pos-1,i,lead?last:-1,t|((i==last)&&lead)||((i==lastt)&&lead),lead|(i!=0),limit&(res==i)));
	if(!limit&&lead&&lastt!=-1) f[pos][last][t]=cnt;
	return cnt;
}

ll slove(ll x){
	len=0;memset(f,-1,sizeof f);
	while(x) a[++len]=x%10,x/=10;
	ll cnt=0;
	cnt=dfs(len,-1,-1,0,0,1);
	return cnt;
}

int main(){
	n=read();m=read();
	if(n>m)swap(n,m);
	if(n==m&&n<10) return printf("%lld",0)&0;
	cout<<slove(m)-slove(n-1);
	return 0;
}
2021/12/19 13:25
加载中...