大概没你们说得复杂吧......

\(Part\;1\) \(Nim\)游戏

大家都对异或和感到懵逼吧（排除大佬），其实很简单，用\(SG\)函数打表计算即可解决：

抛个板子：

void get_sg(int n)

{

    memset(sg,0,sizeof(sg));

    for(int i=1;i<=n;i++)

    {

        memset(S,0,sizeof(S));

        for(int j=1;f[j]<=i&&j<=m;j++)

        {

            S[sg[i-f[j]]]=1;

        }

        for(int k=0;k<=n;k++)

        {

            if(!S[k])

            {

                sg[i]=k;

                break;

            }

        }

    }

}

//S[]代表能被表示的数

//f[]代表可以转移的方法

然后发现\(sg[a_i]=a_i\)（\(a_i\)为集合中元素个数），根据博弈论的常识知识即可知道答案。

\(Part\;2\) 取火柴游戏

一眼看出是\(Nim\)游戏的板子题，于是先上：

#include<iostream>

#include<algorithm>

#include<cstdio>

using namespace std;

int n,a[500005];

int sum=0;

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum^=a[i];

	if(sum) printf("win\n");

	else printf("lose\n");

	return 0;

}

这人真粗鲁

不过仔细一看，还需要输出方案，其实也是很水的，证明如下：

我们都知道异或运算是满足结合律的，即\(a\;xor \;b\; xor\;c=a\;xor(b\;xor\;c)\),

并且\(a\;xor\;a=0\),这是为啥？

考虑异或定义：二进制位相同为\(0\),不同为\(1\)，显然同一个数二进制是一模一样的，异或为\(0\)。

根据上述，可得\(s\;xor\;a\;xor\;a=s\),这也就是说，异或的逆运算是他自己。

不过和这题有啥关系呢？

优化！

我们考虑求出所有数的异或和，每次用异或踢掉一个数，判断其余数的异或和\(sum\)能否被异或为\(0\)，显然两数\(x,y\)异或和为\(0\)，当且仅当\(x=y\).

解题

显然如果一个人在他的必胜态操作，使另一个人进入必败态，他就成功了，即异或和为\(0\)，这样像前缀和一样处理出异或和，然后每次\(O(1)\)的转移就好了。，不过注意踢掉暂时不用的，若未找到姐解，再异或回来。

其他

这题是有些贪心的思路的，显然对一堆火柴操作，只有一个可行解（由于只有相同的数才异或为\(0\)），问题是如何让堆序最小，那从第一堆开始算就好了，找到的第一组解一定是最优解鸭\(qwq\)。

粘上简单修改的代码即可，复杂度是\(O(N)\)的，常数较小吧，足以通过此题。

\(Code\):

#include<iostream>

#include<algorithm>

#include<cstdio>

using namespace std;

int n,a[500005];

int sum=0;

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum^=a[i];

	if(sum)

	{

		sum^=a[1];

		for(int i=1;i<=n;i++)

		{

			if(sum<=a[i])//找到可行解

			{

				printf("%d %d\n",a[i]-sum,i);

				for(int j=1;j<=n;j++)

				{

					if(j==i) printf("%d ",sum);

					else printf("%d ",a[j]);

				}

				return 0;

			}

			sum=sum^a[i]^a[i+1];//这是精髓，注意把试验过的异或回来，把下一个数踢掉

		}

	}

	else printf("lose\n");

	return 0;

}

都看了，没个赞不好吧，大佬你觉得呢？

巴特西

题解：luogu P1247

大概没你们说得复杂吧......

\(Part\;1\) \(Nim\)游戏

\(Part\;2\) 取火柴游戏

优化！

解题

其他

\(Code\):

最新文章

热门文章