P3107 [USACO14OPEN]Odometer S解题报告

解题报告

P3107 [USACO14OPEN]Odometer S解题报告：

题意

题意：给定区间$[l,r]$，求区间至少一半的数位相同的数数量。

数据范围：$1\leqslant l\leqslant r\leqslant 10^{18}$。

数位dp的普通题，但是有些细节需要注意。

分析

这里，我会把我所有的思考过程记录下来：

观察题面，发现这道题很显然是数位dp。

我们发现处理区间至少一半的数位相同的数的数量不好做，那么就把它拆成处理每个数字$k$出现超过一半的数的数量。

我们可以先写出$\text{calc}$函数的板子（即拆解数位）：

int calc(int x,int k){
    memset(f,-1,sizeof(f));
    for(len=0;x;x/=10)
        num[++len]=x%10;
    return dfs1(...);
}

这里$\text{calc(x,k)}$指拆解$x$的数位为$num$数组，并求小于等于$x$，且数字$k$不少于一半的数的个数的函数。

然后开始写记忆化搜索的$\text{dfs}$函数，考虑有哪些值可以影响答案：

• 首先是$len,k,flg1$，这三个数分别代表当前处理的数的长度，求解的数字$k$和卡位的标志。（卡位的标志$flg1$在当前选择的数与前面的数完全相同时为$1$，否则为$0$。卡位的标志影响答案的原因：如果$flg1=1$，则当前数位只能取到$num[len]$，因此答案会有差别）
• 为了处理答案（数字$k$必须超过一半），我们要记录两个参数$cnt1,cnt2$，分别指$k$出现的次数与非$k$的数字出现的次数。
• 发现前导零也会对答案造成影响（因为位数可能不一，这样会导致前导零。而前导零中的$0$是不能算到$cnt1$与$cnt2$中的），因此我们也要记录前导零的标志$flg2$。

这样，$\text{dfs}$函数的的参数就出来了：int dfs1(int len,int k,int cnt1,int cnt2,int flg1,int flg2)

然后是记忆化搜索的套路：用数组$f[len][cnt1][cnt2][flg1][flg2]$表示处理长度为$len$，当前钦定的数出现次数出现$cnt1$次，非当前钦定的数出现$cnt2$次，卡位标志为$flg1$，前导零标志为$flg2$的答案。

考虑转移也很简单：枚举数位$i$，然后对所有可以放得下（$flg1=0$或$i\leqslant num[len]$）的方案进行转移，注意在$cnt1$与$cnt2$进行转移的时候需要判断前导零：
$len\Rightarrow len-1\\k\Rightarrow k\\cnt1\Rightarrow cnt1+(i\ne0||flg2=0)\times(i=k)\\cnt2\Rightarrow cnt2+(i\ne0||flg2=0)\times(i\ne k)\\flg1\Rightarrow i=num[len]\&\&flg1\\flg2\Rightarrow i=0\&\&flg2$
即：res+=dfs1(len-1,k,cnt1+(i!=0||flg2==0)*(i==k),cnt2+(i!=0||flg2==0)*(i!=k),i==num[len]&&flg1,i==0&&flg2);

这样，$\text{dfs}$函数也出来了：

int dfs(int len,int k,int cnt1,int cnt2,int flg1,int flg2){
    if(len==0)
        return cnt1>=cnt2;
    if(f[len][cnt1][cnt2][flg1][flg2]!=-1)
        return f[len][cnt1][cnt2][flg1][flg2];
    int res=0;
    for(int i=0;i<=9;i++)
        if(i<=num[len]||flg1==0)
            res+=dfs1(len-1,k,cnt1+(i!=0||flg2==0)*(i==k),cnt2+(i!=0||flg2==0)*(i!=k),i==num[len]&&flg1,i==0&&flg2);
    return f[len][cnt1][cnt2][flg1][flg2]=res;
}

虽然这样能过样例，但是交上去后会收获WA的好成绩。

这个程序有两点错误：

1. 没开$long\ long$
2. 求解发生错误。

第二点是为什么呢？我们举一个例子：$112212$，这个数可以在$k=1$时产生贡献，也会在$k=2$时产生贡献，即一个长度为偶数的数有可能会出现两个数出现次数同时不少于一半。

此时我们可以使用容斥，将总数减去这些特殊的数，在这里为了方便思考，我把这种特殊的数的求解用了另一个函数$\text{calc2}$，当然也用了另一个记忆化搜索函数$\text{dfs2}$。

