【接上回】-数位dp例题及详解-上
共\(4\)道难度较高、较有思考性的题。
附上数位dp题单：https://www.luogu.com.cn/training/494976#problems
小小的总述：
数位dp是这样的，状态表示越简洁，dp数组越小巧，进而时空消耗就越少。所以我们刷题的时候，可以先无脑把\(f\)数组的每一维都设为与当前状态相关的所有变量，然后在此基础上，再用下面的方法进行优化：
- 逐步思考哪些状态是一样的，进而优化维度或者每一维的大小。（最重要，是数位dp的精髓，可以同时优化时间和空间）
例：几乎所有数位dp题 - 搜索中途可能有一些状态需要剪枝。（只能优化时间，记忆化越强效果越不明显，所以其实也不是那么重要，但是应该作为写搜索的一个习惯）
例：Round Numbers S、Segment Sum - 思考dp数组有没有冗余空间（根本搜索不到的那种）。（只能优化空间，可应对一些卡常的题）
例：Balanced Numbers
SP10606 Balanced Numbers
SPOJ注册不上所以暂时无法提交w，但是3份代码与正解对拍没有问题。
使用\(vis[0\sim 9]\)表示\(0\sim 9\)的访问情况，\(sta[0\sim 9]\)表示\(0\sim 9\)填写个数的奇偶性（奇数为\(1\)，偶数为\(0\)）。暴搜先打出来，然后考虑怎么记忆化。我们发现如果两个状态（\(limit=false\)）填写到同一位置\(pos\)，而且\(vis\)和\(sta\)都相同，那么这两个状态答案相同。
所以用\(f[pos][vis][sta]\)来记忆化，空间\(20*1024*1024\)，不会MLE（1.46G的内存）
注意到数据范围，可能需要开unsigned long long，注意这样\(f\)数组就不能初始化为\(-1\)了，可以再开一个bool类型的\(fv\)表示\(f\)的这个状态是否计算出答案了。
1.1 Code
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int t,l,r,a[30];
bitset<10> vis,sta;
bool fv[30][1024][1024];
int f[30][1024][1024];
int dfs(int pos,bool limit,bool zero){
if(pos==0){
for(int i=0;i<=9;i++) if(vis[i]&&sta[i]==i%2) return 0;
return 1;
}
int numvis=vis.to_ullong(),numsta=sta.to_ullong();
if(!limit&&!zero&&fv[pos][numvis][numsta])
return f[pos][numvis][numsta];
int rig=limit?a[pos]:9,ans=0;
for(int i=0;i<=rig;i++){
bool is=(zero&&i==0);
bool tvis=vis[i],tsta=sta[i];
if(!is) vis[i]=1,sta[i]=!sta[i];
ans+=dfs(pos-1,limit&&i==rig,is);
vis[i]=tvis,sta[i]=tsta;
}
if(!limit&&!zero) f[pos][numvis][numsta]=ans,fv[pos][numvis][numsta]=1;
return ans;
}
int solve(int x){
int len=0;
while(x){
a[++len]=x%10;
x/=10;
}
return dfs(len,1,1);
}
signed main(){
memset(fv,0,sizeof fv);
cin>>t;
while(t--){
cin>>l>>r;
cout<<solve(r)-solve(l-1)<<endl;
}
return 0;
}
空间优化
（第3种优化方式）
其实上面的就能过了，但是我们注意到还有优化空间。
上面的表示其实就是四进制，但是我们发现\(vis[i]=0,sta[i]=1\)的情况不存在，所以我们可以优化成三进制，状压一下就可以了。总空间\(20*(3^{10})=20*59049\)。
按道理说应该只是优化了空间而没有优化时间，因为上面所说的情况根本不会搜索到。
（但很奇怪的是这份代码跑得奇快，具体见下面的时间对比，如果大家有解答请在评论区告诉我，谢谢！）
1.2 空间优化Code
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int t,l,r,a[30];
int sta[10];
bool fv[30][59049];
int f[30][59049];
//0没访问，1访问奇数次，2访问偶数次，10位三进制
//优化掉了“没访问过，奇数次”的状态
int to_num(){
int ans=0;
for(int i=0;i<=9;i++) ans=ans*3+sta[i];
return ans;
}
int dfs(int pos,bool limit,bool zero){
if(pos==0){
for(int i=0;i<=9;i++){
if(sta[i]==0) continue;
if(sta[i]-1!=i%2) return 0;
}
return 1;
}
int numsta=to_num();
if(!limit&&!zero&&fv[pos][numsta])
return f[pos][numsta];
int rig=limit?a[pos]:9,ans=0;
for(int i=0;i<=rig;i++){
bool is=(zero&&i==0);
int tsta=sta[i];
if(!is) sta[i]=(sta[i]==0||sta[i]==2)?1:2;
ans+=dfs(pos-1,limit&&i==rig,is);
sta[i]=tsta;
}
if(!limit&&!zero) f[pos][numsta]=ans,fv[pos][numsta]=1;
return ans;
}
int solve(int x){
int len=0;
while(x){
a[++len]=x%10;
x/=10;
}
return dfs(len,1,1);
}
signed main(){
memset(fv,0,sizeof fv);
cin>>t;
while(t--){
cin>>l>>r;
cout<<solve(r)-solve(l-1)<<endl;
}
return 0;
}
究极时空优化
（第1种优化方式）
结论：只要vis奇数位上1的个数、vis偶数位上1的个数、sta奇数位上1的个数、sta偶数位上1的个数都分别相等，两种状态答案就一样。所以可以直接使用\(f[pos][a][b][c][d]\)来记忆化，也可以直接压缩成\(f[pos][a]\)。空间\(20*(6^4)=20*1296\)，时间也是。
为什么呢？如果你一共访问了\(n\)个奇数，其中有\(m(m\leq n)\)个奇数访问了奇数次。那么不用管具体这些奇数是几，因为结果中奇数互相换是不会影响的。比如\(331132377\)满足条件，那么我把\(1\)和\(7\)互换，或者把\(3\)都换成\(9\)……都不会影响结果。偶数同理。
1.3 究极时空优化Code
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int t,l,r,a[30];
bitset<10> vis,sta;
bool fv[30][1296];
int f[30][1296];
int dfs(int pos,bool limit,bool zero){
if(pos==0){
for(int i=0;i<=9;i++) if(vis[i]&&sta[i]==i%2) return 0;
return 1;
}
int num=(vis[0]+vis[2]+vis[4]+vis[6]+vis[8]);
num=num*6+(vis[1]+vis[3]+vis[5]+vis[7]+vis[9]);
num=num*6+(sta[0]+sta[2]+sta[4]+sta[6]+sta[8]);
num=num*6+(sta[1]+sta[3]+sta[5]+sta[7]+sta[9]);
if(!limit&&!zero&&fv[pos][num])
return f[pos][num];
int rig=limit?a[pos]:9,ans=0;
for(int i=0;i<=rig;i++){
bool is=(zero&&i==0);
bool tvis=vis[i],tsta=sta[i];
if(!is) vis[i]=1,sta[i]=!sta[i];
ans+=dfs(pos-1,limit&&i==rig,is);
vis[i]=tvis,sta[i]=tsta;
}
if(!limit&&!zero){
f[pos][num]=ans,fv[pos][num]=1;
}
return ans;
}
int solve(int x){
int len=0;
while(x){
a[++len]=x%10;
x/=10;
}
return dfs(len,1,1);
}
signed main(){
memset(fv,0,sizeof fv);
cin>>t;
while(t--){
cin>>l>>r;
cout<<solve(r)-solve(l-1)<<endl;
}
return 0;
}
运行消耗对比
从上到下分别是洛谷题解排名第一、朴素算法、空间优化、究极时空优化的代码的运行消耗，每个样例测试点均在\(5\)个以内。所以可以看出，朴素算法即可通过此题，而优化后的代码，无论在时间还是空间方面，都比题解优。
\[\textbf{——TO BE CONTINUED——} \] 标签：sta,int,30,pos,例题,优化,dp,数位 From： https://www.cnblogs.com/Sinktank/p/18132770