题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=6156
题目描述： 求L~R所有的数的l~r进制的f(x), f(x) = 当前进制 如果回文串， f(x) = 1 其他情况
解题思路： 数位DP， 统计个数 ， 需要作出改变的就是进制和回文
代码：
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #include <map> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define mem0(a) memset(a,0,sizeof(a)) #define mem1(a) memset(a,-1,sizeof(a)) #define meminf(a) memset(a,0x3f,sizeof(a)) #define fi(n) for(i=0;i<n;i++) #define fj(m) for(j=0;j<m;j++) #define sca(x) scanf("%d",&x) #define scalld(x) scanf("%I64d",&x) #define print(x) printf("%d ",x) #define printlld(x) printf("%I64d ",x) #define d printf("======= ") typedef long long LL; using namespace std; const int maxn = 100; int digit[maxn]; int temp[maxn]; LL dp[40][maxn][maxn][5]; // dp[i][j][p][q] i 进制第j位是p完成还是没完成 LL dfs( int k, int pos, int len, int status, int limit ) { if( pos < 0 ) { if( status ) return k; else return 1; } if( !limit && dp[k][pos][len][status] != -1 ) { return dp[k][pos][len][status]; } int end = limit ? digit[pos] : k-1; LL ret = 0; for( int i = 0; i <= end; i++ ) { temp[pos] = i; if( i == 0 && len == pos) { ret += dfs( k, pos-1, len-1, status, limit && (i==end)); } else if( status && pos < (len+1)/2 ) { ret += dfs( k, pos-1, len, i == temp[len-pos], limit&&(i==end) ); } else { ret += dfs( k, pos-1, len, status, limit&&(i==end) ); } } if( !limit ) dp[k][pos][len][status] = ret; return ret; } LL fun( int num, int k ) { if( num == 0 ) return k; int cnt = 0; while( num ) { digit[cnt++] = num % k; num /= k; } return dfs( k, cnt-1, cnt-1, 1, 1 ); } int main() { int t; // cin >> t; sca(t); int cases = 1; mem1(dp); while( t-- ) { LL res = 0; int L, R, l, r; // cin >> L >> R >> l >> r; sca(L), sca(R), sca(l), sca(r); for( int i = l; i <= r; i++ ) { res += fun(R, i) - fun(L-1, i); } printf( "Case #%d: %lld ", cases++, res ); // cout << "Case: #" << cases++ << ": " << res << endl; } return 0; }
思考： 自己一开始没想到数位DP， 赛后补题的时候写的时候也有很多错误， 有好多细节自己想不到， 是真的菜， 现在把代码删了， 重新写一遍， 还有好多好多地方是需要努力的啊
http://acm.hdu.edu.cn/showproblem.php?pid=6156
转载于:https://www.cnblogs.com/FriskyPuppy/p/7398339.html