这道题看着像是manacher，但其实是数位dp。
因为如果某个数上的某一位与它的上一位相同，则这个数肯定是个回文数；同理，如果某个数上的某一位与它的上上一位相同，则这个数肯定也是个回文数。
数位dp时要注意前导0的判断。
代码：
#include<bits/stdc++.h> #define ll long long #define N 21 #define L 11 using namespace std; ll a,b,dp[N][L][L][2],num[N]; long long dfs(int k,int pre,int ppre,bool limit,bool pre0) { if(!k)return 1; if(dp[k][pre][ppre][limit])return dp[k][pre][ppre][limit]; ll ans=0; int t; if(limit)t=num[k]; else t=9; for(int i=0;i<=t;i++)if((i!=pre)&&(i!=ppre))ans+=dfs(k-1,((pre0&&!i)?-1:i),((pre0&&!i)?-1:pre),limit&&i==t,pre0&&!i); return dp[k][pre][ppre][limit]=ans; } ll query(ll x) { memset(dp,0,sizeof(dp)); int cnt=0; while(x) { num[++cnt]=x; x/=10; } ll ans=dfs(cnt,-1,-1,true,true); return ans; } int main() { scanf("%lld%lld",&a,&b); printf("%lld\n",query(b)-query(a-1)); return 0; }转载于:https://www.cnblogs.com/ez-lcw/p/11168859.html
