P10024 「HCOI-R1」报名人数

· · 个人记录

赛时唯一做出的题，果然还是我太菜了

题目大意

对于 0\sim 9，对应所用的短竖线数量分别是 6, 2, 5, 5, 4, 5, 6, 3, 7, 6。
求表示一个数各数位短竖线的和连续相同的数列的最大长度。

思路

第一想法直接暴力，求出每个数短竖线的和，然后贪心比较。

52分代码

#include<bits/stdc++.h>
using namespace std;
int a[20]={6,2,5,5,4,5,6,3,7,6};
int check(int x)
{
    int k,ans=0;
    while(x)
    {
        k=x%10;
        x/=10;
        ans+=a[k];
    }
    return ans;
}
int main()
{
    int n,m,sum,k=1,mx=1;
    cin>>n>>m;
    sum=check(n);
    for(int i=n+1;i<=m;i++)
    {
        if(check(i)==sum)
            k++;
        else{
            sum=check(i);
            mx=max(mx,k);
            k=1;
        }
    }
    cout<<mx;
    return 0；
}

打表一下后并观察题目我发现只有 2 变为 3 时，短竖线的和才会不变。
我们可以发现，在 2、3 是连续的时，答案为 2 。 于是，就有了下面的代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    bool f=0,flg=0;
    int cnta=0,cntb=0,n,m;
    cin>>n>>m;
    for(int i=n;i<=m;i++)
    {
        if(i%10==2)
            f=1;
        else if(i%10==3&&f)
        {
            cout<<2;
            return 0;
        }
    }
    cout<<1;
    return 0;
}


仔细观察题目，每个以 2 开头 后接 9 加一时，它的短竖线的和也是不变的。

满分代码

#include<bits/stdc++.h>
#include<windows.h>
#define int long long
using namespace std;
bool f;
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=100;i<=1e18;i*=10)
    {
        if(n%i<=3*i/10-1&&m%i>=3*i/10)
        {
            cout<<2;
            return 0;
        }
    }
    for(int i=n;i<=m;i++)
    {
        if(i%10==2)
            f=1;
        else if(i%10==3&&f)
        {
            cout<<2;
            return 0;
        }
    }
    cout<<1;
    return 0；
}

完结撒花