题解：关注 small_lemon_qwq 谢谢喵

· · 题解

打表，我和你拼了！

正解，我和你拼了！

众所周知，打表是一种非常优秀的算法，只是有以下缺点：

所以我们为了不被骂，只能另寻他法。

令 n=X。

注意到，从 70 报数报到 79，每报一次数报数的方向就反一下，那么实际相当于报数的方向不变，并且报 80 的人就是报 70 的人，所以可以考虑直接将其优化掉，遇到非个位出现 7 直接将它变成 8，但是注意变成 8 不要超过了 n。

这样时间复杂度就是了 \operatorname{O}(9^8\times10\times9)=\operatorname{O}(3874204890)\approx\operatorname{O}(4\times10^9)，显然无法通过，考虑优化检查是否存在为 7 的位这一步。

这个题解启发我们可以用高精度动态求检查是否存在为 7 的位，但我们不仅要判断是否存在为 7 的位，还要求出这个为 7 的位。我的做法是开一个栈存储所有为 7 的位，动态更新这个栈，查询时直接返回栈顶（如果有）。

考虑计算时间复杂度，\operatorname{O}(9^8\times10+111111111)=\operatorname{O}(541578321)\approx\operatorname{O}(5\times10^8)，其中 111111111 是高精度进位次数，卡一下午常就过了。

注意 C++11 和 C++14(GCC 9) 的区别。

#include<bits/stdc++.h>
using namespace std;
int d=1,x;
unsigned n,i=1,num[10]={1};
constexpr unsigned p[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
unsigned stk[10],tp;
void update(){
    register int k=0;
    ++num[0];
    tp+=(num[0]==7)-(num[0]==8);
    if(__builtin_expect(num[0]==7,0))stk[tp]=0;
    while(__builtin_expect(num[k]>9,0)){
        num[k]-=10;
        num[++k]++;
        tp+=(num[k]==7)-(num[k]==8);
        if(__builtin_expect(num[k]==7,0))stk[tp]=k;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    // if(n==899999999){
    //  cout<<959;
    //  return 0;
      // }//看清楚，我注释了的
    #ifndef ONLINE_JUDGE
    auto start=clock();
    #endif
    while(__builtin_expect(i<=n,1)){
        x+=d;
        register int tmp=__builtin_expect(tp,0)?stk[tp]:(__builtin_expect(i%7==0,0)-1);
        if(tmp!=-1)d=~d+1;
        if(__builtin_expect(tmp>0,0)){
            if(__builtin_expect(i+p[tmp]<=n,1)){
                i+=p[tmp];
                ++num[tmp];
                --tp;
            }else{
                if((n-i)&1)x+=d;
                break;
            }
            x+=d;
            d=~d+1;
            continue;
        }
        ++i,update();
    }
    cout<<(x%1337+1336)%1337+1;
    #ifndef ONLINE_JUDGE
    cout<<"\n"<<clock()-start;
    #endif
    return 0;
}

这个代码 C++14(GCC 9) 会 TLE，不知道为什么，很玄学。

这样在 n=10^9 时要跑 1.1s，所以请后人继续努力，或增大时限。