P10024-------观察性质

MoCaRabbit · 2023-12-25 13:20:41 · 个人记录

当时比赛时我是机房里第一个 A 掉的人。

这题，数据范围有点大，我们一个个 Subtask 的看。

Subtask 0 太简单了，我们就不看了。

Subtask 1

直接扫一遍，判断有连续的短竖线个数连续一样的数最长有多少个。

时间复杂度 O(n)，能得 52 分。

代码。

#include<bits/stdc++.h>
using namespace std;
int l,r;
int a[10]={6,2,5,5,4,5,6,3,7,6};
int count(int x){
    int ans=0;
    if(x==0) return 6;
    while(x) ans+=a[x%10],x/=10;
    return ans
    ;
}
int main() {
    cin>>l>>r;
    int u=count(l),ans=1,cnt=1;
    for(int i=l+1;i<=r;i++){
        int e=count(i);
        if(u==e) cnt++;
        else u=e,ans=max(ans,cnt),cnt=1;
    }
    cout<<ans;
    return 0;
} 

Subtask 1

观察个位数的短竖线个数。

我们发现个位数中连续的段最多有 2 个。

通过一定的数学直觉与数学推导。

我们得出，短竖线个数连续一样的数最多有 2 个。

因为短竖线个数连续一样最少为 1 个。

可以直接输出 rand()。

再来观察 x \times 100+29 与 x \times 100+30 一定是一个连续段。

所以说，每 100 个数中必定有长度为 2 的连续段。

于是，当 r-l>100 时可以直接输出 2。

特判一下，直接做出来。

代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int l,r;
int a[10]={6,2,5,5,4,5,6,3,7,6};
int count(int x){
    int ans=0;
    if(x==0) return 6;
    while(x) ans+=a[x%10],x/=10;
    return ans;
}
signed main() {
    cin>>l>>r;
    if(r-l<=100){
        int u=count(l),ans=1,cnt=1;
        for(int i=l+1;i<=r;i++){
            int e=count(i);
            if(u==e) cnt++;
            else u=e,ans=max(ans,cnt),cnt=1;
        }
        cout<<ans;
        return 0;
    }
    else cout<<2;
    return 0;
}