自动搬运

查看原文

来自洛谷，原作者为

	良心WA题人 啦叭叭叭 啾啾啾啦叭叭叭

搬运于2025-08-24 23:08:28，当前版本为作者最后更新于2024-04-01 21:37:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

因为只能操作最左侧的棋子，则抛开无法操作的位置，只会有位置 $i,i+1,i+2$ 有值。

记 $f_{i,j,k,l,0/1}$ 表示位置 $i,a_i=j,a_{i+1}=k,a_{i+2}=l$，当前操作者是 Alice/Bob 时的操作次数。有转移

$$\left\{\begin{matrix} f_{i,j,k,l,0}=\min(f_{i,j-2,k+1,l,1},f_{i,j-2,k,l+1,1})+1\ (j\ge 2) \\ f_{i,j,k,l,0}=f_{i+1,k,l,0,0}\ (j<2) \end{matrix}\right. $$

最后一维为 $1$ 时同理。

注意到第一维最多只会有 $2\times \log n$ 次就会变成 $0$，所以只需要枚举到 $2\times\log n$ 即可。

然后发现貌似不太好优化了。注意到，当前位置无论如何操作，操作次数都是固定的。可以考虑位置 $i$ 会分别操作多少个到后面的位置。

Key Lemma: $a_i$ 个棋子除了最后一轮操作以外，无论 $a_{i+1}$ 和 $a_{i+2}$ 一开始放了多少个，每轮一定是 Alice 和 Bob 分别在 $a_{i+1}$ 和 $a_{i+2}$ 各放一个。

此时去掉原 dp 第三维，令最终放置 $a_{i+1}$ 了 $k$ 个，若假设定理成立，令 $t=f_{i+1,a_{i+1}+k,a_{i+2}+\left\lfloor \frac{a_i}{2}\right\rfloor-k,?}$（问号由当前状态的先后手和 $\left\lfloor \frac{a_i}{2}\right\rfloor$ 奇偶性决定）。

考虑反证法，若最后结果 $f_{i+1,a_{i+1}+k,a_{i+2}+\left\lfloor \frac{a_i}{2}\right\rfloor-k,?}\le t$，则最终情况对 Alice 有利，此时假设 $k\ge \left\lfloor \frac{a_i}{2}\right\rfloor-k$（另一种同理）：

• 若 $k-(\left\lfloor \frac{a_i}{2}\right\rfloor-k)\le 2$，此时可以通过除最后一轮外二人轮流在 $a_{i+1}$ 和 $a_{i+2}$ 放置来达到，则有 $f_{i+1,a_{i+1}+k,a_{i+2}+\left\lfloor \frac{a_i}{2}\right\rfloor-k,?}= t$，原命题得证。
• 若 $k-(\left\lfloor \frac{a_i}{2}\right\rfloor-k)> 2$，则 $2\times k>2+\left\lfloor \frac{a_i}{2}\right\rfloor$，$k>1+\left\lfloor \frac{a_i}{4}\right\rfloor$。而一个人在一轮操作中最多进行 $\left\lfloor \frac{a_i}{4}\right\rfloor+1$ 次操作，则在放置 $a_{i+1}$ 的棋子中必然有 Bob 参与，此时可以让 Bob 参与操作的棋子放到 $a_{i+2}$ 使得最终结果不为 $f_{i+1,a_{i+1}+k,a_{i+2}+\left\lfloor \frac{a_i}{2}\right\rfloor-k,?}$，与假设相悖，所以原命题得证。

此时可以得知在最后一轮之前，$a_{i+1}$ 和 $a_{i+2}$ 各增加了 $\left\lfloor\dfrac{\left\lfloor \frac{a_i}{2}\right\rfloor-1}{2}\right\rfloor=tmp$。考虑 $\left\lfloor \frac{a_i}{2}\right\rfloor$ 的奇偶性（下面假设是 Alice 先操作，Bob 操作同理）：

• 奇数：最后一步是先手操作，则先手可以决定最后放在 $a_{i+1}$ 还是 $a_{i+2}$。转移 $f_{i,j,k,0}=\min(f_{i+1,k+tmp+1,tmp,1},f_{i+1,k+tmp,tmp+1,1})$。
• 偶数：最后一步是后手操作，则后手可以选择是让二者相等还是其中一个多 $2$。若后手会选择让其中一个多 $2$，则先手会为了让后手更小于是会选择更小的一个。转移 $f_{i,j,k,0}=\max(f_{i+1,k+tmp+1,tmp+1,0},\min(f_{i+1,k+tmp+2,tmp,0},f_{i+1,k+tmp,tmp+2,0}))$。

注意到，有用的 $j,k$ 两维看上去是很少的！事实上也确实如此。

可以看出在 $j+k$ 相同时，前一个访问后一个位置的 $j-k$ 的值是连续的。则只有 $j-k$ 是最大值和最小值时在下一维才会产生多出来的状态数。每一个位置多出来两个，一共多出来 $\log n$ 级别个，每个会进行 $\log n$ 级别次转移，所以是 $\log^2 n$ 级别的。

而 $j+k$ 的个数最多会有多少呢？类似的，一次只会以原来的基准多或少 $1$，所以也是连续的且只有最大和最小的会扩展出新的，是 $\log n$ 级别的。

总时间复杂度 $O(\log^3 n)$。使用 map 是 $O(\log^4 n)$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
map<tuple<int,int,int,int>,int>f;
int dp(int i,int j,int k,int l)
{
	if(f.count({i,j,k,l}))
		return f[{i,j,k,l}];
	int&d=f[{i,j,k,l}];
	if(!j&&!k)
		return d=0;
	int t=j/2;
	if(t%2)
	{
		if(!l)
			return d=min(dp(i+1,k+t/2,t/2+t%2,1),dp(i+1,k+t/2+t%2,t/2,1))+t;
		return d=max(dp(i+1,k+t/2,t/2+t%2,0),dp(i+1,k+t/2+t%2,t/2,0))+t;
	}
	d=dp(i+1,k+t/2,t/2,l)+t;
	if(t/2)
	{
		if(!l)
			d=max(d,min(dp(i+1,k+t/2-1,t/2+1,0),dp(i+1,k+t/2+1,t/2-1,0))+t);
		else
			d=min(d,max(dp(i+1,k+t/2-1,t/2+1,1),dp(i+1,k+t/2+1,t/2-1,1))+t);
	}
	return d;
}
signed main()
{
	int t;
	scanf("%lld",&t);
	while(t--)
	{
		int n;
		scanf("%lld",&n);
		printf("%lld\n",dp(1,n,0,0));
	}
	return 0;
}