B4206题解

洛谷同文链接

B4206 [常州市程序设计小能手 2021] 数字翻转

思路

暴力

首先考虑打表，看一眼数据范围，$10^{14}$，啥都不用想，就算你打出了数组代码也一定会太长。

那么，我们就可以写一个函数，遍历 $L$ 到 $R$ 之间的数，检查，如果是，就增加答案数。

70 分的超时代码：

#include<bits/stdc++.h>
using namespace std;
int change[10]={0,-1,2,-1,-1,5,9,-1,8,6};
//#define int unsigned long long
int daozhi(int x){
	int ans=0;
	while(x!=0){
		ans+=x%10;
		x/=10;
		ans*=10;
	}
	return ans/10;
}
int weishu(int x){
	int ans=0;
	while(x!=0){
		ans++;
		x/=10;
	}
	return ans;
}
string check(int x){
	x=daozhi(x);
	int n=weishu(x);
	string ans=to_string(x);
	for(int i=0;i<n;i++){
		ans[i]=change[ans[i]-'0']+'0';
	}
	return ans;
}
signed main(){
	int T;
	cin>>T;
	while(T--){
		int l,r;
		cin>>l>>r;
		int ans=0;
		for(int i=l;i<=r;i++){
			if(check(i)==to_string(i)){
				ans++;
			}
		}
		cout<<ans<<endl;
	}
    return 0;
}

优化

优化思路

可以看到，在 70 分代码中，数字在翻转时调用了很多的函数，导致时间复杂度爆炸。我们可以优化这个翻转的过程。

优化过程

首先看到翻转数字的部分。我把两部分分开了，但是可以把两部分合到一起。

再看到检查函数部分。我的写法是每一位先翻转再把翻转后的结果返回并比较两个结果的关系。但是其实可以一边剥离每一位，另一边检查这一位翻转后是否有意义，并合成回原数字。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll q,r,l,a[11]={0,-1,2,-1,-1,5,9,-1,8,6};
int main(){
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>l>>r;
        int cnt=0;
        for(int j=l;j<=r;j++){
            bool vis=true;
            int t=j,f=0;
            while(t){
                if(a[t%10]==-1){
                    vis=0;
                    break;
                }
                f=f*10+a[t%10];
                t/=10;
            }
            if(f==j&&vis==1){
                cnt++;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

通过记录