ACM之路（16）—

　　题目就是kuangbin的数位DP。

　　先讲C题，不要62，差不多就是一个模板题。要注意的是按位来的话，光一个pos是不够的，还需要一维来记录当前位置是什么数字，这样才能防止同一个pos不同数字的dp值混在一起。直接丢代码：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <iostream>

 #include <vector>

 #include <queue>

 #include <math.h>

 using namespace std;

 typedef long long ll;

 // pos , 记录当前位是什么

 // 第二维是为了防止同一个pos的不同which的dp混淆在一起，因为是记忆化搜索的

 int bit[],dp[][];

 int dfs(int pos,int which,bool have_six,bool flag)

 {

     if(pos == -) return ;

     int& ans = dp[pos][which];

     if(flag && ans!=-) return ans;

     int d = flag?:bit[pos];

     int ret = ;

     for(int i=;i<=d;i++)

     {

         if(i==) continue;

         if(have_six && i==) continue;

         ret += dfs(pos-,i,i==,flag||i<d);

     }

     if(flag) ans = ret;

     return ret;

 }

 int solve(int x)

 {

     //if(x==0) return 0;

     int pos = ;

     while(x)

     {

         bit[pos++] = x % ;

         x /= ;

     }

     int ans = ;

     ans += dfs(pos-,,false,false);

     return ans;

     // 因为0也是一个值

     // 所以solve(5)=5是因为0.1.2.3.5

 }

 int main()

 {

     int x,y;

     memset(dp,-,sizeof(dp));

     //printf("%d !!\n",solve(5));

     while(scanf("%d%d",&x,&y)==)

     {

         if(x== && y==) break;

         else printf("%d\n",solve(y)-solve(x-));

     }

 }

　　那么如果是求区间内还有62的呢？可以是在上面的基础上，用总个数减去；也可以再开一维have，表示是否拥有了62。这样变化一下就是D题了，丢代码：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <iostream>

 #include <vector>

 #include <queue>

 #include <math.h>

 using namespace std;

 typedef long long ll;

 int bit[];

 ll dp[][][];

 /*ll dfs(int pos,bool state,bool flag)

 {

     if(pos == -1) return 1;

     ll& ans = dp[pos][state];

     if(flag && ans!=-1) return ans;

     int d = flag?9:bit[pos];

     ll ret = 0;

     for(int i=0;i<=d;i++)

     {

         if(state && i==9) continue;

         ret += dfs(pos-1,i==4,flag||i<d);

     }

     if(flag) ans = ret;

     return ret;

 }*/

 ll dfs(int pos,bool state,bool have,bool flag)

 {

     if(pos == -) return have;

     ll& ans = dp[pos][have][state];

     if(flag && ans!=-) return ans;

     int d = flag?:bit[pos];

     ll ret = ;

     for(int i=;i<=d;i++)

     {

         if(state && i==) ret += dfs(pos-,i==,,flag||i<d);

         else ret += dfs(pos-,i==,have,flag||i<d);

     }

     if(flag) ans = ret;

     return ret;

 }

 ll solve(ll x)

 {

     //if(x==0) return 0;

     int pos = ;

     while(x)

     {

         bit[pos++] = x % ;

         x /= ;

     }

     ll ans = ;

     ans += dfs(pos-,false,false,false);

     return ans;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     memset(dp,-,sizeof(dp));

     while(T--)

     {

         ll x;

         scanf("%I64d",&x);

         //printf("%I64d\n",x-(solve(x)-1));

         cout<<solve(x)<<endl;

     }

 }

另外还需要注意的是上面的问题并不需要记录当前一位是哪个数字，只要记录是不是需要的数字即可。比方说62，我只要用一个state保存这一位是不是6即可。

　　以上就是数位dp的基本套路，但是还会遇到一种情况，比方说让你统计区间内数的二进制表示的0的个数，这样子在dfs时需要再加一个参数first来表示有没有前导0。举个例子，比如说10010，在dfs以后，如果变成了0XXXX的情况，显然第一个0是不能算在0的个数之内的。因此，如果数位dp的过程中，有无前导0会对结果造成影响的，就要再加一个参数first来辅助完成dp过程。具体见E题代码：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 using namespace std;

 int bit[];

 int dp[][][];

 //int len;

 /*

     单纯的用len来记录总位数是不行的，因为比方说5是101，

     比它小的数可能len不等于3

     也就是说在递推的过程中len是会发生变化的

     因此，换一个方法，用一个bool变量first记录之前位是否存在

 */

 int dfs(int pos,int num_zero,int num_one,bool flag,bool first)

 {

     if(pos == -) return num_zero >= num_one;

     int& ans = dp[pos][num_zero][num_one];

     if(flag && ans!=-) return ans;

     int d = flag?:bit[pos];

     int ret = ;

     for(int i=;i<=d;i++)

     {

         ret += dfs(pos-,(first||i?num_zero+(i==):),(first||i?num_one+(i==):),flag||i<d,first||i);

     }

     if(flag) ans = ret;

     return ret;

 }

 int solve(int x)

 {

     int pos = ;

     while(x)

     {

         bit[pos++] = x%;

         x/=;

     }

     //len = pos;

     return dfs(pos-,,,false,false);

 }

 int main()

 {

     int x,y;

     memset(dp,-,sizeof(dp));

     while(scanf("%d%d",&x,&y)==)

     {

         printf("%d\n",solve(y)-solve(x-));

     }

     return ;

 }

