[CSP-J 2023] 小苹果 题解

讲解

先讲暴力

首先这题第一眼暴力，枚举每一次应该拿走的苹果，每次删除这个苹果。

如果拿到了最后一个苹果，记录一下即可。由于删除次数过于多，可以考虑链表。

时间肯定爆炸，期望得分 $60pts$。

---

先不考虑编号为 $n$ 的苹果是多久拿的。

设苹果的数量是 $8$，拿走苹果的情况如下：

1 2 3 4 5 6 7 8
^     ^     ^

拿走的情况可以看作周期问题，可以分成三个三个周期来取走每一个周期的第一个苹果。如下图：

1 2 3 | 4 5 6 | 7 8
^       ^       ^

所以每次拿走苹果的个数是 $\lceil \frac{n}{3} \rceil$，其中 $n$ 是当前苹果的数量。

然后考虑编号为 $n$ 的苹果是多久拿的。

这里给出一个特殊的例子（后面就知道为什么特殊了），苹果数量是 $7$：

1 2 3 4 5 6 7
^     ^     ^ 

分组情况是这样的：

1 2 3 | 4 5 6 | 7
^       ^       ^

可以看到这时后面编号为 $7$ 的苹果被“孤立”了，这是因为最后一组只有 $n$ 编号的那一个苹果了，也说明了当 $n$ 除以 $3$ 的余数是 $1$ 时，最后一个苹果会被取走。$n$ 表示这个时候苹果的数量。

按照结论模拟即可，期望得分 $100pts$。

需要注意的是：今年的 CSP 的题在 ACGO 上交都要加上 freopen 和 fclose。

赛时代码：

//O(?)mo ni
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int main(){
 	freopen("apple.in","r",stdin);
 	freopen("apple.out","w",stdout);
	int n;
	cin >> n;
	int cnt=n;
	int ans1=0,ans2=-1;
	while (cnt!=0){
		++ans1;
		int t=ceil(cnt/3.0);
		if (ans2==-1 && cnt%3==1){
			ans2=ans1;
		}
		cnt-=t;
	}
	cout<<ans1<<" "<<ans2<<endl;
 	fclose(stdin);
 	fclose(stdout);
	return 0;
}