LV4
1.天数
问题描述
我们计从 1949 年 10 月 1 日至 1949 年 10 月 2 日经过了 1 天。
请问从 1949 年 10 月 1 日至 2022 年 1 月 1 日经过了多少天？
答案提交
本题为一道结果填空的题，只需要算出结果后，在代码中使用输出语句将结果输出即可。
题解
直接用时间的api，一个LocalDate 用于表示日期，一个ChronoUnit 包含了多种时间单位，用于计算两个日期之间的差异
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 import java.time.LocalDate;import java.time.temporal.ChronoUnit;public class Main { public static void main (String[] args) { LocalDate startDate = LocalDate.of(1949 , 10 , 1 ); LocalDate endDate = LocalDate.of(2022 , 1 , 1 ); long daysBetween = ChronoUnit.DAYS.between(startDate, endDate); System.out.println(daysBetween); } }
2.好好学习
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
汤姆跟爷爷来中国旅游。一天，他帮助中国的小朋友贴标语。他负责贴的标语是分别写在四块红纸上的四个大字：“好、好、学、习”。但是汤姆不认识汉字，他就想胡乱地贴成一行。
请你替小汤姆算一下，他这样乱贴，恰好贴对的概率是多少？
答案是一个分数，请表示为两个整数比值的形式。例如：1/3 或 2/15 等。如果能够约分，请输出约分后的结果。
题解
共有4!种情况，只有两种符合
代码
1 2 3 4 5 6 7 8 9 10 11 import java.util.Scanner;public class Main { public static void main (String[] args) { System.out.println("1/12" ); } }
3.土地测量
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
造成高房价的原因有许多，比如土地出让价格。既然地价高，土地的面积必须仔细计算。遗憾的是，有些地块的形状不规则，比如是五边形。
一般需要把它划分为多个三角形来计算。
已知三边求三角形的面积需要用海伦定理
各条边长数据如下：
1 2 3 4 5 6 7 AB = 52.1 BC = 57.2 CD = 43.5 DE = 51.9 EA = 33.4 EB = 68.2 EC = 71.9
根据这些数据求五边形地块的面积。四舍五入到小数后两位。
题解
没有巧妙做法
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import java.util.Scanner;public class Main { public static void main (String[] args) { double ab=52.1 ; double bc=57.2 ; double cd=43.5 ; double de=51.9 ; double ea=33.4 ; double eb=68.2 ; double ec=71.9 ; double s1=(ea+ab+eb)/2.0 ; double a1=Math.sqrt(s1*(s1-ea)*(s1-ab)*(s1-eb)); double s2=(eb+bc+ec)/2.0 ; double a2=Math.sqrt(s2*(s2-eb)*(s2-bc)*(s2-ec)); double s3=(ec+cd+de)/2.0 ; double a3=Math.sqrt(s3*(s3-ec)*(s3-cd)*(s3-de)); System.out.printf("%.2f" ,a1+a2+a3); } }
4.组素数
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
素数就是不能再进行等分的数。比如：2 3 5 7 11 等。 9=3∗3 说明它可以3等分，因而不是素数。
我们国家在 1949 年建国。如果只给你 1 9 4 9 这 4 个数字卡片，可以随意摆放它们的先后顺序（但卡片不能倒着摆放啊，我们不是在脑筋急转弯！），那么，你能组成多少个 44 位的素数呢？
比如：1949，4919 都符合要求。
请你输出能组成的 4 位素数的个数，不要罗列这些素数!!
题解
判断素数的方法，是一个数循环除到自己的开根号，都不能除尽，则是素数。这里的组合不多，可以直接罗列。如果较多的情况可以用循环来循环出所有组合的情况，即从最小的数循环到最大的数，中间判断每一位上的数字，并且相应的数字计数器上–，如果最后计数器都为0，则是符合要求的组合
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 import java.util.Scanner;public class Main { static int count; public static void main (String[] args) { count=0 ; a(1499 ); a(1949 ); a(1994 ); a(4199 ); a(4919 ); a(4991 ); a(9149 ); a(9419 ); a(9491 ); a(9194 ); a(9941 ); a(9914 ); System.out.println(count); } public static void a (int i) { boolean a=true ; for (int j=2 ;j<=i/j;j++) { if (i%j==0 ) { a=false ; break ; } } if (a) { count++; } } }
5.梅森素数
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如果一个数字的所有真因子之和等于自身，则称它为“完全数”或“完美数”
例如：
1 2 6 = 1 + 2 + 3 28 = 1 + 2 + 4 + 7 + 14
早在公元前 300 多年，欧几里得就给出了判定完全数的定理：
若 2 n − 1 2^n−1 2 n − 1 2 ( n − 1 ) ∗ ( 2 n − 1 ) 2^{(n−1)}∗(2^n−1) 2 ( n − 1 ) ∗ ( 2 n − 1 )
但人们很快发现，当 n 很大时，判定一个大数是否为素数到今天也依然是个难题。
因为法国数学家梅森的猜想，我们习惯上把形如：2 n − 1 2^n−1 2 n − 1
截止 2013 年 2 月，一共只找到了 48 个梅森素数。 新近找到的梅森素数太大，以至于难于用一般的编程思路窥其全貌，所以我们把任务的难度降低一点：
1963 年，美国伊利诺伊大学为了纪念他们找到的第 2323 个梅森素数 n=11213，在每个寄出的信封上都印上了“2 11213 − 1 2^{11213}−1 2 11213 − 1
2 11213 − 1 2^{11213}−1 2 11213 − 1
题解
由于数字过大所以要用到BigInteger，然后直接算出这个数，再取最后100位
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import java.util.Scanner;import java.math.BigInteger;public class Main { public static void main (String[] args) { Scanner scan = new Scanner (System.in); BigInteger one = BigInteger.ONE; BigInteger two = BigInteger.TWO; BigInteger r = two.pow(11213 ).subtract(one); String s = r.toString(); String src = s.substring(s.length()-100 ,s.length()); System.out.println(src); scan.close(); } }
6.生日蜡烛
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
某君从某年开始每年都举办一次生日 party，并且每次都要吹熄与年龄相同根数的蜡烛。
现在算起来，他一共吹熄了 236 根蜡烛。
请问，他从多少岁开始过生日 party的？
请输出他开始过生日 party 的年龄数。
题解
两层循环一层控制开始年龄，内层去从当前年龄开始加，当正好等于的时候输出
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import java.util.Scanner;public class Main { public static void main (String[] args) { for (int age=1 ;age<100 ;age++) { int t=0 ; for (int i=age;i<100 ;i++) { t=t+i; if (t==236 ) { System.out.println(age); } if (t>236 ) { break ; } } } } }
7.蛇形填数
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如下图所示，小明用从 1 开始的正整数“蛇形”填充无限大的矩阵。
1 2 3 4 5 6 1 2 6 7 15 ... 3 5 8 14 ... 4 9 13 ... 10 12 ... 11 ... ...
容易看出矩阵第二行第二列中的数是 55。请你计算矩阵中第 2020 行第 2020 列的数是多少？
题解
找规律，每次加上的数字依次加4
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import java.util.Scanner;public class Main { public static void main (String[] args) { int count=1 ; for (int i=1 ;i<21 ;i++) { for (int j=1 ;j<i;j++) { count=count+4 ; } } System.out.println(count); } }
8.方程整数解
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
方程: a 2 + b 2 + c 2 = 1000 a^2+b^2+c^2=1000 a 2 + b 2 + c 2 = 1000
这个方程有正整数解吗？有：a,b,c=6,8,30 就是一组解。 你能算出另一组合适的解吗？
请填写该解中最小的数字。
题解
纯暴力，但是后一个数字的开始大小是前一个数字的大小
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java.util.*;public class Main { public static void main (String[] args) { for (int i=1 ;i<40 ;i++) { for (int j=i;j<40 ;j++) { for (int k=j;k<40 ;k++) { if (i*i+j*j+k*k==1000 &&i!=6 ) { System.out.println(i); return ; } } } } } }
9.跑步锻炼
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝每天都锻炼身体。
正常情况下，小蓝每天跑 1 千米。如果某天是周一或者月初（1 日），为了激励自己，小蓝要跑 22 千米。如果同时是周一或月初，小蓝也是跑 22 千米。
小蓝跑步已经坚持了很长时间，从 2000年 1 月 1 日周六（含）到 2020 年 10 月 1 日周四（含）。请问这段时间小蓝总共跑步多少千米？
题解
依旧是用时间api
或者用excel：**1.新建一个Excel文件 **
**2.填充2000年1月1日到2020年10月1日 **
**3.通过单元格格式中在日期后加上对应的星期数 **
4.单元格行数记为h；查找“星期一”，找到的数量记为a; 查找“月1日”（不能是1日，否则如11日也会计入），找到的数量记为b；查找“月1日星期一”，找到的数量记为c；答案n=h+a+b-c;
h =7580 这个只需要设置整个单元格格式（最好不要使用日期格式，因为没有星期，只有年月日）为自定义格式 yyyy"年"m"月"d"日"aaaa 这样在填充时就会自动格式化位年月日星期几的格式
点击填充 >> 序列>> 终止值 2020年10月1日就可以自动填充了 （选择序列产生在列）h 就可以出来了
另外为什么是 h + a + b-c ? 因为h中已经把星期一和月初一算过一次了，因为他要算两次 ，所以就再加一次，减去 c是因为a 和b中已经算过了一次了，只需要再减去星期一和月初一同时满足的就可以
另外查找时有可能遇到无法查找，这可能是因为，查找选项中的查找范围没有设置为值 ，因为他默认是查找公式，或者查找的格式没有清空
h=7580，a=1083，b=250，c=34
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import java.time.LocalDate;public class Main { public static void main (String[] args) { LocalDate localDate = LocalDate.of(2000 , 1 , 1 ); LocalDate endDate = LocalDate.of(2020 , 10 , 2 ); int sum = 0 ; while (localDate.compareTo(endDate) != 0 ) { if (localDate.getDayOfWeek().getValue() == 1 || localDate.getDayOfMonth() == 1 ) { sum+=2 ; }else { sum+=1 ; } localDate = localDate.plusDays(1 ); } System.out.println(sum); } }
10.等差素数列
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
2,3,5,7,11,13,…是素数序列。 类似：7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。
上边的数列公差为 30，长度为 6。
2004 年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。 这是数论领域一项惊人的成果！
有这一理论为基础，请你借助手中的计算机，满怀信心地搜索：
长度为 10 的等差素数列，其公差最小值是多少？
题解
依旧暴力，需要一个函数用来判断是否为素数。然后循环，外层循环控制公差，这样可以保证公差是最小的，不会受到内层循环的初始数字的影响。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 public class Main { public static void main (String[] args) { for (int i = 1 ;i<10000 ;i++){ for (int j = 1 ;j<1000 ;j++){ int k; for (k=0 ;k<=9 ;k++){ if (!isPrime(j+k*i)) break ; } if (k==10 ) { System.out.println(i); return ; } } } } public static boolean isPrime (int num) { for (int i = num-1 ;i>1 ;i--){ if (num%i==0 ) return false ; } return true ; } }
11.Fibonacci 集合
问题描述
小蓝定义了一个 Fibonacci 集合 F, 集合的元素如下定义:
最小的 5 个 Fibonacci 数 1,2,3,5,8 属于集合 FF 。
如果一个元素 x 属于 F, 则 3x+2、5x+33x +2、5x +3 和 8x+5 都属于集合 FF 。
其他元素都不属于 F 。
请问，这个集合中的第 2020 小元素的值是多少?
题解
把已经存在过的数字的对应数组中下标的赋值为true，后面在循环里判断是否为true
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner scan = new Scanner (System.in); boolean [] f = new boolean [20200000 ]; f[1 ] = true ; f[2 ] = true ; f[3 ] = true ; f[5 ] = true ; f[8 ] = true ; int flag = 1 ; int cnt = 0 ; while (true ) { if (f[flag]) { f[3 *flag+2 ] = true ; f[5 *flag+3 ] = true ; f[8 *flag+5 ] = true ; cnt++; if (cnt==2020 ) { break ; } } flag++; } System.out.println(flag); scan.close(); } }
12.修剪灌木
问题描述
爱丽丝要完成一项修剪灌木的工作。
有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌木, 让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始, 每天向右修剪一棵灌木。当修剪了最右侧的灌木后, 她会调转方向, 下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。
灌木每天从早上到傍晩会长高 1 厘米, 而其余时间不会长高。在第一天的早晨, 所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。
输入格式
一个正整数 N, 含义如题面所述。
输出格式
输出 N 行, 每行一个整数, 第 i 行表示从左到右第 i 棵树最高能长到多高。
样例输入
样例输出
题解
直接用暴力的做法太复杂了。简单一点就是考虑这颗树离那一边更远，最大值就是这个距离的两倍
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import java.util.Scanner;public class Test2 { public static void main (String[] args) { Scanner sc = new Scanner (System.in); int n = sc.nextInt(); for ( int i = 1 ; i <= n ; i++ ){ int max = Math.max(n-i,i-1 ); System.out.println(max*2 ); } } }
13.阶乘求和
问题描述
令 S=1!+2!+3!+⋯+202320232023!，求 S 的末尾 9 位数字。
提示：答案首位不为 0。
题解
从40的阶乘开始，后面的九位就全都是0了，所以要算的就是前四十个的阶乘的和
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import java.util.Scanner;public class Main { public static void main (String[] args) { long sum = 0 ; for (int i = 1 ; i <= 40 ; i++) { long temp = 1 ; for (int j = 1 ; j <= i; j++) { temp *= j; temp = temp % 1000000000l ; } sum += temp; } System.out.println(sum % 1000000000l ); } }
14.奇怪的捐赠
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
地产大亨 Q 先生临终的遗愿是：拿出 100 万元给 X 社区的居民抽奖，以稍慰藉心中愧疚。
麻烦的是，他有个很奇怪的要求：
100 万元必须被正好分成若干份（不能剩余）。每份必须是 7 的若干次方元。比如：1 元, 7 元， 49 元，343 元，…
相同金额的份数不能超过 5 份。
在满足上述要求的情况下，分成的份数越多越好！
请你帮忙计算一下，最多可以分为多少份？
题解
直觉做题就是暴力，从最小的面额开始循环，最后==。
巧妙的做法是，把100万转化为七进制，也就是11333311，第n位就代表7的n次方
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner scan = new Scanner (System.in); String str = Integer.toString(1000000 , 7 ); int count = 0 ; for (int i = 0 ; i < str.length(); i++) { count += str.charAt(i) - '0' ; } System.out.println(count); scan.close(); } }
15.好数
问题描述
一个整数如果按从低位到高位的顺序，奇数位 (个位、百位、万位 ⋯⋯ ) 上的数字是奇数，偶数位 (十位、千位、十万位 ⋯⋯ ) 上的数字是偶数，我们就称之为 “好数”。
给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。
输入格式
一个整数 N。
输出格式
一个整数代表答案。
样例输入 1
样例输出 1
样例输入 2
样例输出 2
样例说明
对于第一个样例，24 以内的好数有 1、3、5、7、9、21、23，一共 7 个。
题解
就循环判断从1开始到这个数字
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import java.util.*;public class Main { public static int pr (int a) { int x = 1 ; while (a!=0 ){ int t = a%10 ; if (x%2 ==1 ){ if (t%2 ==0 ) return 0 ; }else { if (t%2 ==1 ) return 0 ; } x++; a /= 10 ; } return 1 ; } public static void main (String[] args) { Scanner sc=new Scanner (System.in); int n=sc.nextInt(); int count=0 ; for (int i=1 ;i<=n;i++){ if (pr(i)==1 ){ count++; } } System.out.println(count); } }
16.迷宫
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。
1 2 3 4 010000 000100 001001 110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中 D<L<R<U。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 01010101001011001001010110010110100100001000101010 00001000100000101010010000100000001001100110100101 01111011010010001000001101001011100011000000010000 01000000001010100011010000101000001010101011001011 00011111000000101000010010100010100000101100000000 11001000110101000010101100011010011010101011110111 00011011010101001001001010000001000101001110000000 10100000101000100110101010111110011000010000111010 00111000001010100001100010000001000101001100001001 11000110100001110010001001010101010101010001101000 00010000100100000101001010101110100010101010000101 11100100101001001000010000010101010100100100010100 00000010000000101011001111010001100000101010100011 10101010011100001000011000010110011110110100001000 10101010100001101010100101000010100000111011101001 10000000101100010000101100101101001011100000000100 10101001000000010100100001000100000100011110101001 00101001010101101001010100011010101101110000110101 11001010000100001100000010100101000001000111000010 00001000110000110101101000000100101001001000011101 10100101000101000000001110110010110101101010100001 00101000010000110101010000100010001001000100010101 10100001000110010001000010101001010101011111010010 00000100101000000110010100101001000001000000000010 11010000001001110111001001000011101001011011101000 00000110100010001000100000001000011101000000110011 10101000101000100010001111100010101001010000001000 10000010100101001010110000000100101010001011101000 00111100001000010000000110111000000001000000001011 10000001100111010111010001000110111010101101111000
题解
这题得用bfs来做。核心的就是这个bfs函数，首先要一个队列用来存储已出队列的坐标的子坐标，并且要一个数组用来记录对应坐标是如何从父节点到达的。全都初始化后开始核心部分，如果队列不空就开始循环，先首元素出队列，然后判断这个元素的坐标是否是终点，如果不是终点，那么对于当前，进行一个循环，去加上一个方向，但是要注意的是，这里的方向是二维数组的方向，而不是正常数学上的直角坐标系。加上后判断坐标是否合法，如果合法就标记为已访问过，并且加入到队列中，并且更新当前节点的父节点的横纵坐标，以及路径信息。如果上面判断的是终点，那么循环把节点加入到创建的路径中并再获取其父节点再添加，最后要先把这个路径反向再输出。然后就是主函数，先用字符串读取全部数据，然后逐个读取字符，再转成整型。最后调用bfs即可。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 import java.util.*;public class Main { static int [] dx={1 ,0 ,0 ,-1 }; static int [] dy={0 ,-1 ,1 ,0 }; static char [] direction={'D' ,'L' ,'R' ,'U' }; public static String bfs (int [][] pz,int n,int m) { Queue<int []> queue = new LinkedList <>(); boolean [][] visited=new boolean [n][m]; int [][] parentx=new int [n][m]; int [][] parenty=new int [n][m]; char [][] directionFromParent=new char [n][m]; queue.add(new int []{0 ,0 }); visited[0 ][0 ]=true ; parentx[0 ][0 ]=-1 ; parenty[0 ][0 ]=-1 ; while (!queue.isEmpty()) { int [] current=queue.poll(); int x=current[0 ]; int y=current[1 ]; if (x==n-1 &&y==m-1 ) { StringBuilder path=new StringBuilder (); int px=x,py=y; while (parentx[px][py]!=-1 ) { path.append(directionFromParent[px][py]); int tmpX = parentx[px][py]; int tmpY = parenty[px][py]; px = tmpX; py = tmpY; } return path.reverse().toString(); } for (int i=0 ;i<4 ;i++) { int nx=x+dx[i]; int ny=y+dy[i]; if (nx>=0 &&nx<n&&ny>=0 &&ny<m&&!visited[nx][ny]&&pz[nx][ny]==0 ) { visited[nx][ny]=true ; queue.add(new int []{nx,ny}); parentx[nx][ny]=x; parenty[nx][ny]=y; directionFromParent[nx][ny]=direction[i]; } } } return "no" ; } public static void main (String[] args) { int n=30 ; int m=50 ; int [][] pz=new int [n][m]; String[] pz1={"01010101001011001001010110010110100100001000101010" , "00001000100000101010010000100000001001100110100101" , "01111011010010001000001101001011100011000000010000" , "01000000001010100011010000101000001010101011001011" , "00011111000000101000010010100010100000101100000000" , "11001000110101000010101100011010011010101011110111" , "00011011010101001001001010000001000101001110000000" , "10100000101000100110101010111110011000010000111010" , "00111000001010100001100010000001000101001100001001" , "11000110100001110010001001010101010101010001101000" , "00010000100100000101001010101110100010101010000101" , "11100100101001001000010000010101010100100100010100" , "00000010000000101011001111010001100000101010100011" , "10101010011100001000011000010110011110110100001000" , "10101010100001101010100101000010100000111011101001" , "10000000101100010000101100101101001011100000000100" , "10101001000000010100100001000100000100011110101001" , "00101001010101101001010100011010101101110000110101" , "11001010000100001100000010100101000001000111000010" , "00001000110000110101101000000100101001001000011101" , "10100101000101000000001110110010110101101010100001" , "00101000010000110101010000100010001001000100010101" , "10100001000110010001000010101001010101011111010010" , "00000100101000000110010100101001000001000000000010" , "11010000001001110111001001000011101001011011101000" , "00000110100010001000100000001000011101000000110011" , "10101000101000100010001111100010101001010000001000" , "10000010100101001010110000000100101010001011101000" , "00111100001000010000000110111000000001000000001011" , "10000001100111010111010001000110111010101101111000" }; for (int i=0 ;i<n;i++) { for (int j=0 ;j<m;j++) { pz[i][j]=pz1[i].charAt(j)=='1' ?1 :0 ; } } String result=bfs(pz,n,m); System.out.println(result); } }
17.报数游戏
问题描述
小蓝和朋友们在玩一个报数游戏。由于今年是 2024 年，他们决定要从小到大轮流报出是 20 或 24 倍数的正整数。前 10 个被报出的数是：20,24,40,48,60,72,80,96,100,120。请问第 202420242024 个被报出的数是多少?
题解
202420242024是偶数，偶数个都是24的倍数，所以202420242024/2*24
代码
1 2 3 4 5 6 7 import java.util.Scanner;public class Main { public static void main (String[] args) { System.out.println(202420242024L /2 *24 ); } }
18.滑行
问题描述
小蓝准备在一个空旷的场地里面滑行，这个场地的高度不一，小蓝用一个 n 行 m 列的矩阵来表示场地，矩阵中的数值表示场地的高度。
如果小蓝在某个位置，而他上、下、左、右中有一个位置的高度（严格）低于当前的高度，小蓝就可以滑过去，滑动距离为 1 。
如果小蓝在某个位置，而他上、下、左、右中所有位置的高度都大于等于当前的高度，小蓝的滑行就结束了。
小蓝不能滑出矩阵所表示的场地。
小蓝可以任意选择一个位置开始滑行，请问小蓝最多能滑行多远距离。
输入格式
输入第一行包含两个整数 n, m，用一个空格分隔。
接下来 n 行，每行包含 m 个整数，相邻整数之间用一个空格分隔，依次表示每个位置的高度。
输出格式
输出一行包含一个整数，表示答案。
样例输入
1 2 3 4 5 4 5 1 4 6 3 1 11 8 7 3 1 9 4 5 2 1 1 3 2 2 1
样例输出
样例说明
滑行的位置一次为 (2,1),(2,2),(2,3),(3,3),(3,2),(4,2),(4,3)。
题解
这题用到dfs。核心的dfs函数中每次移动并判断完合法性后就选择一个最大值赋值，每次选择最大值都是在进行递归这样能实现一条路走到底
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 import java.util.Scanner;public class Main { static int n; static int m; static int [][] height; static int [][] dp; static int [] dx={-1 ,1 ,0 ,0 }; static int [] dy={0 ,0 ,-1 ,1 }; public static void main (String[] args) { Scanner scan = new Scanner (System.in); n=scan.nextInt(); m=scan.nextInt(); height=new int [n][m]; for (int i=0 ;i<n;i++) { for (int j=0 ;j<m;j++) { height[i][j]=scan.nextInt(); } } dp=new int [n][m]; for (int q=0 ;q<n;q++) { for (int p=0 ;p<m;p++) { dp[q][p]=-1 ; } } int ans=0 ; for (int e=0 ;e<n;e++) { for (int k=0 ;k<m;k++) { ans=Math.max(ans,dfs(e,k)); } } System.out.println(ans); scan.close(); } static int dfs (int x,int y) { if (dp[x][y]!=-1 ) { return dp[x][y]; } dp[x][y]=1 ; for (int o=0 ;o<4 ;o++) { int nx=x+dx[o]; int ny=y+dy[o]; if (nx>=0 &&nx<n&&ny>=0 &&ny<m&&height[nx][ny]<height[x][y]) { dp[x][y]=Math.max(dp[x][y],1 +dfs(nx,ny)); } } return dp[x][y]; } }
19.跑步计划
问题描述
小蓝计划在某天的日期中出现 1 时跑 5 千米，否则只跑 1 千米。注意日期中出现 1 不仅指年月日也指星期。
请问按照小蓝的计划，2023 年小蓝总共会跑步锻炼多少千米?例如，5 月 1 日、1 月 13 日、11 月 5 日、4 月 3 日 (星期一) 小蓝会跑 5 千米，而 5 月 23 日小蓝会跑 1 千米 (示例日期均为 2023 年)
题解
和之前的一样依旧excel神力，正经做可以用日期类
代码
1 2 3 4 5 6 7 8 9 10 import java.util.Scanner;public class Main { public static void main (String[] args) { System.out.println(242 *5 +365 -242 ); } }
20.分布式队列
问题描述
小蓝最近学习了一种神奇的队列： 分布式队列。简单来说，分布式队列包含 N 个节点（编号为 0 至 N−1，其中 0 号为主节点），其中只有一个主节点，其余为副节点。
主/副节点中都各自维护着一个队列，当往分布式队列中添加元素时，都是由主节点完成的（每次都会添加元素到主节点对应的队列的尾部）；副节点只负责同步主节点中的队列。可以认为主/副节点中的队列是一个长度无限的一维数组，下标为 0,1,2,3…，同时副节点中的元素的同步顺序和主节点中的元素添加顺序保持一致。
由于副本的同步速度各异，因此为了保障数据的一致性，元素添加到主节点后，需要同步到所有的副节点后，才具有可见性。
给出一个分布式队列的运行状态，所有的操作都按输入顺序执行。你需要回答在某个时刻，队列中有多少个元素具有可见性。
输入格式
第一行包含一个整数 N，表示节点个数。
接下来包含多行输入，每一行包含一个操作，操作类型共有以下三种： add、sync 和 query，各自的输入格式如下：
add element： 表示这是一个添加操作，将元素 element 添加到队列中;
sync f o l l o w e r i d follower_{id} f o ll o w e r i d f o l l o w e r i d follower_{id} f o ll o w e r i d
query： 查询操作，询问当前分布式队列中有多少个元素具有可见性。
输出格式
对于每一个 query 操作，输出一行，包含一个整数表示答案。
样例输入
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 3 add 1 add 2 query add 1 sync 1 sync 1 sync 2 query sync 1 query sync 2 sync 2 sync 1 query
样例输出
样例说明
执行到第一个 query 时，队列内容如下：
0： [1,2]
1： []
2： []
两个副节点中都无元素，因此答案为 0。
执行到第二个 query 时，队列内容如下：
0： [1,2,1]
1： [1,2]
2： [1]
只有下标为 0 的元素被所有节点同步，因此答案为 1 。
执行到第三个 query 时，队列内容如下：
0： [1,2,1]
1： [1,2,1]
2： [1]
只有下标为 0 的元素被所有节点同步，因此答案为 1。
执行到第四个 query 时，队列内容如下：
0： [1,2,1]
1： [1,2,1]
2： [1,2,1]
三个元素都被所有节点同步，因此答案为 3。
题解
题目看着很长，但是实际上不复杂，他最终要显示的就是一个数字，也就是说，具体添加了什么到主节点不重要，同步到副节点什么也不重要，重要的是同步到了哪个副节点。所以对于主节点只需要用一个变量来记录总数即可，（因为后面需要判断主节点中个数是否大于副节点中的个数，这样才能添加进去）其次对于副节点来说就用一个数组来表示，相应的下标对应相应的副节点，然后同步的时候就++。最后就是判断用户输入的指令是什么，用equals来比较字符串即可，如果是添加和同步就再获取下一个数字，如果是查询就直接变量数组找到最小。然后把这一段都放到while循环里，条件是能读取到下一个，这里用hasNext，专门用来判断的方法，不会读取到下一个。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner scan = new Scanner (System.in); int n=scan.nextInt(); int total=0 ; int [] sy=new int [n]; while (scan.hasNext()) { String str=scan.next(); if (str.equals("add" )) { int a=scan.nextInt(); total++; } if (str.equals("sync" )) { int b=scan.nextInt(); if (sy[b]<total) { sy[b]++; } } if (str.equals("query" )) { int min=Integer.MAX_VALUE; for (int i=1 ;i<n;i++) { min=Math.min(min,sy[i]); } System.out.println(min); } } scan.close(); } }
21.定时任务
问题描述
Cron 表达式在定时任务中经常被使用，在这里我们用了一种简化后的版本 SimpleCron 表达式：SimpleCron 表达式是一个具有时间含义的字符串，字符串以 4 个空格隔开，分为 5 个域，格式为 X X X X X，其中 X 是一个域的占位符。5 个域从左至右依次为秒 (0−59)、分钟 (0−59)、小时 (0−23)、日期 (1−31)、月份 (1−12)，其中括号内为他们各自的取值范围。同时域内取值也可以使用一些特殊字符（每个域内只能使用一种特殊字符）:
特殊字符 ∗ （ASCII 码为 42）表示所有可能的值。例如：在分钟域内表示每一分钟；在日期域内表示月内的每一天。
特殊字符 , （ASCII 码为 44）表示列出枚举值。例如：在秒域内，3,20表示分别在 3 秒和 20 秒执行一次任务。
特殊字符 − （ASCII 码为 45）表示范围，可以视为连续的若干个枚举值。例如：1−5 等价于 1,2,3,4,5。
例如，4 2 1,3,15 1−31∗表示的含义是每个月份中的每一天中的 01:02:04、03:02:04、15:02:04 这三个时刻各执行一次，在 2023 年一共会执行 1095 次。
现在给出你一个合法的 SimpleCron 表达式，其中用到的所有数字均没有前导零。请问在 2023 一整年当中，使用了这个表达式的定时任务总计会执行多少次?
输入格式
输入一行，包含一个 SimpleCron 字符串。
输出格式
输出一行，包含一个整数表示答案。
样例输入
样例输出
题解
重点在于分解字符串
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 import java.util.*;public class Main {static int [] level = {59 , 59 , 23 , 31 , 12 }; static int [] m = {0 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31 }; public static void main (String[] args) { Scanner scan = new Scanner (System.in); String[] s = scan.nextLine().split(" " ); ArrayList<Integer>[] a = new ArrayList [5 ]; for (int i = 0 ; i < 5 ; i ++ ) { a[i] = new ArrayList <>(); if (s[i].contains("*" )) { for (int j = i == 4 || i == 3 ? 1 : 0 ; j <= level[i]; j ++ ) { a[i].add(j); } } else if (s[i].contains("-" )) { String[] s1 = s[i].split("-" ); int l = Integer.parseInt(s1[0 ]); int r = Integer.parseInt(s1[1 ]); for (int j = l; j <= r; j ++ ) { a[i].add(j); } } else if (s[i].contains("," )) { String[] s1 = s[i].split("," ); for (String j : s1) { a[i].add(Integer.parseInt(j)); } } else { a[i].add(Integer.parseInt(s[i])); } } int ans = 0 ; for (int i = 0 ; i < a[4 ].size(); i ++ ) for (int j = 0 ; j < a[3 ].size() && a[3 ].get(j) <= m[a[4 ].get(i)]; j ++) { ans += a[0 ].size() * a[1 ].size() * a[2 ].size(); } System.out.println(ans); scan.close(); } }
22.类斐波那契循环数
问题描述
对于一个有 n 位的十进制数 N=d 1 d 2 d 3 … d n d_1d_2d_3…d_n d 1 d 2 d 3 … d n
{S 1 = d 1 , S 2 = d 2 , S 3 = d 3 , … , S n = d n S_1=d_1,S_2=d_2,S_3=d_3,…,S_n=d_n S 1 = d 1 , S 2 = d 2 , S 3 = d 3 , … , S n = d n
数列 S 的第 k(k>n)个数为：
∑ i = k − n k − 1 S i \sum_{i=k−n}^{k−1}S_i ∑ i = k − n k − 1 S i
如果这个数 N 会出现在对应的类斐波那契数列 S 中，那么 N 就是一个类斐波那契循环数。
例如对于 197，对应的数列 S 为：
{1,9,7,17,33,57,107,197,…}
197 出现在 S 中，所以 197是一个类斐波那契循环数。
请问在 0 至 10 7 10^7 1 0 7
题解
这道题就是一个反向遍历，拆解数字，滑动窗口。先做一个拆解数字的函数，先把数字转成字符串，再把每一位取出来，然后累加，这里累加出来的就是第n+1个数，所以下面定义的next的初值就是累加和，然后判断是否等于这个数本身，如果不是就继续求下一个，下一个的值就是前n个的和，所以用滑动窗口。最后在主函数中用反向遍历。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 import java.util.Scanner;public class Main { static boolean isLoopNum (int N) { String str = Integer.toString(N); int n = str.length(); int [] win = new int [n]; long sum=0 ; for (int i=0 ;i<n;i++) { win[i]=str.charAt(i)-'0' ; sum=sum+win[i]; } int idx=0 ; while (true ) { long next=sum; if (next==N) { return true ; } if (next>N) { return false ; } sum=sum-win[idx]+next; win[idx]=(int )next; idx++; if (idx==n) { idx=0 ; } } } public static void main (String[] args) { for (int i=10000000 ;i>=0 ;i--) { if (isLoopNum(i)==true ) { System.out.println(i); break ; } } } }
23.Fibonacci 数列与黄金分割
题目描述
Fibonacci 数列是非常著名的数列：
F[1]=1,
F[2]=1,
对于 i>3，F[i]=F[i−1]+F[i−2]。
Fibonacci 数列有一个特殊的性质，前一项与后一项的比值，F[N]/F[N+1]， 会趋近于黄金分割。
为了验证这一性质，给定正整数 N，请你计算 F[N]/F[N+1]，并保留 8 位小数。
输入描述
输入一个正整数 N (1≤N≤2×10 9 10^9 1 0 9
输出描述
输出 F[N]/F[N+1]。答案保留 8 位小数。
输入输出样例
示例
输入
输出
题解
本来打算全部算出来的，但是java中的数组不允许用long，只能int，所以改成了两个变量滚动，但是这样只能通过60%，对于这种求比值，极限的问题，一般不能直接求，大概率会导致溢出的问题，得进行数学上的转化，这道题就得转化为r = 1 / (1 + r)
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner scan = new Scanner (System.in); long N=scan.nextLong(); if (N <= 20 ) { double r = 1.0 ; for (long i = 1 ; i < N; i++) { r = 1.0 / (1.0 + r); } System.out.printf("%.8f" , r); } else { System.out.printf("%.8f" , (Math.sqrt(5.0 ) - 1.0 ) / 2.0 ); } scan.close(); } }
24.砝码称重
问题描述
你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W 1 , W 2 , ⋅ ⋅ ⋅ , W N W_1,W_2,⋅⋅⋅,W_N W 1 , W 2 , ⋅ ⋅ ⋅ , W N
请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数 N。
第二行包含 N 个整数：W 1 , W 2 , W 3 , ⋅ ⋅ ⋅ , W N W_1,W_2,W_3,⋅⋅⋅,W_N W 1 , W 2 , W 3 , ⋅ ⋅ ⋅ , W N
输出格式
输出一个整数代表答案。
样例输入
样例输出
样例说明
能称出的 10种重量是：1、2、3、4、5、6、7、9、10、11。
1=1；
2=6−4(天平一边放 6，另一边放 4)；
3=4−1；
4=4；
5=6−1；
6=6；
7=1+6；
9=4+6−1；
10=4+6；
11=1+4+6。
题解
这题用dp，这里的dp数组表示的是差值。对于每个砝码都可以有三种选择，不放，放在重的一边，放在轻的一边，并且把这个结果给一个新的dp数组，这个数组代表的是放入当前砝码后的结果，最后再把这个结果赋值回原dp数组
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner scan = new Scanner (System.in); int n=scan.nextInt(); int [] weight=new int [n]; int sum=0 ; for (int i=0 ;i<n;i++) { weight[i]=scan.nextInt(); sum=sum+weight[i]; } boolean [] dp=new boolean [sum+1 ]; dp[0 ]=true ; for (int j=0 ;j<n;j++) { boolean [] newdp=new boolean [sum+1 ]; for (int d=0 ;d<sum+1 ;d++) { if (dp[d]) { newdp[d]=true ; if (d+weight[j]<=sum) { newdp[d+weight[j]]=true ; newdp[Math.abs(d-weight[j])]=true ; } } } dp=newdp; } int count=0 ; for (int k=1 ;k<sum+1 ;k++) { if (dp[k]) { count++; } } System.out.println(count); scan.close(); } }
25.小蓝与钥匙
问题描述
小蓝是幼儿园的老师, 他的班上有 28 个孩子, 今天他和孩子们一起进行了 一个游戏。
小蓝所在的学校是寄宿制学校, 28 个孩子分别有一个自己的房间, 每个房间对应一把钥匙, 每把钥匙只能打开自己的门。现在小蓝让这 28 个孩子分别将自己宿舍的钥匙上交, 再把这 28 把钥匙随机打乱分给每个孩子一把钥匙, 有 28!=28×27×⋯×1 种分配方案。小蓝想知道这些方案中, 有多少种方案恰有一半的孩子被分到自己房间的钥匙 (即有 14 个孩子分到的是自己房间的钥匙, 有 14 个孩子分到的不是自己房间的钥匙)。
题解
直接暴力会超时。要求有14个人拿到对应钥匙，那就先求选14个人有多少种可能，然后剩下的14个人对其进行全错排列：f(n)=(n-1)*(f(n-1)+f(n-2))
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import java.util.Scanner;public class Main { public static void main (String[] args) { System.out.println(f(14 )*paiLie()); } public static long f (int n) { if (n==1 ) { return 0 ; } if (n==2 ) { return 1 ; } return (n-1 )*(f(n-1 )+f(n-2 )); } static long paiLie () { long ans=1 ; for (long i = 0 ; i < 14 ; i++) { ans=ans*(28 -i)/(i+1 ); } return ans; } }
26.X质数
问题描述
对于一个含有 M 个数位的正整数 N，任意选中其中 K 个不同的数位（0≤K<M），将这些选中的数位删除之后，余下的数位按照原来的顺序组成了一个新的数字 P 。如果至少存在一个 P 是质数，我们就称 N 是一个 X 质数。例如，对于整数 7869 ，我们可以删去 7 和 6 ，得到一个新的数字 89 ，由于 89是一个质数，因此 7869 是一个 X 质数。又如，对于整数 77 ，可以删去一个 7 后变为质数 7 ，因此 77 也是一个 X 质数。
请问 1至 1000000中一共有多少个不同的 X 质数。
题解
对于这道题，先把这个范围内的质数全部求出来，这里用欧拉筛法或者埃氏筛法，埃氏筛法就是把质数的倍数都筛掉，但是会出现重复筛的情况，效率较低，但是欧拉筛法就可以每个数只被最小质子因子筛掉。把所有质数都求出之后，接下就是要对每一个数字，先转成字符串，再求出其每一个子字符串，这里用dfs递归来做，一个数字对于其每一个数位都做判断，取或者不取这一位。再把取出的子字符串与筛出的质数列表中的对比。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 import java.util.*;public class Main { public static boolean dfs (char [] d,int idx,int cur,boolean picked,boolean [] isPrime) { if (idx==d.length) { return picked&&isPrime[cur]; } if (dfs(d,idx+1 ,cur,picked,isPrime)) { return true ; } int next=cur*10 +(d[idx]-'0' ); if (dfs(d,idx+1 ,next,true ,isPrime)) { return true ; } return false ; } public static void main (String[] args) { int max=1000000 ; boolean [] isPrime=new boolean [max+1 ]; Arrays.fill(isPrime,true ); isPrime[0 ]=isPrime[1 ]=false ; ArrayList<Integer> primes=new ArrayList <>(); for (int i=2 ;i<max+1 ;i++) { if (isPrime[i]) { primes.add(i); } for (int p:primes) { if (p*i>max) { break ; } isPrime[p*i]=false ; if (i%p==0 ) { break ; } } } int ans=0 ; for (int N=0 ;N<max+1 ;N++) { char [] d=String.valueOf(N).toCharArray(); if (dfs(d,0 ,0 ,false ,isPrime)) { ans++; } } System.out.println(ans); } }
27.星球
问题描述
小明驾驶飞船对某星系发起攻击。星系中有 n 颗星球，编号依次是 1,2,…,n。第 i 颗星球的坐标为 (x i , y i , z i x_i,y_i,z_i x i , y i , z i w i w_i w i
小明需要规划出进攻这 n 颗星球的顺序使得其进攻所需能量最少。
对于一个遍历顺序 p 1 , p 2 , . . . , p n p_1,p_2,...,p_n p 1 , p 2 , ... , p n E = ∑ i = 2 n d ( p i − 1 , p i ) × w i E=\sum^n_{i=2}d(p_{i−1},p_i)×w_i E = ∑ i = 2 n d ( p i − 1 , p i ) × w i d ( p i − 1 , p i ) d(p_{i−1},p_i) d ( p i − 1 , p i ) p i − 1 p_{i−1} p i − 1 p i p_i p i
输入描述
输入共 n+1 行。
第一行为一个正整数 n。
后面 n 行，每行四个整数 x i , y i , z i , w i x_i,y_i,z_i,w_i x i , y i , z i , w i
输出描述
输出共 1 行，一个浮点数（保留两位小数）。
样例输入
1 2 3 4 3 4 3 3 5 2 2 3 5 3 1 1 3
样例输出
样例说明
当进攻顺序为 {1,2,3} 时，所需能量最小，为 5 5 + 3 6 5\sqrt5+3\sqrt6 5 5 + 3 6
题解
这是一个tsp旅行商问题，这道题的n较小，可以用状压dp。二维数组，表示已访问过部分点并且到当前点的值是多少。在获取好所有数据后，先把dp中的所有值都设置为最大值，再把从每个开始的情况设置为0。然后开始三层循环，第一层先控制已访问过的星球，第二层控制当前星球，同时判断当前星球是否在已访问的星球中，已有则继续，定义好当前已访问的前一种情况，如果这种情况不为0，也就是不是只访问了一个星球的情况，则继续第三层循环，也和第二层循环一样要先判断前一个星球是否在前一种访问情况中，是则开始做状态转移，当前状态等于前一种状态加上题目中给出的计算能量。完成所有循环后，要选取出总和最小的情况，就要遍历所有已全部访问时的情况，最终输出最小值。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 import java.util.Scanner;public class Main { static int [] x; static int [] y; static int [] z; static int [] w; public static double dist (int k,int j) { return Math.sqrt(Math.pow(x[k]-x[j],2 )+Math.pow(y[k]-y[j],2 )+Math.pow(z[k]-z[j],2 )); } public static void main (String[] args) { Scanner scan = new Scanner (System.in); int n=scan.nextInt(); double [][] dp=new double [1 <<n][n]; x=new int [n]; y=new int [n]; z=new int [n]; w=new int [n]; for (int i=0 ;i<n;i++) { x[i]=scan.nextInt(); y[i]=scan.nextInt(); z[i]=scan.nextInt(); w[i]=scan.nextInt(); } for (int i=0 ;i<(1 <<n);i++) { for (int j=0 ;j<n;j++) { dp[i][j]=Double.MAX_VALUE; } } for (int i=0 ;i<n;i++) { dp[1 <<i][i]=0.0 ; } for (int mask=1 ;mask<(1 <<n);mask++) { for (int j=0 ;j<n;j++) { if ((mask&(1 <<j))!=0 ) { int prevmask=mask^(1 <<j); if (prevmask!=0 ) { for (int k=0 ;k<n;k++) { if ((prevmask&(1 <<k))!=0 ) { dp[mask][j]=Math.min(dp[mask][j],dp[prevmask][k]+dist(k,j)*w[j]); } } } } } } int fullmask=(1 <<n)-1 ; double ans=Double.MAX_VALUE; for (int j=0 ;j<n;j++) { ans=Math.min(ans,dp[fullmask][j]); } System.out.printf("%.2f" ,ans); scan.close(); } }
28.子2023
问题描述
小蓝在黑板上连续写下从 1 到 2023之间所有的整数，得到了一个数字序列： S=12345678910111213…20222023。 小蓝想知道 S 中有多少种子序列恰好等于 2023？
以下是 3 种满足条件的子序列（用中括号标识出的数字是子序列包含的数字）：
1[2]34567891[0]111[2]1[3]14151617181920212223…
1[2]34567891[0]111[2]131415161718192021222[3]…
1[2]34567891[0]111213141516171819[2]021222[3]…
注意以下是不满足条件的子序列，虽然包含了 2、0、2、3 四个数字，但是顺序不对：
1[2]345678910111[2]131415161718192[0]21222[3]…
题解
常规思路是将所有的2，0，3都找出来并存在数组中，在数组中做四层循环，但是显然超时。所以用dp来做，一共就四种情况，2，20，202，2023，最终输出2023的个数
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 import java.util.Arrays;import java.util.Scanner;public class Main { public static void main (String[] args) { StringBuilder string=new StringBuilder (); Long []dp=new Long [4 ]; Arrays.fill(dp, 0L ); for (int i=1 ;i<=2023 ;i++) { string.append(i); } for (int i=0 ;i<string.length();i++) { if (string.charAt(i)=='2' ) { dp[0 ]++; dp[2 ]+=dp[1 ]; } if (string.charAt(i)=='0' ) { dp[1 ]+=dp[0 ]; } if (string.charAt(i)=='3' ) { dp[3 ]+=dp[2 ]; } } System.out.println(dp[3 ]); } }
29.数字诗意
问题描述 在诗人的眼中，数字是生活的韵律，也是诗意的表达。
小蓝，当代顶级诗人与数学家，被赋予了"数学诗人"的美誉。他擅长将冰冷的数字与抽象的诗意相融合，并用优雅的文字将数学之美展现于纸上。
某日，小蓝静坐书桌前，目光所及，展现着 n 个数字，它们依次为 a 1 , a 2 , … , a n a_1,a_2,…,a_n a 1 , a 2 , … , a n
小蓝希望他面前的所有数字都蕴含诗意，为此，他决定从这 n 个数字中删除一部分。请问，小蓝需要删除多少个数字，才能使剩下的数字全部蕴含诗意？
输入格式 第一行包含一个整数 n，表示展示的数字个数。
第二行包含 n 个整数 a 1 , a 2 , … , a n a_1,a_2,…,a_n a 1 , a 2 , … , a n
输出格式 输出一个整数，表示小蓝需要删除的数字个数，以使剩下的数字全部蕴含诗意。
样例输入 样例输出 样例说明 在样例中，数字 3 可以表示为 1+2，数字 6 可以表示为 1+2+3，数字 8 无法表示为连续的正整数相加，因此，需要删除的数字个数为 1。
题解
纯数学题，找规律，对于奇数来说必然有两个连续的数相加可得，对于偶数来说，如果这个偶数被2除后的奇数那么同样是可以通过连续数字相加获得的，但是如果不是奇数，也就是2的幂次方是不可以的
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner scan=new Scanner (System.in); int n=scan.nextInt(); int ans=0 ; for (int i=1 ;i<=n;i++) { Long j=scan.nextLong(); while (j%2 ==0 &&j>1 ) { j/=2 ; } if (j==1 ) { ans++; } } System.out.println(ans); } }
30.接龙数列
问题描述
对于一个长度为 K 的整数数列：A 1 , A 2 , … , A K A_1,A_2,…,A_K A 1 , A 2 , … , A K A i A_i A i A i − 1 A_{i−1} A i − 1
现在给定一个长度为 N 的数列 A 1 , A 2 , … , A N A_1,A_2,…,A_N A 1 , A 2 , … , A N
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A 1 , A 2 , … , A N A_1,A_2,…,A_N A 1 , A 2 , … , A N
输出格式
一个整数代表答案。
样例输入
样例输出
样例说明
删除 22，剩余 11,121,12,2023 是接龙数列。
题解
还是用dp，一共就只有十种数字结尾的数列，所有以head结尾的最优链都可以无损地接上它，形成一条以tail结尾、长度为dp[head]+1的新链
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner sc=new Scanner (System.in); int []dp=new int [10 ]; int n=sc.nextInt(); String []s=new String [n]; for (int i=0 ;i<n;i++) { s[i]=sc.next(); } for (int i=0 ;i<n;i++) { int head=s[i].charAt(0 )-'0' ; int tail=s[i].charAt(s[i].length()-1 )-'0' ; dp[tail]=Math.max(dp[head]+1 ,dp[tail]); } int max=0 ; for (int i=0 ;i<10 ;i++) { max=Math.max(max,dp[i]); } System.out.println(n-max); } }
31.切割
问题描述
给定一个 W×H的长方形，两边长度均为整数。小蓝想把它切割为很多个边长为整数的小正方形。假设切割没有任何损耗，正方形的边长至少为 2，不允许出现余料，要求所有正方形的大小相等，请问最多能切割出多少个?
输入格式
输入一行，包含两个整数 W, H，用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。如果不存在满足要求的方案，输出 0。
样例输入1
样例输出1
样例说明
切割成 5×10=50个边长为 2 的正方形。
样例输入2
样例输出2
样例输入3
样例输出3
题解
这道题实际上求的是是否有最大公约数，直接用辗转相除法。然后去遍历自然数，如果最大公约数能被整除，就用这个除数作为边长。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner scan = new Scanner (System.in); int w=scan.nextInt(); int h=scan.nextInt(); int d=gcd(w,h); if (d==1 ) { System.out.println(0 ); return ; } long ans=0 ; for (int i=2 ;i<=d;i++) { if (d%i==0 ) { ans=((long )w/i)*(h/i); break ; } } System.out.println(ans); } static int gcd (int a,int b) { if (b==0 ) { return a; } return gcd(b,a%b); } }
32.砍柴
问题描述
小蓝和小乔正在森林里砍柴，它们有 T 根长度分别为 n 1 , n 2 , ⋯ , n T n_1,n_2,⋯,n_T n 1 , n 2 , ⋯ , n T
每次砍柴时，若当前木头长度为 x，需要砍下一截长度为 p 的木头，然后换另一个人继续砍，其中 2≤p≤x且 p 必须为质数。当轮到某一方时 x=1或 x=0，它就没法继续砍柴，它就输了。它们会使用最优策略进行砍柴。请对每根木头判断是小蓝赢还是小乔赢，如果小蓝赢请输出 1（数字 1），如果小乔赢请输出 0（数字 0）。
输入格式
输入的第一行包含一个正整数 T ,
接下来 T 行，每行包含一个正整数，其中第 i 的整数为 n i n_i n i
输出格式
输出 T 行，每行包含一个整数，依次表示对于每一根木头的答案。
样例输入
样例输出
样例说明
对于 n 1 = 1 n_1=1 n 1 = 1
对于 n 2 = 2 n_2=2 n 2 = 2
对于 n 3 = 6 n_3=6 n 3 = 6
题解
博弈论中的必胜态和必败态，0，1都是先手必败态。首先先打表找出质数，然后用dp，如果一个数减去一个质数能变成先手必败态，那么就是先手必胜态，把所有的dp都求出后，把输入的数在dp中对照即可
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner sc=new Scanner (System.in); List<Integer> a=new ArrayList <>(); for (int i = 2 ; i <=100000 ; i++) { boolean isright=true ; for (int j = 2 ; j*j <=i; j++) { if (i%j==0 ) { isright =false ; break ; } } if (isright) { a.add(i); } } int dp[]=new int [100001 ]; dp[2 ]=1 ; for (int i = 2 ; i <=100000 ; i++) { for (int j = 0 ; j < a.size(); j++) { int x=i-a.get(j); if (x<0 ) { break ; } if (dp[x]==0 ) { dp[i]=1 ; break ; } } } int T=sc.nextInt(); int []trr=new int [T]; for (int i = 0 ; i < T; i++) { int t=sc.nextInt(); trr[i]=dp[t]==1 ?1 :0 ; } for (int i = 0 ; i < T; i++) { System.out.println(trr[i]); } } }
33.二进制问题
题目描述
小蓝最近在学习二进制。他想知道 1 到 N中有多少个数满足其二进制表示中恰好有 K 个 1。你能帮助他吗？
输入描述
输入一行包含两个整数 N 和 K。
输出描述
输出一个整数表示答案。
输入输出样例
示例
输入
输出
题解
二进制数位dp。首先把输入的数拆成二进制数，再对组合数进行一个预处理，C(n,k) = C(n-1,k) + C(n-1,k-1)。在遍历每一位数位的时候有两种情况，如果是0，那么只能放0，否则就会超过输入的数字，如果是1，那么可以放1，也就是和原数字一样，或者可以放0，那么后面的数字可以随意放也不会超过输入的数字。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 import java.util.*;public class Main { public static void main (String[] args) { Scanner sc = new Scanner (System.in); long N = sc.nextLong(); int K = sc.nextInt(); ArrayList<Integer> bits = new ArrayList <>(); long x = N; while (x > 0 ) { bits.add((int )(x & 1 )); x >>= 1 ; } Collections.reverse(bits); int L = bits.size(); long [][] C = new long [L + 1 ][L + 1 ]; for (int i = 0 ; i <= L; i++) { C[i][0 ] = 1 ; C[i][i] = 1 ; for (int j = 1 ; j < i; j++) { C[i][j] = C[i - 1 ][j] + C[i - 1 ][j - 1 ]; } } long ans = 0 ; int used = 0 ; for (int i = 0 ; i < L; i++) { int bit = bits.get(i); int rest = L - i - 1 ; if (bit == 1 ) { int need = K - used; if (0 <= need && need <= rest) { ans += C[rest][need]; } used++; if (used > K) break ; } } if (used == K) ans++; if (K == 0 ) ans -= 1 ; System.out.println(ans); sc.close(); } }
34.缴纳过路费
问题描述 在繁华的商业王国中，N 座城市被 M 条商路巧妙地连接在一起，形成了一个错综复杂的无向图网络。每条商路是双向通行的，并且任意两座城市之间最多只有一条直接的商路。每条商路都有它的规则，其中最引人注目的就是穿过商路，需要缴纳过路费。因此，商人们在选择商路时必须格外认真。
有一位名叫小蓝的商人，他对于商路的花费有着自己独到的见解。在小蓝眼中，一条路线包含一条或多条商路，但路线的成本并不是沿途累积的过路费总和，而是这条路线上最贵的那一次收费。这个标准简单而直接，让他能迅速评估出一条路线是否划算。
于是，他设立了一个目标，即找出所有城市对，这些城市之间的最低路线成本介于他心中预设的两个数 L 和 R 之间。他相信，这样的路线既不会太廉价，以至于路况糟糕；也不会过于昂贵，伤害他精打细算的荷包。
作为小蓝的助手，请你帮助小蓝统计出所有满足条件的城市对数量。
输入格式 第一行包含四个整数 N,M,L,R，表示有 N 座城市和 MM 条双向通行的商路，以及小蓝心中预设的最高过路费的下限 L 和上限 R。
接下来 M 行，每行包含三个整数 u,v,w，表示城市 u 和城市 v 之间有一条双向通行的商路，过路费为 w。保证每对城市之间最多只有一条直接的商路。
输出格式 输出仅一行，包含一个整数，表示满足条件的城市对数量。
样例输入 1 2 3 4 5 6 5 5 1 2 1 2 2 1 3 5 1 4 1 2 4 5 2 5 4
样例输出 样例说明 在样例中，满足条件的城市对有 (1,2)，(1,4)，(2,4)。
题解
这道题涉及到的是并查集，但是需要两个，一个用来存小于等于R的，另一个用来存小于L的，求出两个并查集中的城市个数并对其求组合数，再相减
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 import java.util.*;public class Main { public static int [] arr,arr2; public static void init (int size) { arr = new int [size]; arr2 = new int [size]; for (int i = 0 ;i<size;i++) { arr[i] = i; arr2[i] = i; } } public static int find (int [] arr,int x) { return arr[x] == x ? x : (arr[x] = find(arr,arr[x])); } public static void union (int [] arr,int a,int b) { arr[find(arr,a)] = find(arr,b); } public static void main (String[] args) { Scanner sc = new Scanner (System.in); int N = sc.nextInt(); int M = sc.nextInt(); int L = sc.nextInt(); int R = sc.nextInt(); long result = 0 ; init(N+1 ); for (int i = 0 ;i<M;i++) { int u = sc.nextInt(); int v = sc.nextInt(); int w = sc.nextInt(); if (w<=R) { union(arr,u, v); } if (w <L) { union(arr2,u,v); } } int [] cnt = new int [N+1 ]; int [] cnt2= new int [N+1 ]; for (int i = 1 ;i<=N;i++) { cnt[find(arr,i)]++; cnt2[find(arr2,i)]++; } for (int i = 1 ;i<=N;i++) { if (find(arr, i) == i) { result+= cal(cnt[find(arr, i)]); } if (find(arr2, i) == i) { result-= cal(cnt2[find(arr2, i)]); } } System.out.println(result); sc.close(); } public static long cal (long x) { return x*(x-1 )/2 ; } }
35.第K小的和
问题描述
给定两个序列 A,B，长度分别为 n,m。
设另有一个序列 C 中包含了 A,B 中的数两两相加的结果 (C 中共有 n×m 个数)。问 C 中第 K 小的数是多少。请注意重复的数需要计算多次。例如 1,1,2,3 中，最小和次小都是 1，而 3 是第 4 小。
输入格式
输入的第一行包含三个整数 n,m,K，相邻两个整数之间使用一个空格分隔。
第二行包含 n 个整数，分别表示 A 1 , A 2 , … , A n A_1,A_2,…,A_n A 1 , A 2 , … , A n
第三行包含 m 个整数，分别表示 B 1 , B 2 , … , B m B_1,B_2,…,B_m B 1 , B 2 , … , B m
输出格式
输出一行包含一个整数表示答案。
样例输入
样例输出
题解
这道题的直觉是循环得到完整的C，但是测试用例规模过大不可能枚举出来再排序。但A和B是可以排序的，并且排序后就可以知道C的最大值和最小值，这时候就可以用二分法来求K位置的元素。所以需要一个函数可以求出相加和比一个值小的个数，把中间值传入到这个函数并在二分法中调用。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 import java.util.*;public class Main { public static long sum_count (long [] A,long [] B,long x) { long count=0 ; int j=B.length-1 ; for (int i=0 ;i<A.length;i++) { while (j>=0 &&A[i]+B[j]>x) { j--; } count=count+j+1 ; } return count; } public static void main (String[] args) { Scanner scan = new Scanner (System.in); int n=scan.nextInt(); int m=scan.nextInt(); long K=scan.nextLong(); long [] A=new long [n]; long [] B=new long [m]; for (int i=0 ;i<n;i++) { A[i]=scan.nextLong(); } for (int i=0 ;i<m;i++) { B[i]=scan.nextLong(); } Arrays.sort(A); Arrays.sort(B); long left=A[0 ]+B[0 ]; long right=A[n-1 ]+B[m-1 ]; while (left<right) { long mid=(left+right)/2 ; long count=sum_count(A,B,mid); if (count>=K) { right=mid; } else { left=mid+1 ; } } System.out.print(left); scan.close(); } }
36.异或和之和
题目描述
给定一个数组 A i A_i A i
输入格式
输入的第一行包含一个整数 n。
第二行包含 n 个整数 A i A_i A i
输出格式
输出一行包含一个整数表示答案。
样例输入
样例输出
题解
这里求的是每个子段的异或和，异或和指区间内元素按位异或的结果，就是要求出每个子段的异或再相加，可以直接暴力，每次求出一段的异或后，下一次异或只要将前一次异或的结果和当前多出来的数异或就可以得到当前子段的异或，中间要用sum ^= a[j]这种滚动写法来降一层复杂度，不然应该会超时的
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner sc = new Scanner (System.in); int n = sc.nextInt(); int []a = new int [n]; for (int i = 0 ; i < n; i++) { a[i] = sc.nextInt(); } long result = 0 ; for (int i = 0 ; i < n; i++) { long sum = 0 ; for (int j = i; j < n; j++) { sum ^= a[j]; result+=sum; } } System.out.println(result); } }
37.互质数的个数
问题描述
给定 a，b，求 1≤x<a b a^b a b a b a^b a b
输入格式
输入一行包含两个整数分别表示 a，b，用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
样例输入 1
样例输出 1
样例输入 2
样例输出 2
题解
这道题显然不能暴力，需要用快速幂和欧拉函数，非常抽象。快速幂通过将指数分解为二进制来快速计算大数幂，每次右移一位。欧拉函数则用来计算与小于某数并与其互质的数的个数，ϕ ( n ) = n × ( 1 − 1 p 1 ) × ( 1 − 1 p 2 ) × ⋯ × ( 1 − 1 p k ) ϕ(n)=n×(1-\frac1{p_1})×(1−\frac1{p_2})×⋯×(1−\frac1{p_k}) ϕ ( n ) = n × ( 1 − p 1 1 ) × ( 1 − p 2 1 ) × ⋯ × ( 1 − p k 1 )
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 import java.util.Scanner;public class Main { static int mod = 998244353 ; static long qmi (long a,long b) { long res = 1 ; while (b>0 ) { if ((b&1 )>0 ) { res = (res*a)%mod; } a = (a*a)%mod; b>>=1 ; } return res; } public static void main (String[] args) { Scanner scan = new Scanner (System.in); int a=scan.nextInt(); long b=scan.nextLong(); long res = a; long temp = a; for (int i=2 ;i<=temp/i;i++) { if (temp%i==0 ) { res = res/i*(i-1 ); while (temp%i==0 ) { temp/=i; } } } if (temp>1 ) { res = res/temp*(temp-1 ); } long t = qmi(a,b-1 ); res = (res*t)%mod; System.out.println(res); } }
38.因数平方和
问题描述
记 f(x) 为 x 的所有因数的平方的和。例如: f ( 12 ) = 1 2 + 2 2 + 3 2 + 4 2 + 6 2 + 12 2 f(12)=1^2+2^2+3^2+4^2+6^2+ 12^2 f ( 12 ) = 1 2 + 2 2 + 3 2 + 4 2 + 6 2 + 1 2 2
定义 g ( n ) = ∑ i = 1 n f ( i ) g(n)=\sum_{i=1}^nf(i) g ( n ) = ∑ i = 1 n f ( i ) 10 9 + 7 10^9+7 1 0 9 + 7
输入格式
输入一行包含一个正整数 n 。
输出格式
输出一个整数表示答案 g(n) 除以 10 9 + 7 10^9+7 1 0 9 + 7
样例输入
样例输出
题解
直接枚举是一定会超时的，所以用逆向思维，不求每个数的因数相加，求每个因数出现多少次，出现次数为n/2向下取整，再用数论分块和平方和公式求得g
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 import java.util.Scanner;public class Main { static final int MOD = 1000000007 ; static final long INV6 = 166666668 ; public static long squareSum (long factor) { return ((factor * (factor + 1 ) % MOD) * ((2 * factor + 1 ) % MOD) % MOD * INV6 % MOD); } public static void main (String[] args) { Scanner scan = new Scanner (System.in); int n = scan.nextInt(); long anwser = 0L ; long right; for (long left = 1L ; left <= n; left = right + 1 ) { right = n / (n / left); anwser += (squareSum(right) - squareSum(left - 1 )) * (n / left) % MOD; anwser = (anwser + MOD) % MOD; } scan.close(); System.out.println(anwser); } }
