20210303

基础测试 芯片测试

问题描述

有n(2≤n≤20)块芯片,有好有坏,已知好芯片比坏芯片多。
  每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时,能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时,会随机给出好或是坏的测试结果(即此结果与被测试芯片实际的好坏无关)。
  给出所有芯片的测试结果,问哪些芯片是好芯片。

输入格式

输入数据第一行为一个整数n,表示芯片个数。
  第二行到第n+1行为n*n的一张表,每行n个数据。表中的每个数据为0或1,在这n行中的第i行第j列(1≤i, j≤n)的数据表示用第i块芯片测试第j块芯片时得到的测试结果,1表示好,0表示坏,i=j时一律为1(并不表示该芯片对本身的测试结果。芯片不能对本身进行测试)。

输出格式

按从小到大的顺序输出所有好芯片的编号

样例输入

3
1 0 1
0 1 0
1 0 1

样例输出

1 3

解题思路

关键信息 “已知好芯片比坏芯片多”
从这一点出发,讨论总的芯片数量 n

若 n 是偶数,比如 n=8,则好芯片至少是 5 个,对于其中任意一个好芯片而言,它被检测成 1 的次数至少是 4 (也就是 n/2)
若 n 是奇数,比如 n=7,则好芯片至少是 4 个,对于其中任意一个好芯片而言,它被检测成 1 的次数至少是 3 (也就是 n/2)
所以,一个芯片被检测成1 的次数 >= n/2,就是判断是不是好芯片的标准

import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int [][]arr = new int[n][n];
        int b[] = new int[n];
        for (int i =0;i<n;i++){
            for (int j = 0;j<n;j++){
                arr[i][j] = scanner.nextInt();
                if (arr[i][j] == 0){
                    b[j] = b[j]+1;
                }
            }
        }
        for(int i=0;i<n;i++) {
            if (b[i] <= n / 2) {
                System.out.print(i+1+" ");
            }
        }
				scanner.close();
    }
}

视频学习 单词拼接

蓝桥杯培训内部讲解-单词拼接

学习心得

  • 有向图G为欧拉回路:
    当且仅当G的基图连通,且所有顶点的入度等于出度。
  • 有向图G为欧拉路:
    当且仅当G的基图连通,且只存在一个顶点u的入度比出度大1、
    只存在一个顶点v的入度比出度小1,其它所有顶点的入度等于出度。
  • 单词的首字母应该看做是出度,尾字母看做是入度

对应练习 单词接龙

Description
问题描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beast和astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at 和 atide 间不能相连。

输入格式

输入的第一行为一个单独的整数n (n<=20)表示单词数,以下n 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出格式

只需输出以此字母开头的最长的“龙”的长度

样例输入
  5
  at
  touch
  cheat
  choose
  tact
  a

Input

输入描述:
  连成的“龙”为atoucheatactactouchoose
输入样例:
23

Output
输出描述:

输出样例:

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static int n;
	public static int maxLength;
	public static String maxStr = "";
	public static int[] count;
	public static int first = 0;
	public static void main(String[] args)
	{
		Scanner read=new Scanner(System.in);
		n = read.nextInt();
		count = new int[n];
		String []ss = new String[n];
		for(int i=0;i<n;i++)
		{
			ss[i] = read.next();
		}
		maxStr = read.next();
		read.close();
		dfs(maxStr,ss);
		System.out.println(maxLength);
	}
	public static void dfs(String str,String[] ss) 
	{
		if(str.length()>maxLength)
		{
			maxStr = str;
			maxLength = str.length();
		}
		
		for(int i=0;i<n;i++)
		{
			if(count[i]<2)
			{
				String str2 = ss[i];
				int num = judgment(str,str2);
				if(num!=0)
				{
					count[i] = count[i]+1;
					String s = str+ss[i].substring(num);
					dfs(s,ss);
					count[i] = count[i]-1;
				}
			}
		}
	}
	public static int judgment(String str1,String str2)
	{
		int len = 0;
		if(str1.length()==1)
		{
			for(int i=0;i<Math.min(str1.length(),str2.length());i++)
			{
				String str11 = str1.substring(str1.length()-i-1,str1.length());
				String str22 = str2.substring(0,i+1);
				if(str11.equals(str22))
				{
					len = i+1;
				}
			}
		}
		else
		{
			for(int i=0;i<Math.min(str1.length()-1,str2.length()-1);i++)
			{
				String str11 = str1.substring(str1.length()-i-1,str1.length());
				String str22 = str2.substring(0,i+1);
				if(str11.equals(str22))
				{
					len = i+1;
					break;
				}
			}
		}
		return len;
	}
	
}

热门文章

暂无图片
编程学习 ·

C++核心准则ES.40:避免复杂的表达式

ES.40: Avoid complicated expressionsES.40:避免复杂的表达式Reason(原因)Complicated expressions are error-prone.复杂的表达式容易引发错误。Example(示例)// bad: assignment hidden in subexpression while ((c = getc()) != -1)// bad: two non-local variables as…
暂无图片
编程学习 ·

毛毛爸爸手记-2

http://blog.sina.com.cn/s/blog_4bf99d0601000825.html今天,毛爸从天鹅和鸭子的故事说起。从前......一只美丽的天鹅有一天落在地上时,看见了一只健壮的鸭子,她立刻被这只帅气的鸭子所打动,她惊诧于鸭子不同于她同类的模样,不同于她同类气质,是那么的有型,那么的另类。…
暂无图片
编程学习 ·

element dom 事件注册 on off once

