SP10606 BALNUM - Balanced Numbers 题解

· · 题解

很久以前积的题解，因为比目前的题解更优，就从博客园搬过来了。

更好的阅读体验

本题解提供O(20\times 3^{10})和O(20\times 6^4)的做法。

使用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的这个状态是否计算出答案了。

#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;
}

空间优化

其实上面的就能过了，但是我们注意到还有优化空间。

上面的表示其实就是四进制，但是我们发现vis[i]=0,sta[i]=1的情况不存在，所以我们可以优化成三进制，状压一下就可以了。总空间20*(3^{10})=20*59049。

按道理说应该只是优化了空间而没有优化时间，因为上面所说的情况根本不会搜索到。

（但很奇怪的是这份代码跑得奇快，具体见下面的时间对比，如果大家有解答请在评论区告诉我，谢谢！）

#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;
}

进一步时空优化

结论：只要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……都不会影响结果。偶数同理。

#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;
}

运行消耗对比

从上到下分别是洛谷题解（by Fuko_Ibuki）、朴素算法、空间优化、究极时空优化的代码的运行消耗，每个样例测试点均在5个以内。所以可以看出，朴素算法即可通过此题，而优化后的代码，无论在时间还是空间方面，均比题解优。