Description

Victor 是一名熱愛數字的同學。他最近在思考這樣一個問題：
一個字符串是回文的當且僅當它倒過來還和原來相同。那么如果一個數的數串沒有一個長度超過1 的子串是回文串的話，它就是palindrome-free 的。例如：16276 是palindrome-free的，而17276 不是，因為它包含了回文串727。
Victor 想知道在a 到b 的區間內，有多少個數是palindrome-free 的。

Input

從文件numbers.in 中讀入數據。
包括兩個數字a,b。

Output

輸出到文件numbers.out 中。
輸出包含一個整數：區間a,…,b 中palindrome-free 的數的總個數(包括a,b)。

Sample Input

輸入1：

123 321

輸入2：

123456789 987654321

Sample Output

輸出1：

153

輸出2：

167386971

Data Constraint

對于16% 的數據，b - a <= 200。
對于24% 的數據，b - a <= 10^5。
對于32% 的數據，b - a <= 10^6。
對于100% 的數據，0 <= a <= b <= 10^18

Solution

• 這道題是一道典型的數位DP，即根據枚舉數位來統計結果的動態規劃。

• 套路設 Work(x) 表示從 0 到 x 的答案，則答案即為 Work(b)?Work(a?1) 。

• 因為回文只需判斷長度為 2 或 3 的中心串即可，

• 于是設出狀態 F[i][j][k][l] 表示填了 i 位、 上兩位為j、l 限制越界0/1 的方案數。

• 為方便轉移，k 為 0（第 1 到 i 為前導 0）、1（第 1 到 i?1 為前導 0） 或 2 （其他情況）。

• 答案即為 ∑F[n][i][j][k] 。

Code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long n,m; int a[20]; long long f[20][100][3][2]; inline long long work(long long x) {for(a[0]=0;x;x/=10) a[++a[0]]=x%10;reverse(a+1,a+1+a[0]);memset(f,0,sizeof(f));f[0][0][0][1]=1;for(int i=0;i<a[0];i++)for(int j=0;j<=99;j++)for(int k=0;k<2;k++)if(k){for(int l=0;l<a[i+1];l++){if(!l) f[i+1][j%10*10+l][0][0]+=f[i][j][0][1]; elsef[i+1][j%10*10+l][1][0]+=f[i][j][0][1];if(j<=9 && j && j!=l) f[i+1][j%10*10+l][2][0]+=f[i][j][1][1];if(j%10!=l && j/10!=l) f[i+1][j%10*10+l][2][0]+=f[i][j][2][1];}if(!a[i+1]) f[i+1][j%10*10+a[i+1]][0][1]+=f[i][j][0][1]; elsef[i+1][j%10*10+a[i+1]][1][1]+=f[i][j][0][1];if(j<=9 && j && j!=a[i+1]) f[i+1][j%10*10+a[i+1]][2][1]+=f[i][j][1][1];if(j%10!=a[i+1] && j/10!=a[i+1]) f[i+1][j%10*10+a[i+1]][2][1]+=f[i][j][2][1];}elsefor(int l=0;l<=9;l++){if(!l) f[i+1][j%10*10+l][0][0]+=f[i][j][0][0]; elsef[i+1][j%10*10+l][1][0]+=f[i][j][0][0];if(j<=9 && j && j!=l) f[i+1][j%10*10+l][2][0]+=f[i][j][1][0];if(j%10!=l && j/10!=l) f[i+1][j%10*10+l][2][0]+=f[i][j][2][0];}long long sum=0;for(int i=0;i<=99;i++)for(int j=0;j<3;j++)for(int k=0;k<2;k++)sum+=f[a[0]][i][j][k];return sum; } int main() {scanf("%lld%lld",&n,&m);printf("%lld",work(m)-work(n-1));return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5379. 【NOIP2017提高A组模拟9.21】Victor爱数字的全部內容，希望文章能夠幫你解決所遇到的問題。

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