我今天突然发现小苹果就是蒟蒻

所以今天来探讨一下思路

小苹果有两种做法 一种暴力模拟 一种蒟蒻手算 暴力我相信大家都会

#pragma GCC optimize (3)//   O3~1优化
#pragma GCC optimize (2)
#pragma GCC optimize (2)
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>//               浅加个头文件
using namespace std;
int n;
bool f[100000001];//              判断第i个是否拿过
int main()
{
	std::ios::sync_with_stdio(false);//优化2
	cin>>n;
	int x=n;
	int o=0;
	int ans=0;
	while(x>0)//                  模拟直到全拿完
	{
		ans++;//                总天数++
		int l=0;
		int y=0;
		for(int i=1;i<=n;i=y)//模拟拿苹果
		{
			while(f[i])i++;
			f[i]=1;
			l++;
			if(i==n)o=ans;
			y=i;
			int p=0;
			while(p<3)// 对拿过的特殊判断
			{
				y++;
				if(f[y])continue;
				p++;
			}
		}
		x-=l;//                更新苹果数
	}
	cout<<ans<<' '<<o;
	return 0;
}

但是这样的话100%过不了 Because........ 我试过：） 数组必爆！！！！！！！

那这时候蒟蒻手算就有了它存在的意义... 废话不多说

上代码！！！

#pragma GCC optimize (3)//        O1~3优化
#pragma GCC optimize (2)
#pragma GCC optimize (2)
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>//                     头文件看着打
using namespace std;
int n;
int main()
{
	std::ios::sync_with_stdio(false);//   优化
	cin>>n;
	int x=n;
	int o=0;
	int ans=0;
	while(x>0)//                              模拟
	{
		ans++;
		if((x-1)%3==0&&!o)o=ans;
		x-=(x-1)/3+1;//          见图1
	}
	cout<<ans<<' '<<o;
	return 0;
}

图1

当有8颗苹果时

day0

. . . . . . . .

day1

* . . * . . * . 这时一共拿走了3颗

day1可以看作 * 和. . * . . * .

前面的可以表示为1；

后面的可以表示为(x-1)/3

一共是1+(x-1)/3

day2

#*.#.*#.

也可以为

*..*.

同样适用于前式

而判断第n颗苹果是否被拿

只要判断(x-1)是不是3的倍数就行了

这条题解里的信息全是真的

一条不对你来打我✔✔✔✔✔✔✔