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

　　一道非常好的深搜优化题
　　暴力算法

O(nq)

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

CPP

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

无注释版本：

CPP

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

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

文章操作

相关推荐

评论

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