Njzy学习了回文串后联想到了回文数,他希望统计出一个区间内的全部回文数。
如今给定一个闭区间[a,b],求这个区间里有多少个回文数。比方[20,30],仅仅有一个回文数那就是22.
输入描写叙述: 输入包括多组測试数据,每组測试数据包括两个整数a,b,(0<a<=b<10^6)。
输出描写叙述: 对于每组測试数据输出对应的答案。
思路:水题。这个明显是水神杯...聪明的你,肯定不会暴力求解的....对吧?!
太聪明的你,说不定还会当成线段树来拍...可是正常的你,应该会dp一下吧。
大概就是。一次遍历。考虑[0,i]的回文数个数。[l,r]的回文数就是[0,r]-[0,l-1]最后每次查找就是O(1),输出ans[m]-ans[n-1],与CF的前次非常像的做法。我当时用了线段树!
dp方程就是 dp[i]=dp[i-1]+symm(i)。
/*********************************************************** > OS : Linux 3.2.0-60-generic #91-Ubuntu > Author : yaolong > Mail : dengyaolong@yeah.net > Time : 2014年06月03日 星期二 17:53:49 **********************************************************/#include#include #include #include using namespace std;int ans[1000001];bool symm(int m){int temp = m,n=0;while (temp){n = n*10+temp%10;temp = temp/10;}return (m == n);}int main(){ ans[0]=0; for(int i=1;i<=1000000;i++){ if(symm(i)){ ans[i]=ans[i-1]+1; }else{ ans[i]=ans[i-1]; } } int n,m; while(cin>>n>>m){ cout< <