首页 > 代码库 > [CQOI2013]新Nim游戏 Solution
[CQOI2013]新Nim游戏 Solution
题目大意:
传统的Nim游戏是这样的:有一些火柴堆,每堆都有若干根火柴(不同堆的火柴数量可以不同)。两个游戏者轮流操作,每次可以选一个火柴堆拿走若干根火柴。可以只拿一根,也可以拿走整堆火柴,但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。
本题的游戏稍微有些不同:在第一个回合中,第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿,但不可以全部拿走。第二回合也一样,第二个游戏者也有这样一次机会。从第三个回合(又轮到第一个游戏者)开始,规则和Nim游戏一样。
如果你先拿,怎样才能保证获胜?如果可以获胜的话,还要让第一回合拿的火柴总数尽量小。
Sol:
我们第一次拿完后,要使得剩下的火柴中不存在异或和为0的子集,否则对方会将先手必败的状态留给我们。
因此我们需要寻求极大的线性无关组,答案即为总和减去极大线性无关组的权值和。
显然存在线性无关组,因此必然存在解。
那么如何求解极大线性无关组呢?
我们能够证明这是一个拟阵,因此只需要从大到小排序,依次贪心的添加到当前集合就可以了。
(之后再加上拟阵的证明。。。)
因此我们采用在线维护线性基的方法判断当前的数能否加入集合。
Code:
#include <cstdio> #include <cstring> #include <climits> #include <algorithm> using namespace std; #define N 110 int n; int a[N], w[N], ins[30], sav[N], top; int main() { scanf("%d", &n); register int i, j, k; for(i = 1; i <= n; ++i) scanf("%d", &a[i]); sort(a + 1, a + n + 1); long long tot = 0; for(i = 1; i <= n; ++i) tot += (w[i] = a[i]); long long ans = 0; for(i = n; i >= 1; --i) { for(j = 29; j >= 0; --j) { if ((a[i] >> j) & 1) { if (!ins[j]) { ins[j] = i; for(k = 1; k <= top; ++k) if ((a[sav[k]] >> j) & 1) a[sav[k]] ^= a[i]; sav[++top] = i; break; } else a[i] ^= a[ins[j]]; } } if (a[i]) ans += w[i]; } printf("%lld", tot - ans); return 0; }
[CQOI2013]新Nim游戏 Solution
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。