- 「一本通 5.3 例 3」Windy 数
对拍
- 2025-6-5 14:07:57 @
#include<bits/stdc++.h>
using namespace std;
long long ans[21][10],lst[21]={0,1};
void init(){
for(int i=0;i<10;i++)ans[1][i]=1;
for(int i=2;i<21;i++){
for(int j=0;j<10;j++)for(int k=0;k<10;k++){
if(abs(j-k)<2)continue;
ans[i][j]+=ans[i-1][k];
}
lst[i]=ans[i][0];
}
for(int i=2;i<21;i++){
lst[i]+=lst[i-1]+ans[i-1][1];
}
}
long long solve(long long k){
if(!k)return 1;
int num[21]={123123123},tot=0;
bool alw=1;
while(k){
num[++tot]=k%10;
if(abs(num[tot-1]-num[tot])<2)alw=0;
k/=10;
}
long long sum=0,lstx=-2;
for(int i=tot;i>=1;i--){
for(int j=0;j<num[i];j++){
if(abs(j-lstx)<2)continue;
sum+=(j==0&&i==tot?lst[i]:ans[i][j]);
}
if(abs(num[i]-lstx)<2)break;
if(i==1){
if(abs(num[i]-lstx)>=2&&alw)sum+=ans[i][num[i]];
}
lstx=num[i];
}
return sum;
}
int main(int argc,char** argv){
init();
long long a,b;
cin>>a>>b;
// a=stoi(argv[1]),b=stoi(argv[2]);
cout<<solve(max(a,b))-solve(min(a,b)-1);
return 0;
//debug
// cout<<"\n\n\nDEBUG:\n 0 1 2 3 4 5 6 7 8 9\n---------------------------------------\n";
// for(int i=1;i<=5;i++){
// for(int j=0;j<10;j++){
// cout<<setw(3)<<setfill(' ')<<ans[i][j]<<" ";
// }
// cout<<endl;
// }
}
0 comments
No comments so far...
Information
- ID
- 167
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- # Submissions
- 41
- Accepted
- 5
- Uploaded By