题解 CF1829G Hits Different

· · 题解

大家好，我是 CQ-C2024 蒟蒻 CJH。

题意

本题有多组数据。

有一个高 2023 层的数字金字塔。

你击中了一个编号为 n 的罐子，请你求出该罐子上方编号的平方的和。

分析

设 l_i 为 i 左上方罐子的编号，r_i 为 i 右上方罐子的编号，f_i 为击中罐子 i 时的答案。

所以可以很容易地发现几点：

  1. 该罐子编号为 1，不存在左上方和右上方。
  2. 第 x 层最左侧罐子的 r_{\frac{x(x+1)}{2}-x+1}=\dfrac{x(x-1)}{2}-x+2，不存在左上方。
  3. 第 x 层最右侧罐子的 l_{\frac{x(x+1)}{2}}=\dfrac{x(x-1)}{2}，不存在右上方。
  4. 其余罐子 i 的 l_i=r_{i-1}，r_i=l_i+1。

经过观察 f_i=f_{l_i}+f_{r_i}-f_{l_{r_i}}+i^2，因为如果只加左上方和右上方的答案，就会有一部分重合，所以需要减去 i 上方的上方的罐子的答案。

然后预处理 1 \sim n 的相应答案即可。

总体时间复杂度 O(n+t)，竟然成为最优解！

注意事项

注意 10^6 \times 10^6 = 10^{12} > 2^{31}-1，所以计算出的答案需要 long long 存储。

代码

//the code is from chenjh
#include<cstdio>
#define MAXN 1000001
typedef long long LL;
int l[MAXN],r[MAXN];//左上方和右上方。
LL f[MAXN];//答案数组。
void solve(){
    int n;scanf("%d",&n);
    printf("%lld\n",f[n]);
}
int main(){
    for(int i=2;(((LL)i*(i+1))>>1ll)<MAXN+i-1;i++)r[((i*(i+1))>>1)-i+1]=((i*(i-1))>>1)-i+2;//预处理第二点。
    for(int i=2;(((LL)i*(i+1))>>1ll)<MAXN;i++)l[(i*(i+1))>>1]=(i*(i-1))>>1;//预处理第三点。
    for(int i=2;i<MAXN;i++){
        if(l[i]||r[i]) continue;//如果左上方或右上方编号已经处理过，说明是边界节点，直接跳出即可。
        l[i]=r[i-1],r[i]=l[i]+1;//预处理第四点。
    }
    f[1]=1;//记得赋初值！
    for(int i=2;i<MAXN;i++) f[i]=f[l[i]]+f[r[i]]-f[l[r[i]]]+(LL)i*i;//预处理 f 数组。
    int T;scanf("%d",&T);
    while(T--) solve();
    return 0;
}