洛谷 P1654 OSU!

ELLIAS

Olympiad in Informatics

Released at Jul 27, 2018

views

洛谷 P1654 OSU! 滚动数组

本题可以使用滚动数组进一步优化空间.

空间多精贵.

订正一下本题题干:

小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的，每个人每次可以从一堆石子中取出若干个石子，每次取石子的个数有限制，谁不能取石子时就会输掉游戏。 小H先进行操作，他想问你他是否有必胜策略，如果有，第一步如何取石子。

优化分析

看到楼下大佬的代码，用庞大的数组会造成大量的内存浪费. 从算法中可以看到，一个状态只从它前一个状态转移而来，就可以使用滚动数组节约空间.

第一次使用数组取 0 位， 每次转移将 pos ^ 1. 代码如下

1
2
3
4
5
6
7
8

for (register int i = 1; i <= n; ++ i, pos ^= 1)
{
	exp = !pos, k = getdou ();
	x[pos] = (x[exp] + 1) * k;
	y[pos] = (y[exp] + 2*x[exp] + 1) * k;
	v[pos] = v[exp] + (3*x[exp] + 3*y[exp]+1) * k;
}

内容遵循 Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License.

本文永久链接：https://brynhild.online/Luogu-P1654-OSU/

Updated at Sep 2, 2020