首页 > 代码库 > LightOJ 1205 Palindromic Numbers
LightOJ 1205 Palindromic Numbers
数位DP。。。。
Palindromic Numbers
[Submit] [Go Back] [Status] Description A palindromic number or numeral palindrome is a ‘symmetrical‘ number like 16461 that remains the same when its digits are reversed. In this problem you will be given two integers i j, you have to find the number of palindromic numbers between i and j (inclusive). Input Input starts with an integer T (≤ 200), denoting the number of test cases. Each case starts with a line containing two integers i j (0 ≤ i, j ≤ 1017). Output For each case, print the case number and the total number of palindromic numbers between i and j (inclusive). Sample Input 4 1 10 100 1 1 1000 1 10000 Sample Output Case 1: 9 Case 2: 18 Case 3: 108 Case 4: 198 Source Problem Setter: Jane Alam Jan [Submit] [Go Back] [Status] |
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long int LL; int a[70]; LL dp[70][70]; LL dfs(int len,int l,int r,bool limit,bool ok) { if(l<r) return !limit||(limit&&ok); if(!limit&&~dp[len][l]) return dp[len][l]; LL ret=0; int mx=limit?a[l]:9; for(int i=0;i<=mx;i++) { if(l==len-1&&i==0) continue; int g=ok; if(g) g=a[r]>=i; else g=a[r]>i; ret+=dfs(len,l-1,r+1,limit&&i==mx,g); } if(!limit) dp[len][l]=ret; return ret; } LL gaoit(LL n) { if(n<0) return 0; if(n==0) return 1; int len=0; while(n){a[len++]=n%10;n/=10;} LL ret=1; for(int i=len;i>=1;i--) ret+=dfs(i,i-1,0,i==len,1); return ret; } int main() { int T_T,cas=1; cin>>T_T; memset(dp,-1,sizeof(dp)); while(T_T--) { LL x,y; cin>>x>>y; if(x>y) swap(x,y); printf("Case %d: %lld\n",cas++,gaoit(y)-gaoit(x-1)); } return 0; }
LightOJ 1205 Palindromic Numbers