题解 P3107 【[USACO14OPEN]Odometer S】

whiteqwq · 2020-06-12 22:31:08 · 题解

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进行转移的时候需要判断前导零，即：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}。