基础线性代数——千足虫

这篇具有很好参考价值的文章主要介绍了基础线性代数——千足虫。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

[SDOI2010] 外星千足虫

题目来源

题目描述

公元 2333 2333 2333 2 2 2 3 3 3 日,在经历了 17 17 17 年零 3 3 3 个月的漫长旅行后,“格纳格鲁一号”载人火箭返回舱终于安全着陆。此枚火箭由美国国家航空航天局(NASA)研制发射,行经火星、金星、土卫六、木卫二、谷神星、“张衡星”等 23 23 23 颗太阳系星球,并最终在小行星“杰森星”探寻到了地外生命。宇航员在“杰森星”地表岩层下 45.70 45.70 45.70 米位置发现一批珍贵的活体生命样本,并将其带回检测。

在带回的活体样本中,最吸引人的当属这些来自外星的千足虫了。这些虫子身躯纤长,身体分为若干节。受到触碰时,会将身体卷曲成圆环形,间隔一段时间后才会复原活动。

有趣的还不止如此。研究人员发现,这些虫子的足并不像地球千足虫成对出现、总共偶数条——它们每节身体下方都有着不定数量的足,但足的总数一定是奇数条!

虽然从外观难以区分二者,但通过统计足的数目,科学家们就能根据奇偶性判断出千足虫所属的星球。

基础线性代数——千足虫,洛谷算法题合集,线性代数,算法

作为 J 国派去 NASA 的秘密间谍,你希望参加这次研究活动以掌握进一步的情报,而 NASA 选拔的研究人员都是最优秀的科学家。于是 NASA 局长 Charles Bolden 出了一道难题来检测你的实力:

现在你面前摆有 1 … N 1\ldots N 1N 编号的 N N N 只千足虫,你的任务是鉴定每只虫子所属的星球,但不允许亲自去数它们的足。

Charles 每次会在这 N N N 只千足虫中选定若干只放入“昆虫点足机”(the Insect Feet Counter, IFC)中,“点足机”会自动统计出其内所有昆虫足数之和。Charles 会将这个和数   m o d   \bmod mod 2 2 2 的结果反馈给你,同时告诉你一开始放入机器中的是哪几只虫子。

他的这种统计操作总共进行 M M M 次,而你应当尽早得出鉴定结果。

基础线性代数——千足虫,洛谷算法题合集,线性代数,算法

假如在第 K K K 次统计结束后,现有数据就足以确定每只虫子的身份,你就还应将这个 K K K 反馈给 Charles,此时若 K < M K<M K<M,则表明那后 M − K M-K MK 次统计并非必须的。

如果根据所有 M M M 次统计数据还是无法确定每只虫子身份,你也要跟 Charles 讲明:就目前数据会存在多个解。

输入格式

第一行是两个正整数 N , M N,M N,M

接下来 M M M 行,按顺序给出 Charles 这 M M M 次使用“点足机”的统计结果。每行包含一个 01 01 01 串和一个数字,用一个空格隔开。 01 01 01 串按位依次表示每只虫子是否被放入机器:如果第 i i i 个字符是 0 0 0 则代表编号为 i i i 的虫子未被放入, 1 1 1 则代表已被放入。后面跟的数字是统计的昆虫足数   m o d   \bmod mod 2 2 2 的结果。

由于 NASA 的实验机器精确无误,保证前后数据不会自相矛盾。即给定数据一定有解。

输出格式

在给定数据存在唯一解时有 N + 1 N+1 N+1 行,第一行输出一个不超过 M M M 的正整数 K K K,表明在第 K K K 次统计结束后就可以确定唯一解;接下来N行依次回答每只千足虫的身份,若是奇数条足则输出 ?y7M#(火星文),偶数条足输出 Earth

如果输入数据存在多解,输出 Cannot Determine

样例 #1

样例输入 #1

3 5
011 1
110 1
101 0
111 1
010 1

样例输出 #1

4
Earth
?y7M#
Earth

样例 #2

样例输入 #2

5 7
01100 1
11000 1
10100 0
11100 1
00011 1
00000 0
11111 0

样例输出 #2

Cannot Determine

提示

评分标准

对于每一个测试点,如果你的输出文件与答案文件完全相同,该测试点得满分。

否则,对于存在唯一解的测试点,如果你正确回答所有千足虫的身份,将得到 50 % 50\% 50% 的分数;

其他情况,该测试点得零分。

数据规模和约定

对于 20 % 20\% 20% 的数据,满足 N = M ≤ 20 N=M\leq 20 N=M20

对于 40 % 40\% 40% 的数据,满足 N = M ≤ 500 N=M\leq 500 N=M500

对于 70 % 70\% 70% 的数据,满足 N ≤ 500 N\leq500 N500 M ≤ 1 0 3 M\leq 10^3 M103

