题解：B4206 [常州市赛 2021] 数字翻转

miyachn · 2025-07-15 23:04:31 · 题解

题目传送门

　　一道非常好的深搜优化题
　　暴力算法 O(nq) ，由于数据比较水所以加一些优化能够过，上一篇题解关于暴力的讲解已经很清晰了，所以这里不在过多赘述了
　　Q：如何优化？
　　考虑提前预处理出所有符合要求的数，按照常规暴力思想依旧是枚举每一个数，但是这样太慢了
　　那么我们换个思路，将判断可行性转化为构造可行的数
　　这里就用到 dfs 来构造啦（具体解释都放在注释里了）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a1[6]={0,2,5,6,8,9};
ll a2[6]={0,2,5,9,8,6};
//a1储存所有翻转后有意义的数字
//a2储存a1中的数字翻转后的结果 
ll Q,l,r,p[20];
vector<ll> q;//记录所有符合题意的数 
void dfs(ll len,ll ori,ll rev){
    //ori表示当前计算的一段翻转后有意义的数串
    //rev表示ori翻转后的结果 
    //len记录当前ori和rev的长度 
    if(len) q.push_back(ori*p[len]+rev);//两端拼起来符合要求 
    ll st;
    if(len==7) return;//长度达到限制了！（最大不超过10^14 
    if(len==0) st=1;//不能有前导0
    else st=0;
    for(int i=st;i<6;++i){
        if(a1[i]==a2[i]) q.push_back(ori*p[len+1]+a1[i]*p[len]+rev);//可以放在两端中间 
        dfs(len+1,ori*10+a1[i],a2[i]*p[len]+rev);//变换前和变换后的两个数放在两个数串中间也可以 
    }
}
int main(){
    p[0]=1;
    for(int i=1;i<=15;i++) p[i]=p[i-1]*10;//预处理10的次方 
    dfs(0,0,0);//构造所有可行解 
    sort(q.begin(), q.end());//排序 为后面的二分做准备 
    cin>>Q;
    while(Q--){
        cin>>l>>r;
        ll ans=upper_bound(q.begin(),q.end(),r)-lower_bound(q.begin(),q.end(),l);
        //使用二分查找能够很好地降低复杂度 
        cout<<ans<<endl;
    }
    return 0;
}

无注释版本：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a1[6]={0,2,5,6,8,9};
ll a2[6]={0,2,5,9,8,6};
ll Q,l,r,p[20];
vector<ll> q; 
void dfs(ll len,ll ori,ll rev){
    if(len) q.push_back(ori*p[len]+rev); 
    ll st;
    if(len==7) return; 
    if(len==0) st=1; 
    else st=0;
    for(int i=st;i<6;++i){
        if(a1[i]==a2[i]) q.push_back(ori*p[len+1]+a1[i]*p[len]+rev); 
        dfs(len+1,ori*10+a1[i],a2[i]*p[len]+rev); 
    }
}
int main(){
    p[0]=1;
    for(int i=1;i<=15;i++) p[i]=p[i-1]*10; 
    dfs(0,0,0); 
    sort(q.begin(), q.end()); 
    cin>>Q;
    while(Q--){
        cin>>l>>r;
        ll ans=upper_bound(q.begin(),q.end(),r)-lower_bound(q.begin(),q.end(),l);
        cout<<ans<<endl;
    }
    return 0;
}