关于优化方式的说明详见数位dp例题及详解-下。
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\)个以内。所以可以看出,朴素算法即可通过此题,而优化后的代码,无论在时间还是空间方面,均比题解优。
标签:sta,int,题解,30,pos,vis,Balanced,优化,SP10606 From: https://www.cnblogs.com/Sinktank/p/18133481