大家好，又见面了，我是全栈君。
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<iostream>
#include<cstdio>
#include<string>
#include<cstring>
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<<ans[m]-ans[n-1]<<endl;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115728.html原文链接：https://javaforall.net
