P10024 「HCOI-R1」报名人数 题解

话说你谷主题库的题目编号都有 5 位数了（震惊）

形式化题意

在 [i, j](l ≤ i ≤ j ≤ r) 的区间内，使所有相邻的数所用的小木棒都相等，求 j − i + 1 的最大值。

小木棒个数：对于数位分别取 0 ∼ 9，该数位对应所用的短竖线数量分别是 6, 2, 5, 5, 4, 5, 6, 3, 7, 6。

解题思路

观察发现：相邻的两个自然数，它们最多只有两位不同：个位和十位。

而若一个数的末位是 2 的话，则它的下一个数的末位是 3 是必然的，而它们两个的小木棒个数是相等的。

所以得出结论：若 l − r ≥ 10，则改区间内一定有一对 i, j 符合条件。

但是再次观察表格发现，没有相邻的三个数，它们所使用的小木棒个数相等。

所以 j − i + 1 的最大值为 2。

至于 l − r < 10 的时候，直接暴力就得了。

代码：

#include<bits/stdc++.h>
using namespace std;
long long l,r;
map<char,int>mp;
int val(long long k){
	int ans=0;
	while(k){
		ans+=mp[k%10];
		k/=10;
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	char idx=0;
	for(int a:{6,2,5,5,4,5,6,3,7,6}) mp[idx++]=a;
	cin>>l>>r;
	if(l-r>=10) cout<<2;
	else{
		for(long long i=l;i<r;++i){
			if(val(i)==val(i+1)){
				cout<<2;
				return 0;
			}
		}
		cout<<1;
	}
	return 0;
}