首页 > 代码库 > xtu summer individual 1 E - Palindromic Numbers
xtu summer individual 1 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 ≤ 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
解题：回文数字。分成两种类型判断，一种是长度为奇数个的，一种是长度为偶数个的。
举个栗子。。。
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就是不加，你赢了！！！！！！
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #define LL long long10 #define INF 0x3f3f3f11 using namespace std;12 LL dp[200][1000],d[200];13 int len,bit[1000];14 void init() {15 int i,j;16 for(i = 0; i < 10; i++)17 dp[i][1] = dp[i][2] = 1;18 for(i = 3; i < 20; i++) {19 for(j = 0; j < 10; j++) {20 dp[j][i] = 10*dp[0][i-2];21 }22 }23 d[0] = 1;//以0开始的。。。0就是24 for(i = 1; i < 20; i++) {25 for(j = 1; j < 10; j++)26 d[i] += dp[j][i];27 d[i] += d[i-1];28 }//算出0-长度为i的所有回文数字数目29 }30 LL go(int e) {31 if(e < 0) return 1;32 LL sum = 0;33 for(int i = 0; i < 10; i++) {34 sum += dp[i][e];35 }36 return sum;37 }38 LL cal(LL n) {39 if(n < 10) return n+1;40 LL x = n,ans = 0,y = 0;41 int i,j,k,v,u;42 for(len = 0; x; x /= 10, len++)43 bit[len] = x%10;44 ans += d[len-1];45 for(j = 0,v = len>>1,i = len-1; i >= v; i--,j++) {46 if(i == len-1) {47 for(k = 1; k < bit[i]; k++)48 ans += dp[k][len];49 } else if(i == j) {50 u = i;break;51 } else {52 for(k = 0; k < bit[i]; k++)53 ans += dp[k][len-j*2];54 }55 }56 if(i == j) {//奇数个长度，最后结果受最中间的那位影响57 for(i = 0,j = len-1; i < j; i++,j--)58 bit[i] = bit[j];59 for(k = 0; k < 10; k++){60 bit[u] = k;61 for(y = i = 0; i < len; i++)62 y = y*10+bit[i];63 if(y <= n) ans++;64 else break;65 }66 }else{//偶数个长度，最后结果受最后一位影响67 for(i = 0,j = len-1; i < j; i++,j--)68 bit[i] = bit[j];69 for(y = i = 0; i < len; i++)70 y = y*10+bit[i];71 if(y <= n) ans++;72 }73 return ans;74 }75 int main() {76 init();77 int t,ks = 1;78 LL a,b,c;79 scanf("%d",&t);80 while(t--){81 scanf("%lld %lld",&a,&b);82 if(a > b) swap(a,b);83 printf("Case %d: %lld\n",ks++,cal(b)-cal(a-1));84 }85 return 0;86 }