酒业网站模板下载,教师兼职做网站,江苏省建设厅网站首页,做销售用的免费发布信息网站X质数
问题描述
对于一个含有 M 个数位的正整数 N #xff0c;任意选中其中 K 个不同的数位#xff08;0≤KM#xff09;#xff0c;将这些选中的数位删除之后#xff0c;余下的数位按照原来的顺序组成了一个新的数字 P 。如果至少存在一个 P 是质数#xff0c;我们…X质数
问题描述
对于一个含有 M 个数位的正整数 N 任意选中其中 K 个不同的数位0≤KM将这些选中的数位删除之后余下的数位按照原来的顺序组成了一个新的数字 P 。如果至少存在一个 P 是质数我们就称 N 是一个 X 质数。例如对于整数 7869我们可以删去 7 和 6 得到一个新的数字 89 由于 89 是一个质数因此 78697869 是一个 X 质数。又如对于整数 77可以删去一个 7 后变为质数 7 因此 77 也是一个 X 质数。
请问 1 含至 1000000 含中一共有多少个不同的 X 质数。
答案提交
这是一道结果填空的题你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。
分析:递归加回溯生成不同的结果,再判断质数
import java.util.*;public class Main {public static void main(String[] args) {int cnt 0;for (int i 1; i 1000000; i) {int[] arr new int[7]; // 最多6位数字int len 0;int x i;while (x 0) {arr[len] x % 10;x / 10;}ListInteger results new ArrayList();generateNumbers(arr, 0, -1, results);boolean isXPrimeNumberExists false;for (int num : results) {if (num 2 isPrime(num)) {isXPrimeNumberExists true;break;}}if (isXPrimeNumberExists) {cnt;}}System.out.println(cnt);}public static void generateNumbers(int[] arr, int index, int currentNum, ListInteger results) {if (index arr.length) {if (currentNum ! -1)results.add(currentNum);return;}// 选择删除当前位置的数字不累计generateNumbers(arr, index 1, currentNum, results);// 选择保留当前位置的数字if (currentNum -1) {generateNumbers(arr, index 1, arr[index], results);} else {generateNumbers(arr, index 1, currentNum * 10 arr[index], results);}}public static boolean isPrime(int n) {if (n 2) return false;for (int i 2; i Math.sqrt(n); i) {if (n % i 0) return false;}return true;}
}
残缺的数字
问题描述
七段码显示器是一种常见的显示数字的电子元件它由七个发光管组成: 图依次展示了数字 0∼9 用七段码来显示的状态其中灯管为黄色表示点亮灰色表示熄灭。根据灯管的亮暗状态我们可以用一个状态码(状态码是一个 7 位的二进制数字)来表示一个七段码令灯管点亮时状态为 1灯管熄灭时状态为 0按照灯管 ABCDEFG 的顺序标识一个七段码则数字 0∼9 的状态码为:
数字状态码数字状态码01111110510110111011000061011111211011017111000031111001811111114011001191111011
小蓝有一个喜爱的数字长度为 18位每一位用一个七段码显示器来展示 (每位只能是 0∼9可以包含前导零)由于灯管故障一些本该点亮的灯管处于了熄灭状态。例如对于一个长度为 2 的数字来说当两个七段码对应的状态码分别为: 1011111(高位)、1110011(低位)时原本的数字可能会是: 68、69、88、89有 44 种可能的值。
18个七段码显示器对应的状态码分别为:
0000011
1001011
0000001
0100001
0101011
0110110
1111111
0010110
0101001
0010110
1011100
0100110
1010000
0010011
0001111
0101101
0110101
1101010其中每行表示一个七段码对应的的状态码(按照数字的高位到低位给出)。请你判断下小蓝喜爱的数字有多少种可能的值。
答案提交
这是一道结果填空的题你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。
分析:就是每个code判断其有无可能通过将0变成1成为其它状态码,code为输入状态码,digitCode为预定义的状态码,如果相同位时code的数位为1而digitCode为0就不可能.
import java.util.*;public class Main {// 预定义0-9的状态码static String[] digitCodes {1111110, // 00110000, // 11101101, // 21111001, // 30110011, // 41011011, // 51011111, // 61110000, // 71111111, // 81111011 // 9};public static void main(String[] args) {String[] inputCodes {0000011,1001011,0000001,0100001,0101011,0110110,1111111,0010110,0101001,0010110,1011100,0100110,1010000,0010011,0001111,0101101,0110101,1101010};long totalCount 1;for (String code : inputCodes) {int count 0;for (int digit 0; digit 9; digit) {if (isPossible(code, digitCodes[digit])) {count;}}totalCount * count0?1:count;}System.out.println(totalCount);}// 判断给定的状态码是否可能是某个数字的状态码考虑故障状态码中的0可能代表灯管熄灭private static boolean isPossible(String code, String digitCode) {// 只要对应位置的码不冲突即可即如果digitCode为1但code为0说明灯本应亮但灯没有亮不能匹配// 如果code为1digitCode必须为1否则不可能for (int i 0; i 7; i) {if (code.charAt(i) 1 digitCode.charAt(i) ! 1) {return false;}}return true;}
}
整数变换
问题描述
小蓝有一个整数 nn。每分钟小蓝的数都会发生变化变为上一分钟的数减去上一分钟的数的各个数位和。
例如如果小蓝开始时的数为 23则下一分钟变为 23−(23)18再下一分钟变为 18−(18)9再下一分钟变为 9−90共经过了 3 分钟变为 0。
给定一个正整数请问这个数多少分钟后变为 0。
输入格式
输入一行包含一个整数 n。
输出格式
输出一个整数表示答案。
分析:送分题
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);int n scan.nextInt();int cnt 0;while(n0){n - Sum(n);cnt;}System.out.println(cnt);scan.close();}public static int Sum(int n){int sum 0;while(n0){sum n%10;n/10;}return sum;}
}
最大算式
问题描述
给定 n 个非负整数 Ai 你可以在不改变这些数顺序的前提下任意在他们之间插入 ,∗,(,) 四种符号
请问在得到的算式合法的前提下算式的结果最大可以是多少?
由于结果很大你只需要输出答案对 1097 取模的结果即可。
输入描述
输入的第一行包含一个整数 n 。
第二行包含 n 个整数分别表示 A1,A2,⋯,An相邻两个整数之间使用一个空格分隔。
输出描述
输出一行包含一个整数表示答案。
分析:这道题真搞,官网上一堆有缺陷的答案,没有考虑各种边界情况,但就是能过样例.
官网的测试也有问题.这个问题其实就是处理1,把1和其它数合并起来.边界情况就是第一个数是1和最后一个数是1的情况,另外一般情况就是将1加到左右边最小的非0数上.但这里有一个最大的问题就是当前一个非0数是2时要把1加到2上面.官网上好多错的答案就是只考虑了21问题.这个真难想到.eg 1 1 1 1 1 1时,如果不把1加到2上面算出来是8,但最大值是9 import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static int mod 1000000007;public static void main(String[] args) {Scanner scan new Scanner(System.in);int n scan.nextInt();long[] arr new long[n1];for(int i 0; i n; i){arr[i] scan.nextLong();}for(int i 0; i n; i){if(arr[i] ! 1) continue;//处理1int temp i;if(i0){//第一个数是1temp;while(arr[temp]0tempn){temp;}arr[temp];//找到右边第一个非0元素将1加在他上面}else{//一般1情况int l temp-1, r temp1;while(l0 arr[l]0){l--;}while(rn arr[r]0){r;}if(arr[l]arr[r] || arr[r] 0 ||arr[l]2) arr[l];else arr[r];}arr[i] 0;//现在的1就置为0}long ans 1;for (int i 0; i n; i) {if (arr[i] ! 0) ans ans * arr[i] % mod;}System.out.println(ans);scan.close();}
} 躲炮弹
问题描述
小蓝正在玩一个躲炮弹的游戏。游戏中有一个人物和一个炮塔它们的初始距离为 n。
炮塔可能选择在区间 [L,R]上的任意一个整数 x然后发射的炮弹会飞向小蓝操控的人物。但炮弹只会在飞出 x 的倍数的距离(x,2x,3x,…)时落地然后弹回到空中。如果小蓝操控的人物恰好站在了炮弹落地的位置那么游戏就会结束。
小蓝只能在炮弹发射前移动他的人物每移动一步可以使得人物和炮塔的距离增加 1 或者减少 1。他想知道最少要移动多少步才能保证自己的人物一定能躲过炮弹。
输入格式
输入一行包含三个整数 n,L,R相邻的整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示小蓝操纵的人物最少需要移动的步数。
分析:找到一个离n最近的数且他的因数不在(l,r)区间内(质因数)或者找到一个质数
思路是官网上的一个题解:0躲炮弹 - 蓝桥云课
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int l in.nextInt();int r in.nextInt();if (n l) {System.out.println(0);return;}if (n l n r) {// 需要先走出区间int minSteps Math.min(n - l 1, r - n 1 2000); // 初始值设为可能的最大值// 检查向右走出区间后是否能快速找到质数/安全数for (int i 0; i 2000; i) {int candidate r 1 i;if (isSafe(candidate, l, r)) {minSteps Math.min(minSteps, r - n 1 i);break;}}System.out.println(minSteps);} else {// n r 的情况for (int i 0; i 2000; i) {if (isSafe(n - i, l, r) || isSafe(n i, l, r)) {System.out.println(i);return;}}}in.close();}// 检查一个数是否安全不是[l,r]区间的倍数且其所有因数都不在[l,r]区间private static boolean isSafe(int num, int l, int r) {if (num 2) return false; // 0和1不是质数if (num l num r) return false;// 快速检查小因数for (int i 2; i * i num i r; i) {if (num % i 0) {if (i l i r) return false;int other num / i;if (other l other r) return false;}}return true;}
} 等腰三角形
问题描述
给定一个包含 n 个数的序列 Ai 每次操作可以选择其中任意一个数将其 1 或 −1 。
我们要让这个序列满足能够从中任选三个数这三个数对应长度的三条边总能组成一个等腰三角形。问最少需要多少次操作才能让序列满足条件。
输入描述
输入的第一行包含一个整数 n 。
第二行包含 n 个整数分别表示 A1,A2,⋯,An相邻两个整数之间使用一个空格分隔。
输出描述
输出一行包含一个整数表示最少的操作次数。
分析:不会,好像是连续的三元素逐个检查,不懂,贴个正确代码算了
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();long[] a new long[n]; // 0-based数组long[] b new long[n 1]; // 前缀和数组大小为n1for (int i 0; i n; i) {a[i] sc.nextLong();}Arrays.sort(a);for (int i 0; i n; i) {b[i 1] b[i] a[i];}// 不使用接口直接用匿名类// 计算区间[l, r]的变换成本// l, r为0-based// 传入x返回总操作// 方式直接定义一个函数class Checker {long calculate(int l, int r, long x) {int mid lowerBound(a, l, r 1, x);long res 0;res (long)(mid - l) * x - (b[mid] - b[l]);res (b[r 1] - b[mid]) - (long)(r - mid 1) * x;return res;}}Checker checkObj new Checker();long ans Long.MAX_VALUE;// 中位数方案long midVal a[n / 2];ans Math.min(ans, checkObj.calculate(0, n - 1, midVal));// 枚举切分点for (int i 0; i n - 1; i) {long x a[i / 2];long y a[i (n - i) / 2];if (2 * x y || i 0) {ans Math.min(ans, checkObj.calculate(0, i, x) checkObj.calculate(i 1, n - 1, y));} else {long lVal x, rVal y;while (lVal rVal) {long midl lVal (rVal - lVal) / 3;long midr rVal - (rVal - lVal) / 3;long cl checkObj.calculate(0, i, midl) checkObj.calculate(i 1, n - 1, Math.min(2 * midl - 1, y));long cr checkObj.calculate(0, i, midr) checkObj.calculate(i 1, n - 1, Math.min(2 * midr - 1, y));if (cl cr) {rVal midr - 1;} else {lVal midl 1;}}long cl checkObj.calculate(0, i, lVal) checkObj.calculate(i 1, n - 1, Math.min(2 * lVal - 1, y));long cr checkObj.calculate(0, i, rVal) checkObj.calculate(i 1, n - 1, Math.min(2 * rVal - 1, y));ans Math.min(ans, Math.min(cl, cr));}}System.out.println(ans);}static int lowerBound(long[] arr, int from, int to, long key) {int low from;int high to; // to是开区间while (low high) {int mid (low high) 1;if (arr[mid] key) {low mid 1;} else {high mid;}}return low;}
} 连续数组
问题描述
小蓝对连续数组很感兴趣对于一个长度为 NN 的连续数组 numsnums中的元素取值范围为 1∼N且 nums 中不存在重复元素每两个相邻的数组元素 nums[i]、nums[i1]之间都存在关系(1≤i≤N−1)且只可能是以下两种关系中的一种:
连续此时 nums[i1]等于 nums[i]1;不连续此时 nums[i1]不等于 nums[i]1。
现在给出一个长度为 N 的数组中任意相邻的数组元素之间的关系请问共有多少种满足条件的连续数组?
输入格式
输入的第一行包含一个整数 N 表示数组长度。
第二行包含 N−1 个整数相邻的整数之间使用一个空格分隔表示连续数组中相邻元素之间的关系取值只能是 0 (表示不连续关系)或 1(表示连续关系)。其中第 i (1≤i≤N−1)个整数表示 nums[i]和 nums[i1] 之间的关系。
输出格式
输出一行包含一个整数表示答案。 分析:题解里看到暴力回溯加剪枝的方法,发现可以通过,因为样例N很小,贴出该代码,是立志成为算法er的题解,加了点注释更直观
import java.util.*;
import java.io.*;
import java.math.*;public class Main {static int INF Integer.MAX_VALUE;static int mod 1000000007 ;static int N 30,M 2*N;static int[] op new int[N],select new int[N],vis new int[N];static int n,m;static long ans;static void dfs(int u) {if(un) {// for(int i1;in;i) System.out.print(select[i] );// System.out.println();ans ;return;}if(op[u-1]1) {//检查前一个位置的关系是否是连续int val select[u-1]1;// 计算当前必须选择的数字(前一个数字1)if(vis[val]0 valn) {//检查这个数字是否可用且在范围内select[u] val;// 选择这个数字vis[val] 1;//标记为已使用dfs(u1);//递归处理下一个位置vis[val] 0;// 回溯取消选择(恢复现场)}}else {for(int i1;in;i) {//处理不连续的情况尝试所有可能的数字if(vis[i]1 || select[u-1]1i) continue;//跳过已使用的数字和前一个数字1select[u] i;vis[i] 1;dfs(u1);vis[i] 0;//选择数字、标记、递归、回溯的步骤与前面类似}}}public static void main(String[] args) throws IOException {n sc.nextInt();for(int i1;in-1;i) {op[i] sc.nextInt();}for(int i1;in;i) {//尝试每个数字作为排列的第一个元素Arrays.fill(vis, 0);//重置标记数组vis[i] 1;//标记当前选择的第一个数字select[1] i;//设置排列的第一个数字dfs(2);//从第二个位置开始递归构建排列vis[i] 0;//回溯取消第一个数字的选择}System.out.println(ans);}static Scanner sc new Scanner(System.in);}
问题描述
我们定义质数排序为将一个序列中的所有下标为质数的位置进行升序排序 其它位置上的数不变。
例如对 8,7,6,5,4,3,2,1 进行质数排序会得到 8,2,4,5,6,3,7,1。 给定 n 求 1∼n 的每个排列进行质数排序后的逆序对的数量的和。 由于结果很大你只需要输出答案对 998244353 取模的结果即可。
输入格式
输入一行包含一个整数 n。
输出格式
输出一行包含一个整数表示答案。
分析:感觉跟数学有点关系,不会,贴代码
import java.io.*;
import java.util.*;public class Main {static final int MOD 998244353;static final int MAX 1000001;public static void main(String[] args) throws IOException {BufferedReader br new BufferedReader(new InputStreamReader(System.in));int n Integer.parseInt(br.readLine());// 标记非质数位置int[] pr new int[MAX];pr[1] 1;for (int i 2; i n; i) {if (pr[i] 0) {for (int j i i; j n; j i) {pr[j] 1;}}}// 统计质数(s)和非质数(t)数量long s 0, t 0;for (int i 1; i n; i) {if (pr[i] 0) s;else t;}// 计算w和glong w 1, g 1;for (int i 1; i n; i) {if (i ! s 1) w w * i % MOD;if (i ! 2) g g * i % MOD;}// 计算非质数位置间的逆序对long ans t * (t - 1) / 2 % MOD * g % MOD;// 计算质数与非质数位置间的逆序对long A s, B 0; for (int i n; i 1; i--) {if (pr[i] 0) {A--;B;} else {long temp (A * (A 1) / 2 B * (B 1) / 2) % MOD;ans (ans temp * w) % MOD;}}System.out.println(ans);}
} 单词分类
问题描述
在遥远的 LQ 国只存在三种字符l、q 和 b (ASCII 码分别为 108、113、98)所有的单词都由这三种字符组合而来。小蓝为了更加快速的记忆单词决定将词典上所有的单词按照单词前缀将其分为 K 类具体的要求是:
选出 K 个不同的单词前缀作为 K 类对于字典上的每个单词只能属于 K 类中的某一个类不能同时属于多个类对于 K 类中的每个类至少包含有一个单词。
现在已知字典上一共有 N 个单词小蓝想要知道将这 N 个单词按照上述要求分为K 类一共有多少种不同的方案。两个方案不同指的是两个方案各自选出的 K 个单词前缀不完全相同。答案可能过大所以你需要将答案对 1000000007(即 1097)取模后输出。
输入格式
输入的第一行包含两个整数 N 和 K
接下来 NN 行每行包含一个单词由 l、q、b 三种字符组成。
输出格式
输出一个整数表示答案。答案可能很大请输出答案对 1000000007 取模的值。
分析:构建字典树然后通过递归计算每个节点的划分方案数。(不会
import java.util.*;public class Main {static final long MOD 1000000007; // 定义模数// 字典树节点类static class TrieNode {boolean isWord; // 标记当前节点是否是一个单词的结尾MapCharacter, TrieNode children new HashMap(); // 子节点映射}static TrieNode root new TrieNode(); // 字典树根节点public static void main(String[] args) {Scanner scanner new Scanner(System.in);int N scanner.nextInt(); // 单词数量int K scanner.nextInt(); // 分类数scanner.nextLine(); // 消耗换行符// 构建字典树for (int i 0; i N; i) {String word scanner.nextLine();insertWord(word);}// 计算并输出结果long[] result calculateSchemes(root, K);System.out.println(result[K]);}// 向字典树中插入单词private static void insertWord(String word) {TrieNode current root;for (char c : word.toCharArray()) {current.children.putIfAbsent(c, new TrieNode());current current.children.get(c);}current.isWord true; // 标记单词结尾}/*** 递归计算划分方案数* param node 当前节点* param K 分类数* return 长度为K1的数组res[i]表示划分为i类的方案数*/private static long[] calculateSchemes(TrieNode node, int K) {long[] res new long[K 1]; // 初始化结果数组// 如果是单词节点只能划分为1类if (node.isWord) {res[1] 1;return res;}// 收集子节点的计算结果Listlong[] childResults new ArrayList();for (TrieNode child : node.children.values()) {childResults.add(calculateSchemes(child, K));}// 合并子节点结果mergeResults(res, childResults, K);// 当前节点单独作为一类的情况res[1] (res[1] 1) % MOD;return res;}/*** 合并子节点的划分方案* param res 结果数组* param childResults 子节点结果列表* param K 分类数*/private static void mergeResults(long[] res, Listlong[] childResults, int K) {if (childResults.isEmpty()) return;switch (childResults.size()) {case 1: // 只有一个子节点System.arraycopy(childResults.get(0), 0, res, 0, Math.min(childResults.get(0).length, res.length));break;case 2: // 有两个子节点long[] left childResults.get(0);long[] right childResults.get(1);for (int i K; i 0; i--) {for (int j 1; j i; j) {if (j left.length (i - j) right.length) {res[i] (res[i] left[j] * right[i - j]) % MOD;}}}break;case 3: // 有三个子节点long[] first childResults.get(0);long[] second childResults.get(1);long[] third childResults.get(2);for (int i K; i 0; i--) {for (int j 1; j i; j) {for (int l 1; l i - j; l) {if (j first.length l second.length (i - j - l) third.length) {res[i] (res[i] first[j] * second[l] % MOD * third[i - j - l] % MOD) % MOD;}}}}break;}}
} 游戏的得分
问题描述
小蓝和小乔正在玩游戏一开始双方分数均为 1每局游戏都有多个轮次。游戏的每轮总有一个人获胜/失败其中获胜者分数变为原来的 4 倍失败者分数变为原来的 2 倍。小蓝和小乔玩了很多局游戏它们记下了每局游戏最终的分数对 998244353 取模的结果但他们忘记了每局游戏进行的轮次数。
请输出每局游戏中要得到给定的结果所需的最少轮次数。特别地如果小蓝和小乔记错了游戏的结果也就是无论如何也得不到输入的分数请输出 −1。
输入格式
输入的第一行包含一个整数 TT 表示游戏局数。
接下来 T 行每行包含两个整数 ai, bi 分别表示小蓝和小乔在第 i 局游戏的记录。
输出格式
输出 T 行每行包含一个整数其中第 i 行的整数表示得到第 i 局游戏给定结果所需的最少轮次数。
分析:不会,网上也找不到题解,欢迎补充
