[Usaco2009 Nov]lights(高斯消元)
2024-09-30 18:50:47
点灯游戏应该很多人都在小时候頽过吧
反正我直到现在也不会
很明显一个灯最多只需要点一次
然后高斯消元
解完肯定剩自由元(就是那些全是0的行)
然后这些都爆搜
由于剩下的自由元不会太多
所以时间复杂度$O(能过)$
以上
#include<cstdio> #include<algorithm> using std::swap; ; template<typename tp>void read(tp &kk){ tp ret=,f=;char ch=getchar(); ;ch=getchar();} +ch-';ch=getchar();} kk=ret*f; } int n,a[N][N]; void gauss() { ;l<=n;l++) { int g=l; while(g<=n&&(!a[g][l])) g++; if(g>n) continue; if(l!=g) ;i++) swap(a[l][i],a[g][i]); ;i<=n;i++) { if(a[i][l]&&i!=l) { ;j++) a[i][j]^=a[l][j]; } } } } int ans; void wtf(int l,int x) { if(x>ans) return; if(!l){ans=x;return;} ,x+a[l][n+]); else { ]) return; wtf(l-,x); ;i;i--) a[i][n+]^=a[i][l]; wtf(l-,x+); ;i;i--) a[i][n+]^=a[i][l]; } } int m,xi,yi; int main() { read(n),read(m); ;i<=n;i++) a[i][i]=a[i][n+]=; ;i<=m;i++) { read(xi),read(yi); a[xi][yi]^=,a[yi][xi]^=; } gauss(); ans=n; wtf(n,); printf("%d\n",ans); ; }
orz
最新文章
- PHP数学函数
- oracle更新语句merge和update
- 新浪微博客户端(2)-自定义导航控制器,统一NavigationItem
- UML 用例图,时序图,活动图的定义以及区别
- 数据库(class0507)
- HDU 1420 Prepared for New Acmer【中国剩余定理】
- 企业账号打包如何通过HTML页面打开
- Intellj IDEA光标为insert状态,无法删除内容
- 谈谈promise
- netty源码分析之揭开reactor线程的面纱(二)
- js兼容公用方法
- CSS| 框模型-margin
- 作业20171116 beta2及beta发布 成绩
- mysql中min和max查询优化
- HDU 5988.Coding Contest 最小费用最大流
- 使用jquery操作session
- vEthernet(默认交换机) 无法访问网络
- c++ 向main传递参赛
- HDU_5538_House Building
- vs2012安装qt5.5.1
热门文章
- 01_创建一个新的activity&;activity配置清单文件
- asp.net 中的事务
- php pdo操作数据库
- 升级Python后, yum不能用了
- 标准块CP功能实现
- php安装的扩展php -m可以看到,但是phpinfo()看不到,php-fpm关闭了重新打开还是不行?
- redis的多实例
- 暴力/DP Codeforces Beta Round #22 (Div. 2 Only) B. Bargaining Table
- 题解报告:poj 1195 Mobile phones(二维BIT裸题)
- matlab实现算术编解码 分类: 图像处理 2014-06-01 23:01 357人阅读 评论(0) 收藏