P9748: A very noob O(n^0.7304) solution for 2023 CSP-J2 T1
035966_L3
·
·
题解
UPD：将写错的 \dfrac{n}{(\dfrac{2}{3})^x} 改为 n \cdot (\dfrac{2}{3})^x，并解决了代码在输入 (10^6,3^{13}) 时可能会 WA 的问题。
我竟然差点不会 CSP-J2 T1 了……以下是考场做法。
枚举（其实不难证明）可知，1 轮过后，n 个苹果被拿走 \lfloor\dfrac{n}{3}\rfloor 个；x 轮过后，剩下的苹果以 3^x 为周期，且剩下大约 \lfloor n \cdot (\dfrac{2}{3})^x \rfloor 个苹果。例如：
于是，我们先暴力模拟 3^x 个苹果拿 x 轮后的结果，算出周期，接着选出剩下大约 \lfloor n \cdot (\dfrac{2}{3})^x \rfloor 个苹果继续暴力模拟即可。
当 3^x=n \cdot (\dfrac{2}{3})^x 时最优，显然此时 x=\log_3 n \cdot\dfrac{\log 3}{\log 3+\log 3-\log 2}，时间 / 空间复杂度为 O(3^x)=O(n^{0.7304})。
**AC Code：**
```cpp
#include<bits/stdc++.h>
using namespace std;
queue<int> q,qq;
int main()
{
int n,ans1=0,ans2=0,u,c;
cin>>n;
int mod=1;
for(int i=1;i<=13;i++)
mod*=3;
if(n<=mod)
{
for(int i=1;i<=n;i++)
q.push(i);
int rounds=0;
while(!q.empty())
{
rounds++;
c=q.size();
for(int i=1;i<=c;i++)
{
u=q.front();
q.pop();
if(i%3!=1) q.push(u);
else if(u==n) ans2=rounds;
}
}
ans1=rounds;
}
else
{
for(int i=1;i<=mod;i++)
q.push(i);
for(int rd=1;rd<=13;rd++)
{
c=q.size();
for(int i=1;i<=c;i++)
{
u=q.front();
q.pop();
if(i%3!=1) q.push(u);
else if(n%mod==u%mod) ans2=rd;
}
}
int sz=q.size();
for(int st=0;st<=n;st+=mod)
for(int j=1;j<=sz;j++)
{
u=q.front();
q.pop();
q.push(u);
if(st+u>n) break;
qq.push(st+u);
}
int rounds=13;
while(!qq.empty())
{
rounds++;
c=qq.size();
for(int i=1;i<=c;i++)
{
u=qq.front();
qq.pop();
if(i%3!=1) qq.push(u);
else if(u==n) ans2=rounds;
}
}
ans1=rounds;
}
cout<<ans1<<' '<<ans2;
return 0;
}
```