题解：P13964 [VKOSHP 2024] Colony of Bacteria

· · 题解

题目

提供一个 O(1) 的解法。

由于题目的增量与秒数的奇偶性有关，我们索性按奇偶分情况讨论。我们只需要求出从 1 到 k 所有奇数秒对于前一秒的增量之和 sum_{Odd} ，以及所有偶数秒对于前一秒的增量之和 sum_{Even} ，最后将两者相加即为答案。

先来看 k 为奇数的情况：

第一列表示秒数 第二列表示这一秒对于上一秒的增量。 秒数 增量
1 1
3 12
5 24
7 36

不难发现，这一秒的增量就是 \left \lfloor \frac{k}{2} \right \rfloor\times12 的结果。 我们要计算的是从 1 到 k 所有奇数秒对于前一秒的增量之和，也就是 sum_{Odd} 。不难发现其实就是

1+12\times(1+2+3+4+......\left \lfloor \frac{k}{2} \right \rfloor)

我们利用等差数列求和公式很容易就能 O(1) 算出。 我们称 n 为 \left \lfloor \frac{k}{2} \right \rfloor 。

1+12\times(\frac{n\times(n+1)}{2}) =1+6n(n+1)

再来看 k 为偶数的情况：

第一列表示秒数 第二列表示这一秒对于上一秒的增量。 秒数 增量
2 8
4 24
6 40
8 56

依旧发现增量是 8\times(k-1) 。 我们要计算的是从 1 到 k 所有偶数数秒对于前一秒的增量之和，也就是 sum_{Even} 。不难发现其实就是

8\times(1+3+5+7+......(k-1)) =8\times \frac{k\times \frac{k}{2}}{2} =2k^2

接下来只需要计算 sum_{Odd} 和 sum_{Even} 的和即可。若 k 为偶数，那么额外计算一下 1 到 k-1 的 sum_{Odd} 即可，反之同理。

下面是代码。

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long k;
    cin>>k;
    if(k&1){
        long long n=k/2;
        long long sum_Odd=1+6*n*(n+1);
        long long sum_Even=(k-1)*(k-1)*2;
        cout<<sum_Odd+sum_Even;
    }else{
        long long sum_Even=k*k*2;
        long long n=(k-1)/2;
        long long sum_Odd=1+6*n*(n+1);
        cout<<sum_Odd+sum_Even;
    }
    return 0;
}