题解：P13964 [VKOSHP 2024] Colony of Bacteria

Forever_Rain · 2025-09-07 21:04:53 · 题解

分析

描述了一种细菌的扩展行为，其遵循：偶数秒时向 8 个方向扩展；在奇数秒时，只向 4 个正方向扩展。

我们需要计算在第 k 秒时，细菌占据的格子总数。

思路

有点懒，看看找规律能否解决该题。

通过观察前几秒的示例数据，我们可以发现一个规律：

首先合理推测，在 k=1 时需要特判，且结果为 1。

对于后四个格子，我们充分发扬人类智慧：

当 k>1 时，结果为 \big[(2k-1)^2-2\big] \left\lfloor \frac{k-1}{2} \right\rfloor \big(\left\lfloor \frac{k-1}{2} \right\rfloor+1 \big)。

然后我们就可以根据规律轻松的写出代码了。

但是十年 OI 一场空，不开 long long 见祖宗。

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long k;
    cin>>k;
    if(k==1) cout<<1;// 特判
    else{// 按照前文所述规律进行计算
        long long r=(k-1)/2;
        long long L=2*k-1;
        cout<<L*L-2*r*(r+1);
    }
    return 0;
}