首页 > 代码库 > 东大oj1155 等凹函数
东大oj1155 等凹函数
Problem Description
定义一种数字称为等凹数字,即从高位到低位,每一位的数字先递减再递增,且该数是一个回文数,即从左读到右与从右读到左是一样的,仅形成一个等凹峰,如543212345,5544334455是合法的等凹数字,543212346,123321不是等凹数字。现在问你[L,R]中有多少等凹数字呢?L,R<=1e18(小于等于2位的无凹峰)
Input
第一行一个整数T,表示有T组数据,T <= 110.
接下来的每行包含两个用空格分开的整数L R,保证L,R<=1e18.
Output
对于每组输入,在一行输出一个整数,代表[L,R]中等凹数字的个数。
Sample Input
2
1 100
666 666666
Sample Output
0
356
没有dfs算不了的问题,如果有,那就用天河一号去dfs(误)
每次都从L到R循环挨个验证肯定TLE,所以用了递归去构造回文数,每次尝试填一个数字,且要求小于等于上一个数字,填完之后给他左右对称过去,这样就生成了一个等凹数字,把他丢到答案数组里面。
对称有两种,比如54322345, 5432345,所以写了两个create分别生成这两种等凹。
有意思的是,从1到1e18,有184574个等凹数。
#include<cstdio> #include<algorithm> using std:: sort; long long res[1000000], NUM = 0; int temp[20] = {100}; void create(int n)// { long long ans = 0; for(int i = n; i <= 2*n-1; i++) temp[i] = temp[2*n-i]; for(int i = 1; i <= 2*n-1; i++) { ans *= 10; ans += temp[i]; } res[NUM++] = ans; } void create2(int n) { long long ans = 0; for(int i = n+1; i <= 2*n; i++) temp[i]= temp[2*n+1-i]; for(int i = 1; i <= 2*n; i++) { ans *= 10; ans += temp[i]; } res[NUM++] = ans; } void dfs(int cur, int n)//create n down words 1 : n { if(cur == n+1) { int ok = 0, cmp = temp[1]; for(int i = 1; i <= n; i++)//平 胸 禁 止(反正也没人看到(误)) if(temp[i] != cmp) ok = 1; if(ok) { create(n); create2(n); } return; } for(int i = 0; i <= 9; i++) { if(i <= temp[cur-1]) { temp[cur] = i; dfs(cur+1, n); } } } void test() { for(int i = 0; i < NUM; i++) printf("%lld ", res[i]); } int main() { for(int i= 2; i <= 9; i++) dfs(1, i); sort(res, res+NUM); //test(); int t; scanf("%d", &t); while(t--) { long long L, R, l, r; scanf("%lld%lld", &L, &R); for(int i = 0; i < NUM; i++) if(res[i] >= L) { l = i; break; } for(int i = NUM-1; i >= 0; i--) if(res[i] <= R) { r = i; break; } printf("%lld\n", r-l+1); } return 0; }
东大oj1155 等凹函数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。