　　然后几题是比较有意思的。

　　A题，问区间内的美丽数的个数，美丽数指的是：这个数能被各个位置上的数字整除。这题的方法是直接找他们的最小公倍数，然后当做状态的状态的一维即可。要注意的是如果最小公倍数开最大的话，会超内存，那么只要将这一系列的最小公倍数离散化即可。其实这题似乎还可以优化，我没有深究了。具体见代码：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <iostream>

 #include <vector>

 #include <queue>

 #include <math.h>

 using namespace std;

 typedef long long ll;

 int gcd(int a,int b) {return a%b?gcd(b,a%b):b;}

 int lcm(int a,int b) {return a*b/gcd(a,b);}

 // pos,离散化后的公约数的位置,各个位置上数字的和

 int a[+];

 int bit[];

 ll dp[][][+];

 ll dfs(int pos,int _lcm,int sum,bool flag)

 {

     if(pos == -) return (ll)(sum%_lcm==);

     ll& ans = dp[pos][a[_lcm]][sum];

     if(flag && ans!=-) return ans;

     int d = flag?:bit[pos];

     ll ret = ;

     for(int i=;i<=d;i++)

     {

         ret += dfs(pos-,i?lcm(_lcm,i):_lcm,(sum*+i)%,flag||i<d);

     }

     if(flag) ans = ret;

     return ret;

 }

 ll solve(ll x)

 {

     int pos = ;

     while(x)

     {

         bit[pos++] = x % ;

         x /= ;

     }

     ll ans = ;

     ans += dfs(pos-,,,false);

     return ans;

 }

 int main()

 {

     // 离散化

     for(int i=,j=;i<=;i++)

     {

         a[i] = %i?:(++j);

         //printf("%d !!\n",j );

     } // max = 48

     int T;

     scanf("%d",&T);

     memset(dp,-,sizeof(dp));

     while(T--)

     {

         ll x,y;

         scanf("%I64d%I64d",&x,&y);

         printf("%I64d\n",solve(y)-solve(x-));

     }

 }

　　B题，问区间内满足以下条件的数，这个数字内的LIS等于K。那么只要模拟LIS用二进制储存一个状态码当做一维的内容即可。具体见代码：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <iostream>

 #include <stdlib.h>

 #include <string>

 #include <stack>

 using namespace std;

 const int inf = 0x3f3f3f3f;

 typedef long long ll;

 typedef pair<int,int> pii;

 const int N =  + ;

 int bit[],K;

 ll dp[][<<][];

 ll L,R;

 /*

     state是一个状态码，

     二进制状态下，各位如果是0表示LIS中没有这个数，

     否则，就有。

     例如100110，那么表示当前这个数的LIS为125

     如果我要插入一个数字是3，那么3将5替换掉就可以了，

     否则，如果插入的是一个6，比5都大，只要将6放在5后面即可。

     下面的代码就是实现的这一过程。

 */

 int newState(int state,int x)

 {

     // 找到第一个大于x的数将它替换掉

     // 是对LIS的nlog(n)的体现

     for(int i=x;i<;i++)

     {

         if(state & (<<i)) return (state^(<<i))|(<<x);

     }

     return state | (<<x);

 }

 int getLen(int state)

 {

     int cnt = ;

     while(state)

     {

         if(state&) cnt++;

         state >>= ;

     }

     return cnt;

 }

 ll dfs(int pos,int state,bool first,bool flag)

 {

     if(pos == -) return getLen(state)==K;

     ll& ans = dp[pos][state][K];

     if(flag && ans!=-) return ans;

     int d = flag?:bit[pos];

     ll ret = ;

     for(int i=;i<=d;i++)

     {

         ret += dfs(pos-,first||i?newState(state,i):,first||i,flag||i<d);

     }

     if(flag) ans = ret;

     return ret;

 }

 ll solve(ll x)

 {

     int pos = ;

     while(x)

     {

         bit[pos++] = x % ;

         x /= ;

     }

     return dfs(pos-,,false,false);

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     memset(dp,-,sizeof(dp));

     for(int kase=;kase<=T;kase++)

     {

         scanf("%I64d%I64d%d",&L,&R,&K);

         printf("Case #%d: %I64d\n",kase,solve(R)-solve(L-));

     }

 }

