P1662 数7

TempestJueMu · 2022-04-22 22:01:33 · 题解

首先，看到题目很容易能想到一个模拟代码。

int x;
bool f(int a)//判断a中有无7
{
    while(a)
    {
        if(a%10==7)return 1;
        a/=10;
    }
    return 0;
}
int main()
{
    scanf("%d",&x);
    int now=0,k=1;
    for(int i=1;i<=x;++i)
    {
        now+=k;
        if(now==0)now=1337;
        if(now==1338)now=1;
        if(i%7==0/*整除*/||f(i)/*含7*/)k=-k;
    }
    printf("%d",now);
    return 0;
}

提交后 TLE 了 4 个点，考虑优化。

• 用一个变量记录 \bmod\ 7 的结果，避免每次循环都 \bmod 一次。（据说 % 很慢）

• 用类似高精度的思想，用一个数组记录当前数的每一位数，并用一个变量记录含 7 的个数，可避免每一次都将当前数字分解。

int x,Num_7;//Num_7即当前数中含7的个数
int num[11]={0,1};//高精…？
void Update()//当前数+1
{
    num[1]++;
    if(num[1]==8)Num_7--;//由7变为8，少了一个7
    if(num[1]==7)Num_7++;//多了一个7
    int k=1;
    while(num[k]>9)//处理进位
    {
        num[k]-=10,num[k+1]++;
        k++;
        if(num[k]==8)Num_7--;//同上
        if(num[k]==7)Num_7++;
    }
}
int main()
{
    scanf("%d",&x);
    int now=0,k=1;
    for(int i=1,M=1;i<=x;++i,++M,Update())
    {
        now+=k;
        if(M==7)M=0;
        if(now==0)now=1337;
        if(now==1338)now=1;
        if(!M/*整除*/||Num_7/*含7*/)k=-k;
    }
    printf("%d",now);
    return 0;
}

但还是 T 了 1 个点。

考虑分段，把 10^8 \sim 10^9 的答案分为 10 段，每段分开求解。

根据上面的代码，通过熟练地打表可以打出来。

int fx[]={1,1,-1,-1,1,1,-1,1,-1,1};//方向
int biao[]={0,548,866,892,64,1303,97,1278,1278,960};//编号

AC代码：

int x,Num_7;
int num[11];
void insert(int x)
{
    while(x)
    {
        num[++num[0]]=x%10;
        if(num[num[0]]==7)Num_7++;
        x/=10;
    }
}
void Update()
{
    num[1]++;
    if(num[1]==8)Num_7--;
    if(num[1]==7)Num_7++;
    int k=1;
    while(num[k]>9)
    {
        num[k]-=10,num[k+1]++;
        k++;
        if(num[k]==8)Num_7--;
        if(num[k]==7)Num_7++;
    }
}
int fx[]={1,1,-1,-1,1,1,-1,1,-1,1};//方向
int biao[]={0,548,866,892,64,1303,97,1278,1278,960};//编号
int main()
{
    scanf("%d",&x);
    int s=x/100000000,start=s*100000000+1;//分段
    int now=biao[s],k=fx[s];
    insert(start);//把start存入num数组里，Num_7初始化
    for(int i=start,M=start%7;i<=x;++i,++M,Update())
    {
        now+=k;
        if(M==7)M=0;
        if(now==0)now=1337;
        if(now==1338)now=1;
        if(!M||Num_7)k=-k;
    }
    printf("%d",now);
    return 0;
}