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的数都是满足的，绝对不会超。

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

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 const int maxn=+;

 const int mod=1e9+;

 ll L,R;

 int l,r;

 int dig[];

 ll solve(ll n, int k)

 {

     if(n==)  return ;

     int len=;

     ll tmp=n;

     while(tmp)

     {

         dig[++len]=tmp%k;

         tmp/=k;

     }

     ll num=;

     if(len&)  //奇数位

     {

         if(len>=)

         {

             ll base=;

             for(int i=len/+;i<=len;i++)

             {

                 num+=dig[i]*base;

                 base*=k;

             }

             num--;   //除去本身，1~num-1的数都是可行的

             num*=k;  //奇位数的时候中间那位数可以自由选择

             base=; ll tmp=;

             for(int i=;i<=len/;i++)  //奇数位下偶数的情况，前面计算的都是奇位数的情况

             {

                 tmp+=(k-)*base;  //直接算最大值即可

                 base*=k;

             }

             num+=tmp;

             num+=k-;  //再加上一位数的情况，因为这个前面没有计算

         }

         else num=dig[];

     }

     else   //偶数位

     {

         ll base=;

         for(int i=len/+;i<=len;i++)

         {

             num+=dig[i]*base;

             base*=k;

         }

         num--;

         base=; ll tmp=;

         if(len>)  //偶数位下奇位数的情况

         {

             for(int i=;i<=len/-;i++)

             {

                 tmp+=(k-)*base;

                 base*=k;

             }

             tmp*=k;

             num+=tmp;

         }

         num+=k-;

     }

     ll cnt1=,cnt2=;

     //判断前一半的数和当前前一半数相等时的情况

     if(len&)

     {

         if(len>=)

         {

             ll base=;

             int zero=;

             for(int i=len;i>=len/+;i--)

             {

                 cnt1+=dig[i]*base;

                 if(dig[i]==)  zero++;  //特别注意，排除前导0

                 if(zero==len-i+)  continue;

                 base*=k;

             }

             base=;

             for(int i=;i<=len/;i++)

             {

                 cnt2+=dig[i]*base;

                 base*=k;

             }

             int zhong=dig[len/+];

             if(cnt1<=cnt2)  num+=zhong+;

             else num+=zhong;

         }

     }

     else

     {

         ll base=;

         int zero=;

         for(int i=len;i>=len/+;i--)

         {

             cnt1+=dig[i]*base;

             if(dig[i]==)  zero++;

             if(zero==len-i+)  continue;

             base*=k;

         }

         base=;

         for(int i=;i<=len/;i++)

         {

             cnt2+=dig[i]*base;

             base*=k;

         }

         if(cnt1<=cnt2)  num++;

     }

     return k*num+(n-num);

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     int T;

     int kase=;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%lld%lld%d%d",&L,&R,&l,&r);

         ll ans=;

         for(int k=l;k<=r;k++)

         {

             ans+=solve(R,k)-solve(L-,k);

         }

         printf("Case #%d: %lld\n",++kase,ans);

     }

     return ;

 }