xtu summer individual 1 E - Palindromic Numbers

E - Palindromic Numbers

Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu

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 ≤ 10¹⁷).

Output

For each case, print the case number and the total number of palindromic numbers between i and j (inclusive).

Sample Input

1 10

100 1

1 1000

1 10000

Sample Output

Case 1: 9

Case 2: 18

Case 3: 108

Case 4: 198

解题：回文数字。分成两种类型判断，一种是长度为奇数个的，一种是长度为偶数个的。

举个栗子。。。

20 是长度为2的，偶数长度，只要枚举dp[1][2]+d[1]什么意思呢？d[1]就是长度为1 的回文数字有多少个！dp[1][2]表示以1开始，长度为2的回文数字的个数。

再说120.。枚举d[2],由于是奇数，最后是遇到只有一个数字的情况，这是只要枚举最中间这一位就可以了，把低位与高位设置成一致的，1x1,只有从0开始枚举x，只要还在120的范围内，每枚举一个就加一，一旦不在120的范围内立即跳出循环。

再说一个偶数的长度1234.。。d[3]+dp[0][2]+dp[1][2],把低位跟高位一致后，1221，判断这个数是不是在1234内，是就加一，不是就加0，好吧加0就是不加，你赢了！！！！！！

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <vector>

 #include <climits>

 #include <algorithm>

 #include <cmath>

 #define LL long long

 #define INF 0x3f3f3f

 using namespace std;

 LL dp[][],d[];

 int len,bit[];

 void init() {

     int i,j;

     for(i = ; i < ; i++)

         dp[i][] = dp[i][] = ;

     for(i = ; i < ; i++) {

         for(j = ; j < ; j++) {

             dp[j][i] = *dp[][i-];

         }

     }

     d[] = ;//以0开始的。。。0就是

     for(i = ; i < ; i++) {

         for(j = ; j < ; j++)

             d[i] += dp[j][i];

         d[i] += d[i-];

     }//算出0-长度为i的所有回文数字数目

 }

 LL go(int e) {

     if(e < ) return ;

     LL sum = ;

     for(int i = ; i < ; i++) {

         sum += dp[i][e];

     }

     return sum;

 }

 LL cal(LL n) {

     if(n < ) return n+;

     LL x = n,ans = ,y = ;

     int i,j,k,v,u;

     for(len = ; x; x /= , len++)

         bit[len] = x%;

     ans += d[len-];

     for(j = ,v = len>>,i = len-; i >= v; i--,j++) {

         if(i == len-) {

             for(k = ; k < bit[i]; k++)

                 ans += dp[k][len];

         } else if(i == j) {

             u = i;break;

         } else {

             for(k = ; k < bit[i]; k++)

                 ans += dp[k][len-j*];

         }

     }

     if(i == j) {//奇数个长度，最后结果受最中间的那位影响

         for(i = ,j = len-; i < j; i++,j--)

             bit[i] = bit[j];

         for(k = ; k < ; k++){

             bit[u] = k;

             for(y = i = ; i < len; i++)

                 y = y*+bit[i];

             if(y <= n) ans++;

             else break;

         }

     }else{//偶数个长度，最后结果受最后一位影响

         for(i = ,j = len-; i < j; i++,j--)

             bit[i] = bit[j];

         for(y = i = ; i < len; i++)

             y = y*+bit[i];

         if(y <= n) ans++;

     }

     return ans;

 }

 int main() {

     init();

     int t,ks = ;

     LL a,b,c;

     scanf("%d",&t);

     while(t--){

         scanf("%lld %lld",&a,&b);

         if(a > b) swap(a,b);

         printf("Case %d: %lld\n",ks++,cal(b)-cal(a-));

     }

     return ;

 }

巴特西

xtu summer individual 1 E - Palindromic Numbers

最新文章

热门文章