题解：P13964 [VKOSHP 2024] Colony of Bacteria

分析

描述了一种细菌的扩展行为，其遵循：偶数秒时向

8

个方向扩展；在奇数秒时，只向

4

个正方向扩展。

我们需要计算在第

k

秒时，细菌占据的格子总数。

思路

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

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

时间	扩展到的格子数
$1$	$1$
$2$	$9$
$3$	$21$
$4$	$45$
$5$	$69$

首先合理推测，在

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 见祖宗。

CPP

#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;
}

题解：P13964 [VKOSHP 2024] Colony of Bacteria

文章操作

分析

思路

相关推荐

评论

题解：P13964 [VKOSHP 2024] Colony of Bacteria