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
Output for Sample Input
Case 1: 9
Case 2: 18
Case 3: 108
Case 4: 198
代码:
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 int a[40],tmp[40];
5 ll dp[40][100][100];
6 ll dfs(int start,int pos,int ok,bool limit)
7 {
8 if(pos<0)
9 return ok;
10 if(!limit&&dp[pos][ok][start]!=-1)
11 return dp[pos][ok][start];
12 ll ans=0;
13 int up=limit?a[pos]:9;
14 for(int d=0; d<=up; ++d)
15 {
16 tmp[pos]=d;
17 if(start==pos&&d==0)
18 ans+=dfs(start-1,pos-1,ok,limit&&d==up);
19 else if(ok&&pos<(start+1)/2)
20 ans+=dfs(start,pos-1,tmp[start-pos]==d,limit&&d==up);
21 else
22 ans+=dfs(start,pos-1,ok,limit&&d==up);
23 }
24 if(!limit)
25 dp[pos][ok][start]=ans;
26 return ans;
27 }
28 ll solve(ll x)
29 {
30 memset(a,0,sizeof(a));
31 int cnt=0;
32 while(x!=0)
33 {
34 a[cnt++]=x%10;
35 x/=10;
36 }
37 return dfs(cnt-1,cnt-1,1,1);
38 }
39 int main()
40 {
41 memset(dp,-1,sizeof(dp));
42 int t,cnt=1;
43 scanf("%d",&t);
44 while(t--)
45 {
46 ll x,y;
47 scanf("%lld%lld",&x,&y);
48 if(x>y)
49 swap(x,y);
50 printf("Case %d: %lld\n",cnt++,solve(y)-solve(x-1));
51 }
52 return 0;
53 }
转载于:https://www.cnblogs.com/mj-liylho/p/7400440.html