(2020牛客暑期多校训练营)[四] Investigating Legions

题目描述
在这里插入图片描述

样例
输入

1
10 20
101110101010101010100010010101010100101010010

输出

0 0 1 0 1 0 1 0 1 0

思路
将这道题转换一下,发现这是一道关于染色的题目。
但是由于给出的信息可能是错的,所以我们假设若条件的一半及以上都是正确,则这一条信息是正确的。反之,就是错误的。
我们先遍历每一个点,若被染过了,则跳过。若没有被染,搜索一下和他在一个军团的军队,并验证一下这一条信息是否正确。若正确,则将它染色。反之,跳过。每搜索完一个点,也就表示把这一个军团的人都染好了色,所以在下一次搜索前,把染的颜色更换一下即可。
代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,n,m,a[305];
    bool b[305][305];
    char c[90005];
    for(scanf("%d",&t);t--;)
    {
        int d=0,e=0;
        scanf("%d%d%s",&n,&m,c);
        for(int i=0;i<n;i++)//转化为二维数字的形式,利于后来的判断
        {
            for(int j=i+1;j<n;j++)
                b[i][j]=b[j][i]=c[d++]-'0';
            b[i][i]=1;
        }
        memset(a,-1,sizeof(a));
        for(int i=0;i<n;i++)
            if(a[i]==-1)//没被染过色
            {
                vector<int> g(0);
                for(int j=0;j<n;j++)if(b[i][j]&&a[j]==-1)g.push_back(j);//找到和它在一个军团的军队
                for(int j=0;j<n;j++)
                {
                    int sum=0;
                    for(int k=0;k<g.size();k++)if(b[g[k]][j] && a[j]==-1)sum++;
                    if(sum>=g.size()/2)a[j]=e;//若这条信息为真,染上色
                }
                e++;//更换染的颜色
            }
        for(int i=0;i<n;i++) printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}
版权声明:本文为bbbll123原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/bbbll123/article/details/107496056

智能推荐

ActiveMQ学习4-ActiveMQ的安全机制和集群模式

ActiveMQ的安全机制和集群模式 20 ActiveMQ安全机制 20.1 Web 控制台安全 20.2 消息服务器Broker安全 21 ActiveMQ主从集群 21.1 使用集群的重要性 20.2 主从集群的方式 20.2.1 shared filesystem Master-Slave方式主从集群 20.2.2 shared database Master-Slave方式主从集群 20...

说说 Python Django 应用的基础目录结构

通过以下 django-admin 指令创建应用之后,就会生成应用的基础目录结构。 比如,我们建立了一个叫 ‘first’ 的应用,它的目录结构是这样的: 目录或文件 说明 最外层的 first/ 这是新应用的根目录,所有与该应用相关的内容都放在这里。 manage.py 用于管理 Django 项目的命令行工具。 里面一层的 first/ 目录 是一个...

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

猜你喜欢

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...