/* istanbul ignore next */ // 匿名函数自执行,兼容IE-attachEvent,chrome-addEventListener export const on = (function() {if (!isServer && document.addEventListener) {return function(element, event, handler) {if (element && event && h…
暂无图片
编程学习 ·

Spring Boot / Spirng Cloud 引入Rabbit MQ

注意: spring cloud版本:Greenwich.RELEASE spring boot 版本: 2.1.5.RELEASE 1.导包,在pom.xml中导入<dependency><groupId>org.springframework.amqp</groupId><artifactId>spring-rabbit</artifactId></dependency>2.加入配置文件 …
暂无图片
编程学习 ·

阿里云香港云服务器ECS适合什么场景?

香港云服务器有什么好处?适合什么场景呢?许多对于不想备案的用户,那么香港节点最为合适不过了。因此,笔者整理阿里云香港服务器优惠购买流程以及列出香港服务器的好处!阿里云香港服务器:目前阿里云优惠活动中,限时云服务器爆款2折有推出香港节点突发性t5实例 固定配置1核…
暂无图片
编程学习 ·

第四天实训:GUI学生信息管理系统

实训目的:主要涉及程序控制结构、面向对象编程、图形用户界面、Java数据库应用、MySQL数据库这几个方面的内容。通过本项目的开发,了解系统开发的一般流程,初步了解MVC模式与单元测试,巩固所学的Java理论知识,提高Java数据库应用编程的基本技能。 项目说明:本系统包括登录…
暂无图片
编程学习 ·

iOS开发之多线程(2)—— Thread

目录版本简介方法属性示例 版本 Xcode 11.5 Swift 5.2.2 简介 一个Thread即为一个线程. 方法属性 OC中的属性方法(Swift方法名类似): #pragma mark - 属性 // 可以使用返回的字典来保存线程的特定数据. (这只是一个普通的字典, 用来保存所有开发者感兴趣的数据.) @property (r…
暂无图片
编程学习 ·

D_SparkSQL

C_SparkSQL 一. 概述 1. 什么是SparkSQL Spark SQL是Spark用来处理结构化数据的一个模块,它提供了2个编程抽象:DataFrame DataSet并且作为分布式SQL查询引擎的作用。 众所周知的Hive,它是将Hive SQL转换成MapReduce然后提交到集群上执行,大大简化了编写MapReduc的程序的复杂…
暂无图片
编程学习 ·

顺序结构

顺序结构 1,if选择结构public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.println("请输入你的成绩:");int score = scanner.nextInt();if(score>=60 && score<70){System.out.println("及格&quo…
暂无图片
编程学习 ·

vc++ GDI+实现以鼠标为中心缩放图片(并且可以拖动)

按以下步骤操作,即可实现。1. 首先创建一个基于对话框的MFC程序,然后把下面两个文件分别保存为.h文件和 .cpp文件//InitGdiplus.h #pragma once#include <GdiPlus.h> using namespace Gdiplus;class CInitGdiplus { public:CInitGdiplus(void);~CInitGdiplus(void);pri…
暂无图片
编程学习 ·

疫情下的舆情预测系统工作报告part.4

项目地址:https://github.com/Lee991211/Innovation_training.git数据清洗 当获取了大量的微博数据,需要对冗余数据进行清洗,使数据满足一定格式,以达到模型训练的要求@杨涛同学。当然这个任务相对于爬取就比较简单了,出于保存数据备份的想法,我的清洗脚本分为两步。 was…
暂无图片
编程学习 ·

Kafka 总结

消息队列的使用场景 从三大特点来进行描述:解耦、异步、削峰。 Kafka 高可用 Kafka 是由多个 Broker 节点组成,当创建一个 topic时,这个 topic 可以被划分为多个 partition,每个 partition 可以存放在不同的 broker 节点上,每个 partition 存放着一个 topic 的部分数据。-…
暂无图片
编程学习 ·

【解惑】到底是“时间片“?还是“分时轮询“?

1、任务调度任务调度对于电子类或者自动化类专业小伙伴最早接触一般都是在接触RTOS后了,然而对于计算机相关专业的小伙伴应该在学《计算机操作系统》老师对这一块讲解的非常清楚了,包括一些性能指标的定义与计算等等,不过作者这里仅仅只针对RTOS进行讲解,大家感兴趣可以找一…
暂无图片
编程学习 ·

XGBoost学习总结

XGBoost学习总结极端梯度提升算法XGBoost是2014年提出的基于CART回归树的一种boosting集成算法,是对梯度提升决策树(GBDT)算法的一种改进.它的目标是建立t棵回归树使得树群对样本的预测值尽可能接近样本的真实值,并且具有一定的泛化能力.本文是对XGBoost学习的总结与思考,通过总…
暂无图片
编程学习 ·

【原创】软件开发之设计模式分类

按照设计模式的目的进行划分:类别内容举例创建型模式通过抽象类所定义的接口,封装了系统中对象如何创建、组合等信息其代表有Singleton模式等结构型模式主要用于如何组合自己有的类和对象以获得更大的结构其代表有Adapter模式等行为型模式主要用于对象之间的职责及其提供服务…
暂无图片
编程学习 ·

线性代数知识课笔记1

笔记内容摘自 猴博士爱讲课@B站 https://www.bilibili.com/video/BV1hs411e7X8?p=4行列式 行列式的计算 行列式分为2阶、3阶、4阶……n阶等,其中2阶的计算方法为: ∣1326∣ \begin{vmatrix}1&3\\2&6\end{vmatrix} ∣∣∣∣​12​36​∣∣∣∣​ 计算方法为对角线相乘…