$\text{calc2}$的代码很容易写出，这里就不单独提供了（后面有完整代码），我们讲一下$\text{dfs2}$的写法：
首先带入的参数有些变化：
1. 增加了一个$k2$，代表另一个求解的数。
2. 将$cnt2$的意义改成$k2$的出现次数。

记忆化很容易写出，然后就是转移了：

由于这个数只由两个数字组成，我们不需要循环，只需要把循环展开就好了，即写两个$if$，再把计算贡献的$copy$下来就$ok$了。（不过这里要记得考虑一下$cnt2$的转移）

long long dfs2(long long len,long long k1,long long k2,long long cnt1,long long cnt2,long long flg1,long long flg2){
    if(len==0)
        return cnt1==cnt2;
    if(f[len][cnt1][cnt2][flg1][flg2]!=-1)
        return f[len][cnt1][cnt2][flg1][flg2];
    long long res=0;
    if(k1<=num[len]||flg1==0)
        res+=dfs2(len-1,k1,k2,cnt1+(k1!=0||flg2==0),cnt2,k1==num[len]&&flg1,k1==0&&flg2);
    if(k2<=num[len]||flg1==0)
        res+=dfs2(len-1,k1,k2,cnt1,cnt2+(k2!=0||flg2==0),k2==num[len]&&flg1,k2==0&&flg2);
    return f[len][cnt1][cnt2][flg1][flg2]=res;
}

但是交上去后发现并没有这么简单，还是WA。

为什么呢？这里我想了很久，发现前导零没有考虑：因为位数不一定，因此要考虑前导零的转移（记得不要和$k1$与$k2$的转移重复计算贡献）：

    if(k1!=0&&k2!=0&&flg2==1)
        res+=dfs2(len-1,k1,k2,cnt1,cnt2,num[len]==0&&flg1,flg2);

代码

注意，这里数位dp采用更简单的记忆化搜索形式。

#include<stdio.h>
#include<string.h>
const int maxl=25;
long long i,j,k,m,n,len,ans;
long long num[maxl],f[maxl][maxl][maxl][2][2];
long long dfs1(long long len,long long k,long long cnt1,long long cnt2,long long flg1,long long flg2){
    if(len==0)
        return cnt1>=cnt2;
    if(f[len][cnt1][cnt2][flg1][flg2]!=-1)
        return f[len][cnt1][cnt2][flg1][flg2];
    long long res=0;
    for(long long i=0;i<=9;i++)
        if(i<=num[len]||flg1==0)
            res+=dfs1(len-1,k,cnt1+(i!=0||flg2==0)*(i==k),cnt2+(i!=0||flg2==0)*(i!=k),i==num[len]&&flg1,i==0&&flg2);
    return f[len][cnt1][cnt2][flg1][flg2]=res;
}
long long calc1(long long x,long long k){
    memset(f,-1,sizeof(f));
    for(len=0;x;x/=10)
        num[++len]=x%10;
    return dfs1(len,k,0,0,1,1);
}
long long dfs2(long long len,long long k1,long long k2,long long cnt1,long long cnt2,long long flg1,long long flg2){
    if(len==0)
        return cnt1==cnt2;
    if(f[len][cnt1][cnt2][flg1][flg2]!=-1)
        return f[len][cnt1][cnt2][flg1][flg2];
    long long res=0;
    if(k1<=num[len]||flg1==0)
        res+=dfs2(len-1,k1,k2,cnt1+(k1!=0||flg2==0),cnt2,k1==num[len]&&flg1,k1==0&&flg2);
    if(k2<=num[len]||flg1==0)
        res+=dfs2(len-1,k1,k2,cnt1,cnt2+(k2!=0||flg2==0),k2==num[len]&&flg1,k2==0&&flg2);
    if(k1!=0&&k2!=0&&flg2==1)
        res+=dfs2(len-1,k1,k2,cnt1,cnt2,num[len]==0&&flg1,flg2);
    return f[len][cnt1][cnt2][flg1][flg2]=res;
}
long long calc2(long long x,long long k1,long long k2){
    memset(f,-1,sizeof(f));
    for(len=0;x;x/=10)
        num[++len]=x%10;
    return dfs2(len,k1,k2,0,0,1,1);
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(i=0;i<=9;i++)
        ans+=calc1(m,i)-calc1(n-1,i);
    for(i=0;i<=9;i++)
        for(j=i+1;j<=9;j++)
            ans-=calc2(m,i,j)-calc2(n-1,i,j);
    printf("%lld\n",ans);
    return 0;
}