首页 > 代码库 > 东大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 等凹函数