SGU 258 Almost Lucky Numbers 接近幸运数（数位DP）

题意：

　　定义一个具有2n位的正整数，其前n位之和与后n位之和相等，则为lucky数。给定一个区间，问有多少个正数可以通过修改某一位数从而变成lucky数？注意不能含前导0。

思路：

　　我的想法是记录那些非lucky数，再想办法来统计，后来发现有点行不通，无法知道其前后部之和是否相等。如果记录lucky数，然后通过统计每个位上的数来变成lucky数，这更麻烦，因为会重复统计，比如11和22是lucky数，而21可以通过修改1位来变成lucky数，被统计了两次。

　　学习了前辈的方法，也强迫一下自己别人的模板。据我对此模板的理解，第一次求解时是直接求解的，但是把所有统计过的都记录起来了，下次若还用到就直接返回就行了。复杂度是10⁸吧。

　　这是前辈们的代码，拿来理解一下，顺便适应一下新模板。

 #include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <map>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #define pii pair<int,int>

 #define INF 0x7f3f3f3f

 #define LL long long

 #define ULL unsigned long long

 using namespace std;

 const double PI  = acos(-1.0);

 const int N=;

 const int M=;

 const int mod=1e9+;

 int f[N][N][][N][N], bit[N+];

 int dfs(int i,int up,int sum,int more,int less,bool e)    //e表示:是前缀？

 {

     if(i==)

         return (sum!=M && ( sum+more>=M && sum-less<=M ) );

     if(!e && ~f[i][up][sum][more][less])   //已经计算好了(非前缀才行)

         return f[i][up][sum][more][less];

     int ans=;

     int d= i==up? : ;        //起始，注意首位不能为0啊

     int u= e? bit[i]: ;       //终止，注意末位不能超啊

     for( ; d<=u; d++)          //是否为最后一个取决于参数e

     {

         int ssum=  i>(up>>)? sum+d: sum-d; //单峰形的

         int mmore= i>(up>>)? max(more, -d): max(more, d);   //前部：可加。后部：可减

         int lless= i>(up>>)? max(less, i==up?d-:d): max(less, -d);//前部：可减。后部：可加

         ans+=dfs(i-,up, ssum, mmore, lless, e&&d==u);

     }

     return e? ans: f[i][up][sum][more][less]=ans; //前缀的返回不同

 }

 int cal(int n)

 {

     if(n<)    return ;   //仅个位数不可能是lucky数

     int len=, ans=;

     while(n)    //拆数

     {

         bit[++len]=n%;

         n/=;

     }

     for(int i=; i<=len; i+=)      //i是数的长度

         ans+=dfs(i,i,+M,,,i==len);

     return ans;

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     memset(f,-,sizeof(f));

     int L, R;

     while( ~scanf("%d%d",&L,&R) )

         printf("%d\n", cal(R)-cal(L-) );

     return ;

 }

AC代码

巴特西

SGU 258 Almost Lucky Numbers 接近幸运数（数位DP）

最新文章

热门文章