AtCoder AGC002E Candy Piles (博弈论)

神仙题。。表示自己智商不够想不到。。。

好几次读成最后拿的赢了，导致一直没看懂题解。。。

题目链接: https://atcoder.jp/contests/agc002/tasks/agc002_e

题解: 首先所有数从大到小排序，如果把每个数上面画出高度等于它数值的柱状图，那么就可以得到一条从左上角走到右下角的Lattice Path, 两人从原点开始每一步操作就相当于向右或向上走一格，走到边界的输。

那么朴素的DP是\(O(\sum a_i)\)的，考虑优化: 找规律可得从一个不在边界上的点每次往斜下方走一格，那么走的路径上的胜负状态都一样。所以可以从原点走到离边界恰好一格的地方。只需要求这个地方的胜负状态。

如果这里为先手必败，那么其上方和右侧均为先手必胜。找规律可得一个横着或者竖着的边界，边界上全为胜，边界的内部一格胜负交替，因此根据奇偶性可以判断。

很抱歉没有图片我也讲不太清楚，可以参考官方题解的图片。

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cassert>

#include<algorithm>

#include<vector>

using namespace std;

const int N = 4e5;

int a[N+3];

int d[N+3];

int dp[N+3][10];

vector<int> b;

int n;

bool cmp(int x,int y) {return x>y;}

int main()

{

	scanf("%d",&n);

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

	sort(a+1,a+n+1,cmp);

	int pos = 0;

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

	{

		if(a[i]>=i && a[i+1]<=i) {pos = i; break;}

	}

//	printf("pos=%d\n",pos);

	int len1 = 0;

	for(int i=pos+1; i<=n; i++) {if(a[i]>pos-1) len1++;}

	int len2 = a[pos]-pos;

//	printf("len1=%d len2=%d\n",len1,len2);

	if((!(len1&1)) && (!(len2&1))) printf("Second");

	else printf("First");

	return 0;

}

巴特西

AtCoder AGC002E Candy Piles (博弈论)

代码

最新文章

热门文章