本文主要是介绍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());}}
}
这篇关于Edu 12 --- Simple Subset -- 题解 （一个比较巧妙的思维算法题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