对于 100 % 100\% 100% 的数据,满足 1 ≤ N ≤ 1 0 3 1\leq N\leq 10^3 1N103 1 ≤ M ≤ 2 × 1 0 3 1\leq M\leq 2\times 10^3 1M2×103

设计思路

通过阅读本道题,我可以知道:
基础线性代数——千足虫,洛谷算法题合集,线性代数,算法
其中,模2意义下的线性方程组的求解要比一般情况简单很多。容易发现,这恰好对应位运算中的异或操作。于是上面这个线性方程组就转化为异或方程组。综上所述,本道题的本质就是高斯消元——异或版(我用的是化成行阶梯的形式),因此我们可以直接套模板(模板我已经放到后面了),细节:读入的时候得注意01串得用char一个一个读,要不然程序认为101是个数字文章来源地址https://www.toymoban.com/news/detail-849685.html

代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
//这里面有几行是多余的,可以不用考虑
const int N = 2e3+10;

int w[N][N];
int n,m;

int guass(){
    int r=1;
    for(int i=1;i<=n;i++){
        int max=r;// 前 r-1 已经完成操作
        for(int k=r;k<=m;k++){
            if(w[k][i]){
                max=k;
                break;
            }
        }
        if(!w[max][i])continue;
        if(max!=r)swap(w[max],w[i]);
        
        for(int k=1;k<=m;k++){
            if(k==r)continue;
            if(w[k][i]){
                for(int j=i;j<=n+1;j++){
                    w[k][j]^=w[r][j];
                }
            }
        }
        r++;
    }
    
    if(r<n+1){
        for(int i=r;i<=n;i++){
            if(w[i][n+1])return -1;
        }
    }
    
    return 0;
}

int main(){
    cin>>n>>m;
    
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            char a;
            cin>>a;
            w[i][j]=a-'0';
        }
        cin>>w[i][n+1];
        w[i][0]=i;
    }
    
    int t=guass();
    if(t==-1){
        puts("Cannot Determine");
    }else{
        int ans=w[1][0];
        for(int i=1;i<=n;i++){
            ans=max(ans,w[i][0]);
        }
        
        cout<<ans<<endl;
        
        for(int i=1;i<=n;i++){
            if(w[i][n+1]){//外星
                cout<<"?y7M#"<<endl;
            }else{
                cout<<"Earth"<<endl;
            }
        }
    }
    return 0;
}

模板1(异或版)

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 110;

int w[N][N];
int n;

int guass(){
    
    int r=1;//记录有多少行是非零的,就是目前已经完成 多少未知数的列清零了
    for(int i=1;i<=n;i++){
        
        int max=r;// 前 r-1 已经完成操作
        
        for(int k=r;k<=n;k++){
            if(w[k][i]){
                max=k;
                break;
            }
        }
        
        if(!w[max][i])continue; //如果最大的值都是 零。就说明当前这列没有1,也就是说没有这个 xi 未知数
        if(max!=r)swap(w[max],w[r]);
        for(int k=1;k<=n;k++){
            if(k==r)continue;
            if(w[k][i]){
                for(int j=i;j<=n+1;j++){
                    w[k][j]^=w[r][j];
                }
            }
        }
        
        r++;
    }
    if(r<n+1){
        
        for(int i=r;i<=n;i++){
            if(w[i][n+1])return 0;
        }
        
        return 1;
    }
    
    
    return 2;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)
            cin>>w[i][j];
            
    int t=guass();
    
    if(t==0)puts("No solution");
    else if(t==1)puts("Multiple sets of solutions");
    else{
        
        for(int i=1;i<=n;i++){
            printf("%d\n",w[i][n+1]);
        }
    }
    
    return 0;
}

模板2(线性版)

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 110;
const double eps=1e-8;

double w[N][N];
int n;

int guass(){//主元所在行不变,主元所在列消成0
    
    int t=1;//计数器
    for(int i=1;i<=n;i++){//先遍历每列每行(主元)=>对角线
        int r=i;//r是行
        for(int j=i;j<=n;j++){//找非0行,目的为了对角线上不为0
            if(abs(w[j][i])>eps){
                r=j;
                break;
            }
        }
        
        if(r!=i)swap(w[r],w[i]);//列换
        if(abs(w[i][i])<eps)continue;//无解
        
        for(int k=1;k<=n;k++){//对角化
            if(k==i)continue;//本行无需
            double t=w[k][i]/w[i][i];//目的是将主元所在的下面所有列消成0
            for(int j=i;j<=n+1;j++){
                w[k][j]-=t*w[i][j];
            }
        }
        t++;
    }
    
    if(t<n+1){
        for(int i=t;i<=n;i++){
            if(abs(w[i][n+1])>eps)return 0;
            return 1;
        }
        
    }
    
    //结束
    for(int i=1;i<=n;i++){
        
        w[i][n+1]/=w[i][i];
    }
    
    
    return 2;//存在唯一解
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n+1;j++){
            cin>>w[i][j];
        }
    }
    
    int t=guass();
    
    if(t==0)puts("No solution");
    else if(t==1)puts("Infinite group solutions");
    else{
        for(int i=1;i<=n;i++){
            printf("%.2lf\n",w[i][n+1]);
        }
    }
    return 0;
}