　　讲到状态码形式的数位dp，可以再看看最后一题。大意是找出区间内平衡数：任何奇数只要出现了，就必须出现偶数次；任何偶数，只要出现了就必须出现奇数次。不出现的数字不做讨论，同时是任意一个奇数都要出现偶数次，比方说1333，1和3它们都出现了奇数次，而不是所有奇数出现的次数和是偶数次，因此这个数字不满足平衡数的要求。具体实现的话也是转化成3进制的状态码即可，具体见代码：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <iostream>

 #include <stdlib.h>

 #include <string>

 #include <stack>

 using namespace std;

 const int inf = 0x3f3f3f3f;

 typedef long long ll;

 typedef pair<int,int> pii;

 const int N =  + ;

 int bit[];

 ll dp[][];

 int pw[];

 int f[][];

 // f表示的是在这个状态码下各个数字的出现次数

 // 是预处理好的

 // 比如f[12345][6]表示在12345这个状态码下的6的出现的次数的奇偶

 bool check(int state)

 {

     int x = ; // 1表示出现奇数次，2表示出现偶数次

     for(int i=;i>=;i--)

     {

         if(f[state][i])

         {

             if(f[state][i] + x != ) return false;

         }

         x =  - x;

     }

     return true;

 }

 int newstate(int state,int i)

 {

     if(f[state][i] <= )

     {

         //f[state][i]++;

         return state + pw[i]; // 如果出现了0次或者奇数次，就次数加1，相当于那个数字的那一位的三进制加1

     }

     //f[state][i]--;

     return state - pw[i]; // 如果出现了偶数次，让状态码对应位置的三进制减1，表示变成了出现奇数次

 }

 ll dfs(int pos,int state,bool first,bool flag)

 {

     if(pos == -) return check(state);

     ll& ans = dp[pos][state];

     if(flag && ans!=-) return ans;

     int d = flag?:bit[pos];

     ll ret = ;

     for(int i=;i<=d;i++)

     {

         ret += dfs(pos-,first||i?newstate(state,i):,first||i,flag||i<d);

     }

     if(flag) ans = ret;

     return ret;

 }

 ll solve(ll x)

 {

     int pos = ;

     while(x)

     {

         bit[pos++] = x % ;

         x /= ;

     }

     return dfs(pos-,,false,false);

 }

 void init()

 {

     memset(dp,-,sizeof(dp));

     memset(f,,sizeof(f));

     pw[] = ;

     for(int i=;i<=;i++) pw[i] = *pw[i-];

     // 下面是预处理出f的值

     for(int i=;i<=pw[]-;i++)

     {

         int now = i;

         for(int j=;j>=;j--)

         {

             if(now >= pw[j])

             {

                 int t;

                 f[i][j] = t = now/pw[j];

                 now -= t*pw[j];

             }

         }

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     init();

     while(T--)

     {

         ll l,r;

         cin >> l >> r;

         cout << solve(r)-solve(l-) << endl;

     }

 }

　　最后想讲的是J题，求的是区间内的与7无关的数字的平方和。因为涉及到平方，所以涉及到展开的问题。具体见代码注释：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <iostream>

 #include <stdlib.h>

 #include <string>

 #include <stack>

 using namespace std;

 const int inf = 0x3f3f3f3f;

 const int mod = (int)1e9 + ;

 typedef long long ll;

 typedef pair<int,int> pii;

 const int N =  + ;

 struct node

 {

     ll n,s,sq;

 }dp[][][];

 int bit[];

 ll L,R,pw[];

 node dfs(int pos,int sum,int digit_sum,bool flag)

 {

     if(pos == -) return (node){sum&&digit_sum,,};

     node& ans = dp[pos][sum][digit_sum];

     if(flag && ans.n!=-) return ans;

     int d = flag?:bit[pos];

     node ret = (node){,,};

     for(int i=;i<=d;i++)

     {

         if(i == ) continue;

         node temp = dfs(pos-,(sum*+i)%,(digit_sum+i)%,flag||i<d);

         ret.n = (ret.n + temp.n) % mod;

         // 别忘了乘以个数n

         ret.s += (temp.s + (pw[pos] * i) % mod * temp.n) % mod;

         ret.s %= mod;

         // 到这一位需要增加的sq是（i*pw[i]+temp.s）^2，拆开累加即可

         // temp.sq 是 temp.s 的平方

         // 在处理(i*pw[i])的平方时需要乘以个数n。

         // 而处理2倍它们的乘积时不用是因为temp.s中已经乘过n了

         ret.sq += (temp.sq +  * pw[pos] * i % mod * temp.s % mod) % mod;

         ret.sq %= mod;

         ret.sq += (temp.n * pw[pos] % mod * ((pw[pos]*i*i) % mod)) % mod;

         ret.sq %= mod;

     }

     if(flag) ans = ret;

     return ret;

 }

 ll solve(ll x)

 {

     int pos = ;

     while(x)

     {

         bit[pos++] = x % ;

         x /= ;

     }

     return dfs(pos-,,,false).sq % mod;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     memset(dp,-,sizeof(dp));

     pw[] = ;

     for(int i=;i<;i++) pw[i] = (pw[i-] * ) % mod;

     while(T--)

     {

         scanf("%I64d%I64d",&L,&R);

         // 对mod以后的别忘记先加mod再mod不然可能是负数

         printf("%I64d\n",(solve(R)-solve(L-) + mod) % mod);

     }

 }

　　最后想补充的一点是，很多的solve求的都是0~指定位置满足条件的和，但是没有关系，只要相减以后就都抵消了，但是单单使用solve的话就可能会出现问题。

巴特西

ACM之路（16）—— 数位DP

最新文章

热门文章