BZOJ3503:[CQOI2014]和谐矩阵(高斯消元,bitset)

BZOJ3503:[CQOI2014]和谐矩阵(高斯消元,bitset)

大家好,又见面了,我是你们的朋友全栈君。

Description

我们称一个由0和1组成的矩阵是和谐的,当且仅当每个元素都有偶数个相邻的1。一个元素相邻的元素包括它本
身,及他上下左右的4个元素(如果存在)。
给定矩阵的行数和列数,请计算并输出一个和谐的矩阵。注意:所有元素为0的矩阵是不允许的。

Input

输入一行,包含两个空格分隔的整数m和n,分别表示矩阵的行数和列数。

Output

输出包含m行,每行n个空格分隔整数(0或1),为所求矩阵。测试数据保证有解。

Sample Input

4 4

Sample Output

0 1 0 0
1 1 1 0
0 0 0 1
1 1 0 1

数据范围
1 <=m, n <=40

Solution

咋感觉我写了三个高斯消元的题三个板子都长得不一样
讲真这个题不知道比1770那个题低到哪里去了(其实差不多)
会做那个题一定会做这个【认真脸
很明显这个还是构造01矩阵然后解异或方程组
只不过这个构造出来的矩阵是n*m的,n^3显然很吃力
那么我们把1770代码里的异或用bitset来搞常数就小很多了
听说bitset随便虐1e9?

Code

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<bitset> 5 #define N (1600+100) 6 #define id(x,y) (x-1)*m+y 7 using namespace std; 8  9 bitset<N>f[N];10 int ans[N],n,m;11 int dx[7]={        0,1,-1,0,0,0},dy[6]={        0,0,0,1,-1,0};12 13 void Gauss(int n)14 {15     for (int i=1; i<=n; ++i)16     {17         int num=i;18         for (int j=i+1; j<=n; ++j)19             if (f[j][i]>f[num][i]) num=j;20         if (num!=i) swap(f[i],f[num]);21         22         for (int j=i+1; j<=n; ++j)23             if (f[j][i]) f[j]^=f[i];//这里用bitset来搞常数好像很小 24     }25     for (int i=n; i>=1; --i)26     {27         if (!f[i][i]) ans[i]=1;28         else29         {30             for (int j=i+1; j<=n; ++j)31                 f[i][n+1]=f[i][n+1]^(f[i][j]*ans[j]);32             ans[i]=f[i][n+1];33         }34     }35 }36 37 int main()38 {39     scanf("%d%d",&n,&m);40     for (int i=1; i<=n; ++i)41         for (int j=1; j<=m; ++j)42             for (int k=1; k<=5; ++k)43             {44                 int x=i+dx[k],y=j+dy[k];45                 if (x>0 && x<=n && y>0 && y<=m)46                     f[id(i,j)][id(x,y)]=1;47             }48     Gauss(n*m);49     for (int i=1; i<=n; ++i)50     {51         for (int j=1; j<=m-1; ++j)52             printf("%d ",ans[id(i,j)]);53         printf("%d\n",ans[id(i,m)]);54     }55 }

转载于:https://www.cnblogs.com/refun/p/8953107.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107559.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • todoMVC_mvc框架是什么

    todoMVC_mvc框架是什么依赖cssnpmitodomvc-commontodomvc-app-cssapp.component.tsimport{Component}from’@angular/core’;consttodos=[{id:1,title:’吃饭’,done:true},{id:1,title:’工作’,done:false},{id:1,title:’运动’,

  • 激光slam综述_SLAM是什么

    激光slam综述_SLAM是什么什么是slam技术 slam(SimultaneousLocalizationandMapping)叫即时定位与建图,它主要的作用是让机器人在未知的环境中,完成定位(Localization),建图(Mapping)和路径规划(Navigation)。激光slam简要介绍  主流的slam技术应用有两种,分别是激光slam(基于激光雷达lidar来建图导航)和视觉sla…

  • CANoe/CANalyzer诊断功能的深入理解以及CAPL诊断编程实现

    CANoe/CANalyzer诊断功能的深入理解以及CAPL诊断编程实现之前和大家分享了CANoe的基础使用(分析、仿真、测试、诊断),这篇文章将继续深入探讨如何使用CANoe/CANalyzer中的诊断功能。诊断用于在将ECU安装到系统之前或之后配置,维护,支持,控制和扩展ECU,例如,一辆车。诊断通常在请求-响应方案中执行:测试仪(客户端)向…

  • android 置灰不可点击,Android Studio 运行按钮灰色的完美解决方法「建议收藏」

    android 置灰不可点击,Android Studio 运行按钮灰色的完美解决方法「建议收藏」AndroidStudio运行按钮灰色的完美解决方法今天新建项目的时候突然发现编译后运行按钮为灰色。解决方案:第一步:点击图中的AddConfiguration,出来如下界面第二步:点+号,并选择AndroidApp选项出来下图所示界面第三步:在Module中下拉框中选择app如果在Module下拉框没有app这个选项点击搜索框,输入sync,从搜索结果中选择如下项:点击运行…

  • JS日期格式化转换方法

    JS日期格式化转换方法1.将日期转换为指定的格式:比如转换成年月日时分秒这种格式:yyyy-MM-ddhh:mm:ss或者yyyy-MM-dd。当然是网上的方法,只是总结下。可以为Date原型添加如下的方法:Date.prototype.format=function(fmt){varo={“M+”:this.getMonth()+1,…

  • 递归算法之阶乘算法

    递归算法之阶乘算法递归算法是一种比较难理解的算法,本人是一位学生,饱受编程之苦,为了给广大学编程的童鞋提供方便,这里总结了一些教科书中常见的递归算法案例。这是第一篇,简单的用递归实现的阶乘算法。#includeusingnamespacestd;intFactorial(intn){ intsum=0;//定义一个累乘的sum量 if(n==0)return

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号