网站上不去原因,wordpress伪静态结构,深圳 网站建设公,wordpress登陆访问蓝桥杯刷题——day4 题目一题干题目解析代码 题目二题干题目解析代码 题目一
题干
小蓝和朋友们在玩一个报数游戏。由于今年是2024 年#xff0c;他们决定要从小到大轮流报出是20或24倍数的正整数。前10个被报出的数是#xff1a;20,24,40,48,60,72,80,96,100,120。请问第2… 蓝桥杯刷题——day4 题目一题干题目解析代码 题目二题干题目解析代码 题目一
题干
小蓝和朋友们在玩一个报数游戏。由于今年是2024 年他们决定要从小到大轮流报出是20或24倍数的正整数。前10个被报出的数是20,24,40,48,60,72,80,96,100,120。请问第202420242024个被报出的数是多少 这是一道结果填空的题你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只输出这个整数填写多余的内容将无法得分。 题目链接报数游戏
题目解析
这道题目其实很简单我们最先的想法是设立一个计数器然后一个一个的遍历只要满足数字整除20或者整除24那么计数器就1但是这个方法会耗费很长的时间我们可以将20×24看作一个轮回先计算20到24之间的能整除20或者整除24的个数times然后用202420242024除以times得到商和余数商则表示经过了几个轮回而余数则表示是这个轮回的第几个数字那么将两者相加就表示了第202420242024个数是什么了问题解决下面是完整的代码
代码
import java.util.ArrayList;
public class Main {public static void main(String[] args) {ArrayListLong list new ArrayList();long times 0;for (Long i 1L; i 480; i) {if (i % 20 0 || i % 24 0) {list.add(i);times;}}Long a 202420242024L;Long tmp1 a / times;int tmp2 (int) (a % times);System.out.println(list.get(tmp2 - 1) 480L * tmp1);}
}题目二
题干
给定一个数组每次操作可以选择数组中任意两个相邻的元素x,y 并将其中的一个元素替换为gcd(x,y)其中gcd(x,y) 表示x 和y 的最大公约数。请问最少需要多少次操作才能让整个数组只含1。 输入 输入的第一行包含一个整数n表示数组长度。第二行包含n 个整数相邻两个整数之间用一个空格分隔。 输出 输出一行包含一个整数表示最少操作次数。如果无论怎么操作都无法满足要求输出-1。 示例一 输入 3 4 6 9 输出 4 题目链接最大公约数
题目解析
这道题目关键是如何找出一个最小子串该最小子串能够实现数组中的最大公约数为 1什么意思如果我们把一个子串中的一个元素变为了1那么我们就可以根据这个1把数组的其他元素都变成1什么意思我们下面的图 5和4的最大公倍数是1那么我们就可以把其中的一个数字变成1那么其他的也可以根据这个1变成1就像病毒扩散一样因此我们只需要找到一个数组里的最短子串并且该最短子串能够实现最大公倍数为1就能够完成因此我们完整的思路是
计算整个数组的 GCD。如果 GCD 不为 1直接输出 -1。寻找最短的子数组其 GCD 为 1记为长度L。最小操作次数为n−1(L−1)因为n−1是将所有元素通过邻近操作将本身变为1的次数。(L−1)是在将子数组 GCD 为 1其中一个元素变为1的操作次数。
下面是完整代码
代码
import java.util.Scanner;
public class Demo {public static void main(String[] args) {Scanner scanner new Scanner(System.in);//输入数组的长度int n scanner.nextInt();//输入数组的内容int[] arr new int[n];for (int i 0; i n; i) {arr[i] scanner.nextInt();}System.out.println(minOperations(n, arr));}private static int minOperations(int n, int[] arr) {//判断整体的GCDint overallGCD gcdArray(arr);if (overallGCD ! 1) {return -1;// 如果整体GCD不是1无论怎么操作都无法满足需求}//寻找最短子数组其GCD为1int minLength Integer.MAX_VALUE;for (int i 0; i n; i) {int currentGCD arr[i];for (int j i; j n; j) {currentGCD gcd(currentGCD, arr[j]);if (currentGCD 1) {minLength Math.min(minLength, j - i 1);}}}//如果没有找到任何子数组GCD为1if (minLength Integer.MAX_VALUE) {return -1;}return (n - 1) (minLength - 1);}private static int gcdArray(int[] arr) {int result arr[0];for (int i 1; i arr.length; i) {result gcd(result,arr[i]);if (result 0){return 1;}}return result;}private static int gcd(int a, int b) {//计算两个数的GCDwhile (b ! 0) {int tmp b;b a % b;a tmp;}return a;}
}