到了这里,关于基础线性代数——千足虫的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 线性代数基础【3】向量

    一、基本概念 ①向量 ②向量的模(长度) ③向量的单位化 ④向量的三则运算 ⑤向量的内积 二、向量运算的性质 (一)向量三则运算的性质 α + β = β + α α + (β + γ) = (α + β) + γ k (α + β) = kα + kβ (k + l) α = kα + lα (二)向量内积运算的性质 (α , β) = (β , α) = α^Tβ = β^Tα (α , α)

    2024年02月03日
    浏览(50)
  • 线性代数基础--向量

    目录 向量的概念 基本概念 抽象概念 向量的意义  几何意义 物理意义 欧式空间 特点和性质  行向量与列向量 行向量 列向量 两者的关系 向量的基本运算与范数 向量的基本运算 向量的加法 数乘运算(实数与向量相乘) 转置 向量的范数 向量的模与内积 向量的模 向量的内积

    2024年02月11日
    浏览(57)
  • 线性代数基础【2】矩阵

    一、基本概念 ①矩阵 像如下图示的为矩阵,记为A=(aij)m*n ②同型矩阵及矩阵相等 若A、B为如下两个矩阵 如果A和B的行数和列数相等,那么A和B为同型矩阵,且A和B的元素相等(即:aij=bij),则称A和B相等 ③伴随矩阵 设A为n阶矩阵(如上图所示),设A的行列式|A|,则A中aij的余子式为Mij,代数余

    2024年02月04日
    浏览(52)
  • 线性代数:基础解系

    线性代数是大学数学中非常重要的一门课程。它包括向量空间、线性映射、矩阵、行列式、特征值和特征向量等内容。其中,基础解系是线性代数中非常基础的一个概念,也是后续许多内容的基础。 1.1 齐次线性方程组 我们先回顾一下齐次线性方程组的概念。齐次线性方程组

    2024年02月08日
    浏览(43)
  • 【scipy 基础】--线性代数

    SciPy 的 linalg 模块是 SciPy 库中的一个子模块,它提供了许多用于线性代数运算的函数和工具,如矩阵求逆、特征值、行列式、线性方程组求解等。 相比于 NumPy的linalg模块 , SciPy的linalg模块 包含更多的高级功能,并且在处理一些特定的数值计算问题时,可能会表现出更好的性

    2024年02月05日
    浏览(38)
  • 线性代数基础--矩阵

     矩阵是由排列在矩形阵列中的数字或其他数学对象组成的表格结构。它由行和列组成,并且在数学和应用领域中广泛使用。 元素:矩阵中的每个数字称为元素。元素可以是实数、复数或其他数学对象。 维度:矩阵的维度表示矩阵的行数和列数。一个 m × n 的矩阵有 m 行和

    2024年02月11日
    浏览(46)
  • 机器学习线性代数基础

    本文是斯坦福大学CS 229机器学习课程的基础材料,原始文件下载 原文作者:Zico Kolter,修改:Chuong Do, Tengyu Ma 翻译:黄海广 备注:请关注github的更新,线性代数和概率论已经更新完毕。 1. 基础概念和符号 线性代数提供了一种紧凑地表示和操作线性方程组的方法。 例如,以

    2024年02月13日
    浏览(46)
  • 线性代数(一)——向量基础

    线性代数的核心是向量的加和乘两种运算的组合,本篇博客为线性代数的一个引子,主要从向量、线性组合和矩阵逐步引出线性代数的相关知识。 首先介绍的是向量相关,向量是基础。 已知列向量: υ = [ v 1 v 2 ] boldsymbol{upsilon}=left[begin{matrix} v_1 \\\\ v_2end{matrix} right] υ =

    2024年03月21日
    浏览(50)
  • 06-Numpy基础-线性代数

    线性代数(如矩阵乘法、矩阵分解、行列式以及其他方阵数学等)是任何数组库的重要组成部分。 NumPy提供了一个用于矩阵乘法的dot函数(既是一个数组方法也是numpy命名空间中的一个函数) x.dot(y)等价于np.dot(x, y) @符(类似Python 3.5)也可以用作中缀运算符,进行矩阵乘法:

    2024年02月11日
    浏览(40)
  • 【理解线性代数】(四)线性运算的推广与矩阵基础

    工业生产的发展趋势总是从单件生产到批量生产。科学技术研究也是一样,总是从简单计算到复合运算、批量运算。批量意味着生产能力、处理能力的提升。计算机从16位发展到64位,从单核发展到多核;计算机从CPU处理数据发展到GPU处理数据;大数据、人工智能领域的大模型

    2024年02月09日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包