ZeroJudge 解題筆記：g488. COVID-101

作者：王一哲
日期：2025年11月6日


ZeroJudge 題目連結：g488. COVID-101

解題想法

題目給的遞迴式為 $$ n(x) = n(x-1) + x^2 - x + 1 $$ 列出前幾項找規律 $$ \begin{align*} n(1) &= 1\\ n(2) &= n(1) + 2^2 - 2 + 1\\ n(3) &= n(2) + 3^2 - 3 + 1\\ n(4) &= n(3) + 4^2 - 4 + 1\\ n(5) &= n(4) + 5^2 - 5 + 1\\ n(x) &= n(x-1) + x^2 - x + 1 \end{align*} $$ 將以上的式子相加，可以看出 $n(1)$ 到 $n(x-1)$ 會兩兩對消，因此 $$ \begin{align*} n(x) &= (2^2 + 3^2 + 4^2 + \dots + x^2) - (2 + 3 + 4 + \dots + x) + x\\ &= \sum_{i = 1}^x i^2 - 1 - \sum_{i=2}^x i + x\\ &= \frac{x(x+1)(2x+1)}{6} - \frac{(x+2)(x-1)}{2} + x - 1 \end{align*} $$

Python 程式碼

公式解，使用時間約為 27 ms，記憶體約為 3.3 MB，通過測試。

x = int(input())
print(x*(x+1)*(2*x+1)//6 - (x+2)*(x-1)//2 + x - 1)

遞迴解，使用時間約為 42 ms，記憶體約為 3.3 MB，通過測試。

def func(x):
    if x == 1: return 1
    return func(x-1) + x*x - x + 1

print(func(int(input())))

C++ 程式碼

公式解，使用時間約為 2 ms，記憶體約為 72 kB，通過測試。

#include <cstdio>

int main() {
    int x; scanf("%d", &x);
    printf("%d\n", x*(x+1)*(2*x+1)/6 - (x+2)*(x-1)/2 + x - 1);
    return 0;
}

遞迴解，使用時間約為 2 ms，記憶體約為 112 kB，通過測試。

#include <cstdio>

int func(int x) {
    if (x == 1) return 1;
    return func(x-1) + x*x - x + 1;
}

int main() {
    int x; scanf("%d", &x);
    printf("%d\n", func(x));
    return 0;
}