題意:給定范圍內是回文數的個數。
思路:
dp[site][len] site位的回文長度是len。
需要一個負責數組 ok存每位放的數。
然後就是dfs了,就是取len 的中間值mid
超過mid的話 就看看ok裡面之前對稱的那個數 判斷是否相等
相等才能放進入下一位。
注意判斷前導0,和這個oj必須用long long。
代碼:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"queue" #include"algorithm" #include"iostream" using namespace std; //2014年9月24日10:30:25 long long dp[22][22]; int num[22],ok[22]; long long dfs(int site,int n,int zero,int f) { if(site==0) return 1; if(!f&&!zero&&dp[site][n]!=-1) return dp[site][n]; int len=f?num[site]:9; long long ans=0; for(int i=0; i<=len; i++) { if(zero) { if(i==0) ans+=dfs(site-1,n-1,zero&&i==0,f&&i==len); else { ok[site]=i; ans+=dfs(site-1,n,zero&&i==0,f&&i==len); } } else { int mid=(n+1)/2; if(n%2) { if(site==mid) ans+=dfs(site-1,n,zero&&i==0,f&&i==len); else if(site>mid) { ok[site]=i; ans+=dfs(site-1,n,zero&&i==0,f&&i==len); } else { if(ok[n+1-site]==i) ans+=dfs(site-1,n,zero&&i==0,f&&i==len); } } else { if(site>mid) { ok[site]=i; ans+=dfs(site-1,n,zero&&i==0,f&&i==len); } else { if(ok[n+1-site]==i) ans+=dfs(site-1,n,zero&&i==0,f&&i==len); } } } } if(!f&&!zero) dp[site][n]=ans; return ans; } long long solve(long long x) { int cnt=0; while(x) { num[++cnt]=x%10; x/=10; } return dfs(cnt,cnt,1,1); } int main() { int t,cas=1; cin>>t; memset(dp,-1,sizeof(dp)); while(t--) { long long x,y; scanf("%lld%lld",&x,&y); if(x>y) swap(x,y); printf("Case %d: %lld\n",cas++,solve(y)-solve(x-1)); } return 0; } //2014年9月24日11:26:45