题解：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}

即可，反之同理。

下面是代码。

CPP

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

题解：P13964 [VKOSHP 2024] Colony of Bacteria

文章操作

先来看 $k$ 为奇数的情况：

再来看 $k$ 为偶数的情况：

相关推荐

评论

题解：P13964 [VKOSHP 2024] Colony of Bacteria

文章操作

先来看 kkk 为奇数的情况：

再来看 kkk 为偶数的情况：

相关推荐

评论

先来看 $k$ 为奇数的情况：

再来看 $k$ 为偶数的情况：