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
题意：求区间的回文串数量。
思路：从两头向中间靠，前缀是否小于原数用tag表示，后缀是否小于原数用ok表示，注意后缀尽管后面的比原位大，但是前面的小一点可以抵消其效果。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
ll dp[][][][]; int d[],cnt;
ll get(int bg,int l,int r,int tag,bool ok)
{
if(r>l) return !tag||(tag&&ok);
if(!tag&&dp[bg][l][tag][ok]) return dp[bg][l][tag][ok];
int lim=tag?d[l]:; ll res=;
rep(i,,lim){
if(bg==l&&i==) continue;
bool g=ok;
if(ok) g=i<=d[r];
else g=i<d[r];
res+=get(bg,l-,r+,tag&&(i==lim),g);
}
return tag?res:dp[bg][l][tag][ok]=res;
}
ll cal(ll x)
{
if(x<) return 0LL;if(x==) return 1LL;
ll res=; cnt=;
while(x) d[++cnt]=x%,x/=;
rep(i,,cnt) res+=get(i,i,,i==cnt,true);
return res;
}
int main()
{
int T,C=; ll L,R; scanf("%d",&T);
while(T--){
scanf("%lld%lld",&L,&R); if(L>R) swap(L,R);
printf("Case %d: %lld\n",++C,cal(R)-cal(L-));
}
return ;
}
有部分数组没有必要：
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
ll dp[][]; int d[],cnt;
//tag维护前缀是否小于，ok维护后缀是否小于。维护二者不一样。
ll get(int bg,int l,int r,int tag,bool ok)
{
if(r>l) return !tag||(tag&&ok);
if(!tag&&dp[bg][l]) return dp[bg][l];
int lim=tag?d[l]:; ll res=;
rep(i,,lim){
if(bg==l&&i==) continue;
bool g=ok;
if(ok) g=i<=d[r];
else g=i<d[r];
res+=get(bg,l-,r+,tag&&(i==lim),g);
}
return tag?res:dp[bg][l]=res;
}
ll cal(ll x)
{
if(x<) return 0LL;if(x==) return 1LL;
ll res=; cnt=;
while(x) d[++cnt]=x%,x/=;
rep(i,,cnt) res+=get(i,i,,i==cnt,true);
return res;
}
int main()
{
int T,C=;ll L,R; scanf("%d",&T);
while(T--){
scanf("%lld%lld",&L,&R); if(L>R) swap(L,R);
printf("Case %d: %lld\n",++C,cal(R)-cal(L-));
}
return ;
}