[Solution] [CQOI2016]手机号码

时间:2021-02-18 17:59:50

是一道数位DP。可以用记忆化搜索解决。

题目地址

这道题细节非常多。可以考虑分步进行。

  • (L?)(R?)之间的符合条件的数,可以等价为求(text{1~R}?)之间的符合条件的数减去$text{1~L-1}$之间符合条件的数

  • 那我先写一个搜索求解(L?)

void DFS (int X , int K , int U , int _4 , int _8 , int T) {
//变量名介绍:X代表当前的位数,K代表当前位所填的数字,U=1表示卡上界,否则不卡。_4和_8分别是有没有出现过4和8,T=3表示已完成三连号,否则表示未完成,且T等于当前连号。
    if (X == N - 1) {
        if (T == 3)    Ans ;
        return ;
    }
//如果符合条件,就累加答案。
    int Goto = Base - 1 ;
    if (U) Goto = L[X   1] ;
//如果卡了上界,应该进行特判。
    for (int i = 0 ; i <= Goto ;    i) {
        if (_4 && i == 8) continue ;
        if (_8 && i == 4) continue ;
        //如果同时出现8和4就跳过这一步。
        if (T == 3) {
            DFS ( X   1 , i , L[X   1] == i && U ? 1 : 0 ,
            i == 4 || _4 ,i == 8 || _8 , 3) ;
        } else DFS ( X   1 , i , L[X   1] == i && U ? 1 : 0 ,
         i == 4 || _4 ,i == 8 || _8 , i == K ? T   1 : 1) ;
    }
}
  • 上面的代码可以在数位较少时得出正确结果。但是当数位较大((10^{10}≤L<10^{11}?))就会TLE。

  • 搜索是盲目的,因为它做了很多重复性的工作。(By Instructor Li)

  • 对于(text{DFS (int X , int K , int U , int _4 , int _8 , int T)}?),它的同一组参数所得到的结果应该是一样的。这是进行记忆化搜索的前提。

  • 具体地说,开一个数组(text{ F[20][10][2][2][2][4]})。其中六个维度分别对应(text{DFS})的六个参数。

  • 我们每次搜索完成后,把Ans的改变量(delta Ans)结果记录在上述数组里,下一次遇到同一组参数,只要在(Ans)增加上已记录的答案,然后返回即可。

  • 改进版本:

void DFS (int X , int K , int U , int _4 , int _8 , int T) {
//这一部分的变量名解释和刚才一样。
    if (X == N - 1) {
        if (T == 3)    Ans ;
        return ;
    }
    if (F[X][K][U][_4][_8][T] != -1) {
        Ans  = F[X][K][U][_4][_8][T] ;
        return ;
    }
    //遇到同一组参数,只要在$Ans$增加上已记录的答案,然后返回即可。
    F[X][K][U][_4][_8][T] = Ans;
    int Goto = Base - 1 ;
    if (U) Goto = L[X   1] ;
    for (int i = 0 ; i <= Goto ;    i) {
        if (_4 && i == 8) continue ;
        if (_8 && i == 4) continue ;
        if (T == 3) {
            DFS ( X   1 , i , L[X   1] == i && U ? 1 : 0 , i == 4 || _4 ,i == 8 || _8 , 3) ;
        } else DFS ( X   1 , i , L[X   1] == i && U ? 1 : 0 , i == 4 || _4 ,i == 8 || _8 , i == K ? T   1 : 1) ;
    }
    F[X][K][U][_4][_8][T] = Ans - F[X][K][U][_4][_8][T] ;
    //把Ans的改变量δAns结果记录在上述数组里
}
  • 这个版本已经可以快速完成求解。

其他要点:

  • 注意开(text{long long})
  • 注意细节,例如(L-1)的边界情况。

Thanks !