P8676 [蓝桥杯 2018 国 A] 自描述序列

· · 题解

数学

很难想的分类讨论，笔者的思路中只有一种能够得到答案。

n \leq 1000000

直接计算 G_1,G_2,G_3 \cdots G_{10^6} 的值，计算完毕后可以回答 n \leq 10^6 的询问。

n \leq 3793540542

利用得到的信息扩展可以求解的范围，发现 G_{10^6}=6137,G_{6137}=264，但 6137 在序列前 10^6 项中只出现 117 次，扩展时需要考虑未出现的 147 个 6137 造成的影响。

为了方便，计算 G_1,G_2,G_3 \cdots G_{10^6+147}，从 G_{10^6+147+1}，即 G_{1000148}=6138 开始扩展。

由 G_{6138}=264 得 \forall \ i \in [10^6+147+1,10^6+147+264],G_i=6138。像这样枚举 [6138,10^6+147] 中每个整数 i 并计算满足 G_j=i 的整数 j 的范围能够得到 n \leq 3793540542 时任意 G_n 的值。

3793540543 \leq n \leq 2 \times 10^{15}

进一步扩展，如果区间 [l,r] 满足 \forall \ j \in [l,r],G_j=i，那么 [l,r] 中的数在 G 中将出现 (r-l+1) \times i 次。

满足 G_j=i 的整数 j 必定为一段连续自然数。

利用以上性质确定 G_n 的值域 [l,r]，该区间不仅需要满足 \forall \ j \in [l,r],G_j=i，还需要满足 G_{l-1} \neq G_l,G_{r+1} \neq G_r。

确定 G_n 值域 [l,r] 的同时可以确定满足 G_k \in [l,r] 的整数 k 的范围 [l',r']，显然 n \in [l',r']。

根据自描述序列的定义，由于 \forall \ j \in [l,r],G_j=i，值域 [l,r] 中的每个数在 G 中都出现 i 次。

根据 n 在区间 [l',r'] 中第 n-l'+1 个位置得到 G_n=l +\left \lceil \frac{n-l'+1}{i} \right \rceil -1 = l+ \left \lfloor \frac{n-l'}{i} \right \rfloor。

结合 n \leq 3793540542 时的做法能够通过本题。

#include<bits/stdc++.h>
using namespace std;
constexpr long long uim=3793540542ll;
constexpr int sta=6138,lim=1000147;
int pos,dp[2000005];//dp[i]存储数列第i项的值  
long long n,ans;
int main(){
    scanf("%lld",&n);
    pos=3,dp[1]=1ll,dp[2]=2ll,dp[3]=2ll;
    for(int i=3;pos+1<=lim;i++)
        for(int j=1;j<=dp[i]&&pos+1<=lim;j++){
            dp[++pos]=i;
            if(pos==n) return printf("%d\n",i),0;
        }
    long long l=lim,r=lim,ls=uim,rs=uim;
    for(int i=sta;i<=lim;i++){
        l=r+1,r+=dp[i];                 //更新j的范围 
        ls=rs+1,rs+=(r-l+1)*i;          //更新k的范围 
        if(n>=l&&n<=r) ans=i;           //找到答案(n<=3793540542)
        if(n>=ls&&n<=rs) ans=l+(n-ls)/i;//找到答案(n>=3793540543)
        if(ans!=0ll) break;
    }
    printf("%lld\n",ans);
    return 0;
}