Acwing 1083. Windy數

題意：

Windy 定義了一種 Windy 數：不含前導零且相鄰兩個數字之差至少為 2 的正整數被稱為 Windy 數。

Windy 想知道，在 A 和 B 之間，包括 A 和 B，總共有多少個 Windy 數？

題解：

和這個題沒啥區別Acwing 1082. 數字游戲題解連接

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=15; int f[maxn][maxn]; void init(){//這里求的是包含前導0的情況 for(int i=0;i<=9;i++)f[1][i]=1;for(int i=2;i<maxn;i++){for(int j=0;j<=9;j++){for(int k=0;k<=9;k++){if(abs(k-j)>=2){f[i][j]+=f[i-1][k];}}}} } int solve(int n){if(!n)return 0;vector<int>vec;while(n)vec.push_back(n%10),n/=10;int tot=0;int last=-1;//n位數的答案for(int i=vec.size()-1;i>=0;i--){int x=vec[i];for(int j=(i==vec.size()-1);j<x;j++){if(abs(j-last)>=2){tot+=f[i+1][j];}}if(abs(x-last)<2)break;last=x;if(!i)tot++;}//低于n位數 for(int i=1;i<=vec.size()-1;i++)for(int j=1;j<=9;j++)tot+=f[i][j];return tot; } int main() {int l,r;init();cin>>l>>r;cout<<solve(r)-solve(l-1);return 0; }

總結

以上是生活随笔為你收集整理的Acwing 1083. Windy数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。