自动搬运

查看原文

来自洛谷，原作者为

	Leap_Frog 是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了

搬运于2025-08-24 21:46:15，当前版本为作者最后更新于2020-02-07 16:09:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Problem.

起始状态：第$i$个瓶子里装了$a_i$个巧克力豆。
结束状态：前$n-1$个瓶子都空了，只有第$n$个瓶子放了巧克力豆。
状态转移：选$i<j\le k$，然后在第$i$个瓶子里取走一颗，在第$j$和第$k$个瓶子里加上一颗。

Solution.

显然，这是个博弈问题。

看到博弈问题就想到SG函数，因为笔者只会这种博弈。

这是个Multi-SG游戏。
但是可惜啊，Multi-SG并不是什么有什么套路的题目。

我们突然发现，$1<n\le21$。
所以我们可以考虑dp。
dp转移时可以直接暴力枚举$i,j,k$。
复杂度是$O(N^3)$能过。

然后直接套用SG函数就好了。

Coding.

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n,ans,t,sg[N],vis[N],a[N];
inline void work(int ans)
{
	int tot=0,ii=-1,jj,kk;
	for(int i=n;i>=1;i--)
		for(int j=i-1;j>=1;j--)
			for(int k=j;k>=1;k--)
				if((ans^sg[i]^sg[j]^sg[k])==0)
				{
					tot++;
					if(ii==-1) ii=n-i,jj=n-j,kk=n-k;
				}
	printf("%d %d %d\n%d\n",ii,jj,kk,tot);
}
int main()
{
	sg[1]=0;//预处理
	for(int i=2;i<=N-4;i++)
		for(int j=1;j<=i;j++)
			for(int k=j;k<i;k++)//暴力枚举i,j,k
			{
				vis[sg[j]^sg[k]]=i;//SG函数的转移
				for(sg[i]=0;vis[sg[i]]==i;sg[i]++);
			}
	for(scanf("%d",&t),ans=0;t--;ans=0)
	{
		scanf("%d",&n);
		for(int i=n;i>=1;i--) scanf("%d",a+i);
		for(int i=n;i>=1;i--) if(a[i]&1) ans^=sg[i];//这里是一个优化，每个数可以直接变成对二取模后的值。
		if(!ans) puts("-1 -1 -1\n0");else work(ans);
	}
	return 0;
}

完结散花，不要脸求赞