HDU 6156 Palindrome Function

http://acm.hdu.edu.cn/showproblem.php?pid=6156

题意：
$f(n,k)$表示判断n在k进制下是否是回文串，如果是，则返回k，如果不是，则返回1。现在要计算$sum_{i=L}^{R}sum_{j=l}^{r}f(i,j)$。

思路：
因为我不会数位dp，所以我直接模拟做了一发，写得十分繁琐。。。

先是将数转换成k进制，然后去计算出它的前一半的数，只要小于该数那都是成立的，比如说现在前面的数为985，那么1~984的数都是满足的，绝对不会超。

思路大致就是这样，具体的话还有一些细节，请参见代码。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<sstream>
  6 #include<vector>
  7 #include<stack>
  8 #include<queue>
  9 #include<cmath>
 10 #include<map>
 11 #include<set>
 12 using namespace std;
 13 typedef long long ll;
 14 const int INF = 0x3f3f3f3f;
 15 const int maxn=50000+5;
 16 const int mod=1e9+7;
 17 
 18 ll L,R;
 19 int l,r;
 20 int dig[1000];
 21 
 22 ll solve(ll n, int k)
 23 {
 24     if(n==0)  return 0;
 25     int len=0;
 26     ll tmp=n;
 27     while(tmp)
 28     {
 29         dig[++len]=tmp%k;
 30         tmp/=k;
 31     }
 32     ll num=0;
 33     if(len&1)  //奇数位
 34     {
 35         if(len>=3)
 36         {
 37             ll base=1;
 38             for(int i=len/2+2;i<=len;i++)
 39             {
 40                 num+=dig[i]*base;
 41                 base*=k;
 42             }
 43             num--;   //除去本身，1~num-1的数都是可行的
 44             num*=k;  //奇位数的时候中间那位数可以自由选择
 45             base=1; ll tmp=0;
 46             for(int i=1;i<=len/2;i++)  //奇数位下偶数的情况，前面计算的都是奇位数的情况
 47             {
 48                 tmp+=(k-1)*base;  //直接算最大值即可
 49                 base*=k;
 50             }
 51             num+=tmp;
 52             num+=k-1;  //再加上一位数的情况，因为这个前面没有计算
 53         }
 54         else num=dig[1];
 55     }
 56     else   //偶数位
 57     {
 58         ll base=1;
 59         for(int i=len/2+1;i<=len;i++)
 60         {
 61             num+=dig[i]*base;
 62             base*=k;
 63         }
 64         num--;
 65         base=1; ll tmp=0;
 66         if(len>2)  //偶数位下奇位数的情况
 67         {
 68             for(int i=1;i<=len/2-1;i++)
 69             {
 70                 tmp+=(k-1)*base;
 71                 base*=k;
 72             }
 73             tmp*=k;
 74             num+=tmp;
 75         }
 76         num+=k-1;
 77     }
 78 
 79     ll cnt1=0,cnt2=0;
 80     //判断前一半的数和当前前一半数相等时的情况
 81     if(len&1)
 82     {
 83         if(len>=3)
 84         {
 85             ll base=1;
 86             int zero=0;
 87             for(int i=len;i>=len/2+2;i--)
 88             {
 89                 cnt1+=dig[i]*base;
 90                 if(dig[i]==0)  zero++;  //特别注意，排除前导0
 91                 if(zero==len-i+1)  continue;
 92                 base*=k;
 93             }
 94             base=1;
 95             for(int i=1;i<=len/2;i++)
 96             {
 97                 cnt2+=dig[i]*base;
 98                 base*=k;
 99             }
100             int zhong=dig[len/2+1];
101             if(cnt1<=cnt2)  num+=zhong+1;
102             else num+=zhong;
103         }
104     }
105     else
106     {
107         ll base=1;
108         int zero=0;
109         for(int i=len;i>=len/2+1;i--)
110         {
111             cnt1+=dig[i]*base;
112             if(dig[i]==0)  zero++;
113             if(zero==len-i+1)  continue;
114             base*=k;
115         }
116         base=1;
117         for(int i=1;i<=len/2;i++)
118         {
119             cnt2+=dig[i]*base;
120             base*=k;
121         }
122         if(cnt1<=cnt2)  num++;
123     }
124     return k*num+(n-num);
125 }
126 
127 int main()
128 {
129     //freopen("in.txt","r",stdin);
130     int T;
131     int kase=0;
132     scanf("%d",&T);
133     while(T--)
134     {
135         scanf("%lld%lld%d%d",&L,&R,&l,&r);
136         ll ans=0;
137         for(int k=l;k<=r;k++)
138         {
139             ans+=solve(R,k)-solve(L-1,k);
140         }
141         printf("Case #%d: %lld
",++kase,ans);
142     }
143     return 0;
144 }