https://www.lydsy.com/JudgeOnline/problem.php?id=1026

C++版本一

題解：

假設(shè)我們需要求0至x（用數(shù)組表示）的區(qū)間的windy數(shù)的個(gè)數(shù)，x有t位，我們先求出t-1位的windy數(shù)的個(gè)數(shù)，因?yàn)檫@些windy數(shù)絕對(duì)比x小，不會(huì)超過這個(gè)區(qū)間，然后求出長(zhǎng)度為t,最高位小于x[0]的windy數(shù)的個(gè)數(shù)，同樣不會(huì)超過這個(gè)區(qū)間.最后統(tǒng)計(jì)長(zhǎng)度為t，最高位為x[0]的windy數(shù)的個(gè)數(shù)，怎么統(tǒng)計(jì)呢？枚舉i從0到x[1]-1,加上長(zhǎng)度為t-1的最高位為i的數(shù)，不會(huì)超過這個(gè)區(qū)間，然后同樣的，再求最高位為x[1]的windy數(shù)的個(gè)數(shù)，類似于遞歸過程.如果abs(x[0] - x[1]) < 2,則最高位為x[0],次高位為x[1]的windy數(shù)再不存在了，直接退出，到最后一位時(shí)，如果還存在windy數(shù)，windy數(shù)的個(gè)數(shù)+1即可.

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=1000000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; ll t,n,m,k,q; int ans,cnt,flag,temp; int num[20],dp[20][12];int dfs(int len, int last, bool shangxian) {int p;if (len <= 0)return 1;if (!shangxian && dp[len][last] != -1&& last >= 0)return dp[len][last];int cnt = 0, maxx = (shangxian ? num[len] : 9);for (int i = 0; i <= maxx; i++){if (abs(i - last) < 2)continue;p = i;if (i == 0 && last == -10)p = last;cnt += dfs(len - 1, p, shangxian && (i == maxx));}//return cnt;if (last >= 0 && !shangxian)dp[len][last] = cnt;return cnt; }ll solve(int x) {int k = 0;while (x){num[++k] = x % 10;x /= 10;}memset(dp, 255, sizeof(dp));return dfs(k, -10, true); } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifmemset(dp,-1,sizeof(dp));scanf("%lld %lld",&n,&m);printf("%lld\n",solve(m) - solve(n - 1));//cout << "Hello world!" << endl;return 0; }

C++版本二

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath>using namespace std;long long t, a, b;long long f[15][11],shu[15];void init() {memset(f, 0, sizeof(f));for (int i = 0; i <= 9; i++)f[1][i] = 1;for (int i = 2; i <= 10; i++)for (int j = 0; j <= 9; j++)for (int k = 0; k <= 9; k++)if (abs(j - k) >= 2)f[i][j] += f[i - 1][k]; }long long solve(long long x) {memset(shu, 0, sizeof(shu));if (x == 0)return 0;long long k = 0,ans = 0;while (x){shu[++k] = x % 10;x /= 10;}for (int i = 1; i <= k - 1; i++)for (int j = 1; j <= 9; j++)ans += f[i][j];for (int i = 1; i < shu[k]; i++)ans += f[k][i];for (int i = k - 1; i >= 1; i--){for (int j = 0; j <= shu[i] - 1; j++)if (abs(j - shu[i + 1]) >= 2)ans += f[i][j];if (abs(shu[i + 1] - shu[i]) < 2)break;if (i == 1)ans += 1;}return ans; }int main() {scanf("%lld%lld", &a, &b);init();printf("%lld", solve(b) - solve(a - 1));//while (1);return 0; }

?

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的windy数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。