荔枝丹(litchi)

题目描述

绛雪艳浮红锦烂，玉壶光莹水晶寒。

高名已许传新曲，芳味曾经荐大官。

乌府日长霜署静，几株斜覆石栏杆。

——明·陈辉《荔枝》

荔枝（丹），拼音为lizhidan，一种好吃的水果，深得悦色老师的喜爱。

祝阿姨得到了许多许多的荔枝丹，每个荔枝丹上都有一个00到99之间的数字。祝阿姨把它们分成许多组，每组表示一个数，且所有组表示的数字合起来恰好是[L,R][L,R]内的所有数。

祝阿姨知道悦色老师特别喜欢吃荔枝丹，于是邀请了悦色老师来吃荔枝丹。悦色老师最喜欢吃有数字00的荔枝丹了，她吃掉了所有数字为00的荔枝丹。

祝阿姨想知道还剩下多少不同的组。注意悦色老师吃完后，荔枝丹就无序了，也就是说123123和321321是同样的组。

输入

一行两个正整数L,RL,R。

输出

一行一个整数，表示还剩下多少不同的组。

样例输入

<span style="color:#333333"><span style="color:#333333">【样例1输入】

1 10

【样例2输入】

40 57

【样例3输入】

157 165

</span></span>

样例输出

<span style="color:#333333"><span style="color:#333333">【样例1输出】

9

【样例2输出】

17

【样例3输出】

9</span></span>

提示

【子任务】

测试点	R	R-L
1~2	≤106	≥0
3~4	≤1018	0≤R-L≤1000000
5~20	≤1018	≥0

来源

noip2017模拟-wmd

solution

首先由18位的不同数码（无序）的数量为

C（27,9）约=4e6

所以我们可以枚举所有可能的数码，然后判断这个数码能否在[l,r]中出现

用go（pos，l_flag，r_flag），表示到了第pos位，当前获得的数字是否等于相应的L/R的前缀，返回当前枚举的字符串能否构造出来。

分类讨论：

如果pos == n，则返回true。

如果l_flag == 1 && r_flag == 1，进一步讨论：

如果L[pos] == R[pos],则在第pos位只能是L[pos]，然后进行go(pos+1, 1, 1)；

如果L[pos]<R[pos]，那么如果可以放[L[pos]+1,R[pos]-1]中的数字，那么一定可行；如果不可以，则尝试放L[pos]并继续go(pos+1,1,0)或放R[pos]并继续go(pos+1,0,1)。

如果l_flag和r_flag有且仅有一个为真，则与上面的讨论类似，先考虑把那个卡边界的弄成不卡的，如果可行直接返回真，不可行就继续卡边界继续枚举。

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

using namespace std;

ll l,r,L[20],R[20],ans,num[20],f[10];

bool pd(int k,int fl,int fr){

    //cout<<k<<' '<<fl<<' '<<fr<<endl;

    if(k==19)return 1;

    if(fl==0&&fr==0)return 1;

    if(fl==1&&fr==1){

        if(L[k]==R[k]){

            if(f[L[k]]){

                f[L[k]]--;int t=pd(k+1,1,1);f[L[k]]++;

                return t;

            }

            else return 0;

        }

        if(L[k]<R[k]){

            for(int i=L[k]+1;i<R[k];i++)if(f[i])return 1;

            bool can=0;

            if(f[L[k]]){

                f[L[k]]--;can|=pd(k+1,1,0);f[L[k]]++;

            }

            if(can)return 1;

            if(f[R[k]]){

                f[R[k]]--;can|=pd(k+1,0,1);f[R[k]]++;

            }

            return can;

        }

        if(L[k]>R[k])return 0;

    }

    if(fl==1){

        for(int i=L[k]+1;i<=9;i++)if(f[i])return 1;

        if(f[L[k]]){

            f[L[k]]--;int t=pd(k+1,1,0);f[L[k]]++;

            return t;

        }

        return 0;

    }

    if(fr==1){

        for(int i=R[k]-1;i>=0;i--)if(f[i])return 1;

        if(f[R[k]]){

            f[R[k]]--;int t=pd(k+1,0,1);f[R[k]]++;

            return t;

        }

        return 0;

    }

}

void dfs(int k){

    //cout<<k<<endl;

    if(k==19){

        for(int i=0;i<=10;i++)f[i]=0;

        for(int i=1;i<=18;i++)f[num[i]]++;

        //for(int i=0;i<=9;i++)cout<<f[i]<<' ';cout<<endl;

        //for(int i=1;i<=18;i++)cout<<num[i];cout<<endl;

        if(pd(1,1,1))ans++;

        return;

    }

    for(int i=num[k-1];i<=9;i++){

        num[k]=i,dfs(k+1);

    }

}

int main(){

    cin>>l>>r;

    if(r==(ll)1e18){

        if(l<=(ll)1e17)r--;

        else r--,ans++;

    }

    int top=18;

    for(top=18;top>0;top--)L[top]=l%10,l/=10;

    for(top=18;top>0;top--)R[top]=r%10,r/=10;

    //for(int i=1;i<=18;i++)cout<<L[i];cout<<endl;

    //for(int i=1;i<=18;i++)cout<<R[i];cout<<endl;

    dfs(1);

    cout<<ans<<endl;

    return 0;

}

巴特西

荔枝丹(litchi)

荔枝丹(litchi)

题目描述

输入

输出

样例输入

样例输出

提示

来源

最新文章

热门文章