数据结构 CANopen vector textview rss vue教程入门 java反射方法 erp项目描述 linux 获取系统时间 lora开发 maven插件 yml文件注释 xshell搭建ss python入门例子 python免费教程 python读取本地文件 python可视化编程 java入门 java继承关键字 java学习教程 java正则表达式详解 如何安装java环境 java怎么写接口 java线程中断 java接口的实例 java网页 linux系统教程 python队列 云管家 c4dr19 js文件上传 草图大师版本转换器 平面设计软件下载 edquota cdr裁剪工具怎么用 vue响应式原理 取小数点后两位函数 樱牛在哪 img转iso mac字体库
当前位置: 首页 > 学习教程  > 编程语言

gym102920 J. Switches(01矩阵求逆+01矩阵乘法+bitset优化)

2021/1/28 23:51:42 文章标签:

题意&#xff1a; 有n个灯和n个开关, 每个开关可能控制多个灯, 问对于每个灯i,是否存在一种开灯方案, 使得第i个灯亮,其他灯灭,输出方案. 如果无解输出-1. 数据范围&#xff1a;n<500 解法&#xff1a; 如果对于每个灯列一个n*n的01矩阵进行高斯消元求解, 总复杂度是O(n…

题意:

有n个灯和n个开关,
每个开关可能控制多个灯,
问对于每个灯i,是否存在一种开灯方案,
使得第i个灯亮,其他灯灭,输出方案.
如果无解输出-1.

数据范围:n<=500

解法:

如果对于每个灯列一个n*n的01矩阵进行高斯消元求解,
总复杂度是O(n^4),显然不行.

设矩阵A为系数矩阵,
X为开关操作矩阵(未知数矩阵),
B为结果矩阵(常数矩阵),
那么有A*X=B,
左右同时乘上A^(-1):X=A^(-1)*B.

求出A矩阵的逆矩阵A^(-1),
因为B矩阵是n*1,
所以A^(-1)*B是O(n^2),
枚举i,构造Bi,计算第i个灯的答案,
总复杂度是O(n^3),
但是n<=500,O(n^3)还是会T,需要打bitset优化.

code:

#include<bits/stdc++.h>
using namespace std;
const int N=505;
struct Mat{
    bitset<N>r[N],c[N];
    int n,m;
    void init(){
        for(int i=1;i<=n;i++){
            r[i].reset();
        }
        for(int i=1;i<=m;i++){
            c[i].reset();
        }
    }
    Mat operator*(const Mat &B){
        //矩阵A:n*m
        //矩阵B:m*p
        //矩阵ans:n*p
        int p=B.m;
        Mat ans;
        ans.n=n;
        ans.m=p;
        ans.init();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=p;j++){
                ans.r[i][j]=ans.c[j][i]=(((r[i]&B.c[j]).count())&1);
            }
        }
        return ans;
    }
};
Mat inv,x,ans;
bitset<N<<1>a[N];
int n;
int Gauss_rev(int n){
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){//找第i列非零的行换上来
            if(a[j][i]){
                swap(a[i],a[j]);
                break;
            }
        }
        if(!a[i][i])return 0;//无解
        for(int j=1;j<=n;j++){//其他行
            if(a[j][i]&&j!=i){
                a[j]^=a[i];
            }
        }
    }
    return 1;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int x;scanf("%d",&x);
            if(x)a[j][i]=1;
        }
        a[i][i+n]=1;
    }
    if(!Gauss_rev(n)){
        puts("-1");
    }else{
        inv.n=n;
        inv.m=n;
        inv.init();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                inv.r[i][j]=inv.c[j][i]=a[i][j+n];
            }
        }
        x.n=n;
        x.m=1;
        for(int i=1;i<=n;i++){
            x.init();
            for(int j=1;j<=n;j++){
                x.r[j][1]=x.c[1][j]=(i==j);
            }
            ans=inv*x;
            for(int j=1;j<=n;j++){
                if(ans.r[j][1]){
                    printf("%d ",j);
                }
            }
            puts("");
        }
    }
    return 0;
}


本文链接: http://www.dtmao.cc/news_show_650310.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?