Edu 12 --- Simple Subset -- 题解 (一个比较巧妙的思维算法题)

Simple Subset:

题解: 

 

思路解析:

        题目要求任意两个数的和为质数,那我们最坏情况就是任意选择一个数,此时子集为最大。

        如果子集中有两个奇数或者偶数,他们两个之和一定会被2整除,那么我们只能选择一奇一偶。

        如果多个奇数都为1的话,他们两两之和刚好为奇数,就是全部选择1也可以作为一种答案。

        那么我们全部选择1的话,我们还可以选择一个数恰好加上1就变为质数。

        这样就分析出了这道题的四种情况,处理质数时,可以预先通过欧拉筛处理。

代码实现:

        


import java.io.*;
import java.math.BigInteger;
import java.util.*;


public class Main {
    public static void main(String[] args) throws IOException {
        boolean[] isprime = new boolean[2000005];
        int[] prime = new int[150000];
        int tot = 0;
        for (int i = 2; i <= 2000000; i++) {
            if (!isprime[i]) prime[++tot] = i;
            for (int j = 1; j <= tot && prime[j] * i <= 2000000; j++) {
                isprime[prime[j] * i] = true;
                if (i % prime[j] == 0) break;
            }
        }
        int cnt = 0;
        int n = f.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = f.nextInt();
            if (a[i] == 1) cnt++;
        }
        int loop = 0;
        int ans = 1;
        if (cnt > 0) {loop = 2; ans = cnt;}
        int l = 0;
        int r = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (!isprime[a[i] + a[j]] && 2 > ans) {ans = 2;loop = 1; l = i; r = j; break;}
            }
            if (r != 0) break;
        }

        int id = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 1) continue;
            boolean st = isprime[a[i] + 1];
            if (!st){
                if (cnt + 1 > ans){
                    loop = 3;
                    ans = cnt + 1;
                    id = i;
                }
                break;
            }
        }
        w.println(ans);
        if (loop == 0){
            w.println(a[0]);
        } else if (loop == 1) {
           w.println(a[l] + " " + a[r]);

        } else if (loop == 2) {
            for (int i = 0; i < cnt; i++) {
                w.print(1 + " ");
            }
        } else {
            for (int i = 0; i < cnt; i++) {
                w.print(1 + " ");
            }
            w.print(a[id]);
        }
        w.flush();
        w.close();

    }


    static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));
    static Input f = new Input(System.in);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class Input {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Input(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            String str = null;
            try {
                str = reader.readLine();
            } catch (IOException e) {
                // TODO 自动生成的 catch 块
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public Double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/452218.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

JVM垃圾收集器-serial.parNew,parallelScavnge,serialOld,parallelOld,CMS,G1

垃圾收集器 分代模型 适用于新生代&#xff1a; serial parNew parallel Scaavenge 适用于老年代&#xff1a; CMS serial Old(msc) paraller Old 分区模型 适用于超大容量&#xff1a; G1 分代模型 serial /serial Old收集器 1.单线程收集器 2.收集时会暂停其他线程&…

从零搭建Vue项目

目录 环境准备 NodeJS安装 ​编辑 2. 选择安装目录 3. 验证NodeJS环境变量 4. 配置npm的全局安装路径 5. 切换npm的淘宝镜像 6. 安装Vue-cli Vue项目创建 1. 打开UI界面 2. 打开项目管理器 3. 创建项目 vue项目目录结构介绍 运行vue项目 Vue项目开发流程 Vue组…

k8s CKA upgrade - Kubeadm 版本升级实测

升级版本最好是逐步去升级&#xff0c;不要跨越多个大版本&#xff0c;可能会出错 大体流程&#xff1a; 1.先确定升级版本 2.升级kubeadm 3.驱逐节点 4.升级kubelet和kubectl 5.重启kubelet服务 6.恢复节点&#xff0c;使其上线 1.查看现版本&#xff1a;升级版本 kubectl ge…

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的夜间车辆检测系统(深度学习代码+UI界面+训练数据集)

摘要&#xff1a;开发夜间车辆检测系统对于自动驾驶技术具有关键作用。本篇博客详细介绍了如何运用深度学习构建一个夜间车辆检测系统&#xff0c;并提供了完整的实现代码。该系统基于强大的YOLOv8算法&#xff0c;并对比了YOLOv7、YOLOv6、YOLOv5&#xff0c;展示了不同模型间…

oracle临时表空间不释放

项目报错 nested exception is java.sql.SQLException: ORA-01652: unable to extend temp segment by 128 in tablespace TEMP 原因是临时表空间满了&#xff0c;临时表空间一直增长&#xff0c;未释放导致临时表空间使用率100%。 查询临时表空间使用率 --临时表空间利用率…

【MySQL 系列】MySQL 语句篇_DDL 语句

DDL&#xff08; Data Definition Language&#xff0c;数据定义语言&#xff09;用在定义或改变表的结构数据类型、表之间的链接和约束等初始化工作上。常用的语句关键字包括 CREATE、 DROP、 ALTER 等。 文章目录 1、MySQL 中的 DQL 语句2、MySQL 中库表的 DQL 语句详解2.1、…

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的常见手势识别系统(深度学习模型+UI界面代码+训练数据集)

摘要&#xff1a;开发手势识别系统对于增强人机交互和智能家居控制领域的体验非常关键。本博客详尽阐述了通过深度学习技术构建手势识别系统的过程&#xff0c;并附上了全套实施代码。系统采用了先进的YOLOv8算法&#xff0c;并通过与YOLOv7、YOLOv6、YOLOv5的性能对比&#xf…

代码学习记录17

随想录日记part17 t i m e &#xff1a; time&#xff1a; time&#xff1a; 2024.03.12 主要内容&#xff1a;今天的主要内容是二叉树的第六部分&#xff0c;主要涉及二叉搜索树的最小绝对差 &#xff1b;二叉搜索树中的众数&#xff1b;二叉树的最近公共祖先。 530.二叉搜索树…

关于c++的protected关键字

关于c的protected关键字 分类引言例子1&#xff09;错误的demo2&#xff09;改正的demo protected在c中的含义与作用 分类 c基础知识 引言 做了很业务&#xff0c;c基础知识却忘了很多&#xff0c;今天看了一个例子&#xff0c;唤醒了我关于c三大特性之一----封装&#xff0…

VulnHub - Lampiao

希望和各位大佬一起学习&#xff0c;如果文章内容有错请多多指正&#xff0c;谢谢&#xff01; 个人博客链接&#xff1a;CH4SER的个人BLOG – Welcome To Ch4sers Blog Lampiao 靶机下载地址&#xff1a;https://www.vulnhub.com/entry/lampiao-1,249/ 0x01 信息收集 Nm…

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的远距离停车位检测系统(深度学习代码+UI界面+训练数据集)

摘要&#xff1a;开发远距离停车位检测系统对于提高停车效率具有关键作用。本篇博客详细介绍了如何运用深度学习构建一个远距离停车位检测系统&#xff0c;并提供了完整的实现代码。该系统基于强大的YOLOv8算法&#xff0c;并对比了YOLOv7、YOLOv6、YOLOv5&#xff0c;展示了不…

读算法的陷阱:超级平台、算法垄断与场景欺骗笔记08_行为歧视

1. 常见的报价方式 1.1. 水滴定价&#xff08;Drip Pricing&#xff09; 1.1.1. 用一个较低的初始价格吸引消费者入局&#xff0c;之后再不断收取附加费用 1.2. 打折促销 1.2.1. 在一个远被高估的原价上制造折扣价格的魅力 1.2…

免费搭建导航网站教程带免费空间域名源码

使用免费空间和免费域名免费搭建一个导航网站 手把手视频教程 https://pan.xunlei.com/s/VNsoMehs7RCjz3IClV6h2vNMA1?pwdq596#

Docker安装步骤笔记

一、环境准备 VM网络配置 打开VMware软件 --编辑 --虚拟网络编辑器 二、VM创建虚拟机 三、安装rhel8.9操作系统 1、rhel8.9 镜像下载 第一步&#xff1a;进入redhat官网进行注册第二步&#xff1a;下载rhel8.9镜像文件 https://access.redhat.com/downloads/content/rhel …

南昌云宸网络发展有限公司-小分类客户可自选

南昌云辰网络发展有限公司是华东地区最大的互联网公司。 公司业务涉及互联网营销策划、移动互联网、物联网、广告传媒、微电影、***等&#xff0c;依托以互联网技术为核心的B2B企业贸易平台和O2O电子商务平台&#xff0c;提供为用户提供一站式网络营销策划和解决方案。 &#…

JMeter使用记录

文章目录 概述从0创建一个测试场景线程组配置元件CSV Data Set ConfigHTTP信息头管理器HTTP Cookie管理器HTTP请求默认值 逻辑控制器简单控制器IF控制器循环控制器while控制器 取样器HTTP取样 前置/后置处理器BeanShell处理器JSR223处理器 监听器查看结果树聚合报告汇总报告 概…

sqllab第二关通关笔记

知识点整理&#xff1a; 数值型注入判断手法 1/1 1/0 回显不同错误注入函数 extractvalue(xml_flag,xpath) xml_flag&#xff1a;文件表示符xpath&#xff1a;文件路径&#xff1b;不能识别‘~’ ‘#’ 等特殊字符&#xff1b;遇到就报错并打印xpath内容~(十六进制表示)&#…

Linux环境下,QtCreator运行不起来

文章目录 一、qtcreator运行不起来二、错误信息三、下载libxcb-cursor四、安装 一、qtcreator运行不起来 直接点击qtcreator运行不起来 然后再命令行界面下&#xff0c; 进入到qtcreator所在的目录&#xff1a; cd /opt/Qt/Tools/QtCreator/bin 运行程序&#xff1a;./qtcr…

模拟电子技术实验(二)

单选题 1. 本实验的实验目的中&#xff0c;输出电阻测量是第几个目的&#xff1f; A. 1个。 B. 2个。 C. 3个。 D. 4个。 答案&#xff1a;C 评语&#xff1a;10分 单选题 2.本实验电路有一个元件参数有问题&#xff0c;需要修改&#xff1f; A. …

一文看明白Transformer微调过程中嵌入向量的变化

TL&#xff1b;DR 微调在图像分类中显著影响嵌入向量。微调前的嵌入向量提供通用性表征&#xff0c;而微调后的嵌入向量捕获任务特定的特征。这种区别可能导致在异常检测和其他任务中的不同结果。微调前和微调后的嵌入向量各有其独特优势&#xff0c;应结合使用以实现图像分类…