首页 > 代码库 > hdu 5088 Revenge of Nim II(高斯消元)
hdu 5088 Revenge of Nim II(高斯消元)
题目链接:hdu 5088 Revenge of Nim II
题目大意:Nim游戏的变形,因为游戏很不公平,所以现在转变规则,后手可以选取若干堆石子剔除,剩下堆的石子用
来进行游戏,问说后手可能胜利吗。
解题思路:其实即为取出非0堆石子,使得Nim和为0。因为是Nim和(亦或),所以以每个位建立方程,列出40个方
程,进行亦或形式的高斯消元,因为全0肯定为一解,所以方程肯定有解,那么存在多解的情况即为存在自有变元。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000;
typedef long long ll;
typedef int Mat[maxn+5][maxn+5];
int gauss (Mat A, int m, int n) {
int i = 0, j = 0, k, r, u;
while (i < m && j < n) {
r = i;
for (k = i; k < m; k++) {
if (A[k][j]) {
r = k;
break;
}
}
if (A[r][j]) {
if (r != i) {
for (k = 0; k <= n; k++)
swap(A[r][k], A[i][k]);
}
for (u = i + 1; u < m; u++) {
if (A[u][j])
for (k = i; k <= n; k++)
A[u][k] ^= A[i][k];
}
i++;
}
j++;
}
return n - i;
}
int N;
Mat a;
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
ll x;
scanf("%d", &N);
memset(a, 0, sizeof(a));
for (int i = 0; i < N; i++) {
scanf("%I64d", &x);
for (int j = 0; j < 45; j++)
a[j][i] = (x>>j)&1;
}
int ans = gauss(a, 45, N);
printf("%s\n", ans ? "Yes" : "No");
}
return 0;
}
hdu 5088 Revenge of Nim II(高斯消元)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。