AGC002E Candy Piles

有n堆石子，每堆石子有$a_i$个，两人轮流操作。要么取走石子最多的一堆，要么将每堆石子取走1个。谁取走最后1个石子，谁就输了。假设两人都足够聪明，求先手必胜还是后手必胜。

对于两种操作：1.每一次去除最大的数 2.每一次将所有的数减一，那么可以按照从小到大排序，化为一个网格图，那么最后得到的图中，每一次操作相当于从(0, 0)点开始每一次向上移动一格或者向右移动一格：

边界上都为必败点，其余点就按照必败和必胜点的方法转移即可。

将边缘点里面一格求出来就可以了，可以发现斜着的必败点和必胜点都是一样的，这样就可以知道，先按照正方形走，也就是别人往上就往右，到了最大的正方形那个点之后，看往上走的最大的和最右的最大的，就可以判断了。

const int N = 1e5 + 5; int n, a[N];bool cmp(int a, int b) { return a > b; }int main() {n = read(); for (int i = 1; i <= n; i++)a[i] = read();sort(a + 1, a + 1 + n, cmp);for (int i = 1; i <= n; i++) {if (a[i + 1] < i + 1) {int cnt = 0;while(a[i + cnt + 1] == i) cnt ++;bool f = ((a[i] - i) & 1) || (cnt & 1);if (f)cout << "First";elsecout << "Second";break;}}return 0; }

总结

以上是生活随笔为你收集整理的AGC002E Candy Piles的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。