2022/04/15 做题记录

[JLOI2015]装备购买

用拟阵可以证明最小线性基就是从小到大尝试插入得到的，所以直接做就行。

第一次用 std::valarray。

code: /code/2022.4.15/P3265.cpp

[SCOI2016]幸运数字

倍增+线性基，线段树应该会超时。

$\text{O}(nlog^2n)$

code: /code/2022.4.15/P3292.cpp

[CQOI2013] 新Nim游戏

第三个回合先手必败的条件是所有火柴异或和为0

于是第二个回合先手必胜的条件就是存在一个非空子集异或和为 0

于是第一个回合先手就只要留下任何一个线性基就行了。

答案就是总数-最大线性基。

code: /code/2022.4.15/P4301.cpp