P3164 [CQOI2014]和谐矩阵(高斯消元 + bitset)
2024-10-19 02:26:06
题意:构造一个$n*m$矩阵 使得每个元素和上下左右的xor值=0
题解:设第一行的每个元素值为未知数 可以依次得到每一行的值
然后把最后一行由题意条件 得到$m$个方程 高斯消元解一下 bitset写起来比较方便
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
const int MAXN = 45; int n, m;
bitset<MAXN> a[MAXN][MAXN];
bitset<MAXN> b[MAXN];
int ans[MAXN]; int dx[] = {-1, -1, -1, -2};
int dy[] = {-1, 0, 1, 0}; bool check(int x, int y) {
if(x >= 1 && x <= n && y >= 1 && y <= m) return true;
return false;
} void gauss() {
for(int i = 1, now = 1; i <= m && now <= m; now++) {
for(int j = i; j <= m; j++) {
if(b[j][now]) {
std::swap(b[j], b[i]);
break;
}
}
if(!b[i][now]) ans[now] = 1;
for(int j = i + 1; j <= m; j++) {
if(b[j][now]) {
b[j] ^= b[i];
}
}
i++;
} for(int i = m; i >= 1; i--) {
for(int j = i + 1; j <= m; j++) {
if(b[i][j]) {
ans[i] ^= ans[j];
}
}
}
} int main() {
scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) a[1][i][i] = 1;
for(int i = 2; i <= n; i++)
for(int j = 1; j <= m; j++) {
for(int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if(check(nx, ny)) {
a[i][j] ^= a[nx][ny];
}
}
} for(int i = 1; i <= m; i++) {
b[i] = a[n][i];
if(n - 1 >= 1) b[i] ^= a[n - 1][i];
if(i - 1 >= 1) b[i] ^= a[n][i - 1];
if(i + 1 <= m) b[i] ^= a[n][i + 1];
}
gauss(); for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int res = 0;
for(int t = 1; t <= m; t++) {
if(a[i][j][t]) res ^= ans[t];
}
if(j != m) printf("%d ", res);
else printf("%d\n", res);
}
}
return 0;
}
最新文章
- angularJS配合bootstrap动态加载弹出提示内容
- git clone
- oracle的数据库,随笔
- easyUI单元格合并自定义封装
- Linux按照CPU、内存、磁盘IO、网络性能监测
- .NET快速开发平台(DevExpress)免费下载
- android 照相或从相册获取图片并裁剪
- Sending Email from mailx Command in Linux Using Gmail’s SMTP
- div+css实现导航示意箭头
- UDF 编写自定函数
- git 用户手册
- C# LogHelper
- .Net多线程编程—Parallel LINQ、线程池
- 【机器学习实战】第7章 集成方法 ensemble method
- Linux显示以时间生升序显示文件
- 解决topjui中工具栏按钮删除刷新从属表
- C#实现数字字符串左补齐0的方法
- Wpf窗口中打开WinForm窗口
- docker1.13.1的安装与卸载及mysql5.5安装实例
- linux之软连接,硬连接篇
热门文章
- #1使用html+css+js制作网站教程 准备
- 一文彻底理解IO多路复用
- springboot 和 mongdb连接问题 Exception in thread ";main"; com.mongodb.MongoSecurityException:
- /etc/hosts文件
- 【Linux】ssh设置了密钥,但ssh登陆的时候还需要输入密码
- kubernetes机理之调度器以及控制器
- kubernets之pod的标签的使用
- 入门训练 - 蓝桥杯(Python实现)
- celery应用
- Java安全之ysoserial-JRMP模块分析(一)