首页 > 代码库 > HDU5088Revenge of Nim II(高斯消元求自由变元个数)
HDU5088Revenge of Nim II(高斯消元求自由变元个数)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5088
题意:
有n堆石头,可以去掉其中的一些堆(保证至少剩下一堆)问存不存在一种方法使第二个人赢;
分析:
这k个数边构成了一个01矩阵。那么能异或出0的充分条件是对这01矩阵高斯消元以后矩阵的秩小于矩阵的行数(也即存在一行全零,全零行就是异或出来的一行),那么我们只要对这个01矩阵高斯消元即可。
代码如下:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 1005; int step[maxn],dp[maxn], num[maxn]; int main () { int T; scanf("%d", &T); while(T--){ int n; scanf("%d", &n); memset(dp, 0, sizeof(dp)); memset(step, 0, sizeof(step)); dp[0] = 1; for(int i = 1; i <= n; i++) scanf("%d", &num[i]); int Max = -1; for(int i = 1; i <= n; i++){ for(int j = 0; j < i; j++){ if(num[i] > num[j]){ if(step[j]+1 > step[i]){ step[i] = step[j] + 1; dp[i] = dp[j]; } else if(step[j] + 1 == step[i]) dp[i] += dp[j]; } } Max = max(Max, step[i]); } int flag = 0; int ok = 1; for(int i = 1; i <= n; i++){ if(step[i] == Max){ if(dp[i] > 1) ok = 0; else{ if(flag) ok = 0; flag = 1; } } } printf("%d\n", Max - ok ); } return 0; }
HDU5088Revenge of Nim II(高斯消元求自由变元个数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。