首页 > 代码库 > LightOJ-1205 - Palindromic Numbers
LightOJ-1205 - Palindromic Numbers
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 | Output for Sample Input |
4 1 10 100 1 1 1000 1 10000 | Case 1: 9 Case 2: 18 Case 3: 108 Case 4: 198 |
题目大意为:a-b区间有多少个数是回文数,a,b的范围 为10^17
因此只能用数位DP
用DP[pos][len] 记录答案 pos表示的是当前的位置,len为回文数长度
用num[pos] 记录前mid位的信息
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; typedef long long ll; ll a,b; vector<int> digit; int num[20]; ll dp[19][19]; ll dfs(int pos,int len,int zero,int done){ if(pos==-1) return 1; if(!done && !zero && ~dp[pos][len]) return dp[pos][len]; ll res = 0; int end = done?digit[pos]:9; for(int i = 0; i <= end; i++){ if(zero){ num[len] = i; res += dfs(pos-1,len-!i,zero&&i==0,done&&i==end); }else{ int mid = (len+1)>>1; if(len&1){ if(pos < mid){ if(num[2*mid-pos-1]==i) res += dfs(pos-1,len,zero&&i==0,done&&i==end); }else{ num[pos] = i; res += dfs(pos-1,len,zero&&i==0,done&&i==end); } }else{ if(pos == mid){ res += dfs(pos-1,len,zero&&i==0,done&&i==end); }else if(pos < mid){ if(num[mid*2-pos]==i) res += dfs(pos-1,len,zero&&i==0,done&&i==end); } else{ num[pos] = i; res += dfs(pos-1,len,zero&&i==0,done&&i==end); } } } } if(!done && !zero) dp[pos][len] = res; return res; } ll solve(ll x){ digit.clear(); memset(dp,-1,sizeof dp); if(x==0) digit.push_back(0); while(x){ digit.push_back(x%10); x /= 10; } return dfs(digit.size()-1,digit.size()-1,1,1); } int main(){ int ncase,T=1; cin >> ncase; while(ncase--){ cin >> a >> b; if(a > b) swap(a,b); printf("Case %d: %lld\n",T++,solve(b)-solve(a-1)); //cout<<<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。