蓝桥杯
今日学习🛒
🤩1、年龄巧合
😊2、纸牌三角形
😉3、取球游戏🍭 本篇是博主补更的一篇题解，题目难度适中，可操作性强
🤩1、年龄巧合
🎯题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小明和他的表弟一起去看电影，有人问他们的年龄。小明说：今年是我们的幸运年啊。我出生年份的四位数字加起来刚好是我的年龄。表弟的也是如此。已知今年是 2014 年，并且，小明说的年龄指的是周岁。
请推断并填写出小明的出生年份。
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
package day_day_work2;
/**
* @author yx
* @date 2022-03-16 20:27
*/
public class 年龄巧合 {
public static void main(String[] args) {
for (int i = 2014; i >1950 ; i--) {
if ((2014-i)==(i%10+(i/10)%10+(i/100)%10+(i/1000)%10))
System.out.println(i);
}
}
}
💖题解分析：
💦（1）首先我们先尝试着确定区间，这个人出生的时间大概是在（1950，2014）年区 间内，然后先尝试跑一跑代码
💦（2）跑出来结果有2006，1988两个
💦（3）注意看题，因为表弟和“我”同时满足条件，所以2006是表弟的出生时间，而“我”则是1988
😊2、纸牌三角形
🎯题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
A,2,3,4,5,6,7,8,9共 9 张纸牌排成一个正三角形（A 按 1 计算）。要求每个边的和相等。 下图就是一种排法。
这样的排法可能会有很多。
如果考虑旋转、镜像（对称）后相同的算同一种，一共有多少种不同的排法呢？
请你计算并提交该数字。
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
package Day_Day_work;
/**
* @author yx
* @date 2022-03-10 11:10
*/
//dfs问题
public class 纸牌三角形 {
static int ans=0;
static int[]A=new int[9];//这个是用来存数据的
static int[]B=new int[9];//这个是用来表示该数组的位置是否有被遍历过
public static void main(String[] args) {
dfs(0);
/**
* 因为旋转和镜像代表的是同一种，但是它们各重复三次，即重复六次，所以最后要除以六
*/
System.out.println(ans / 6);
}
public static void dfs(int num) {//dfs写的非常巧妙
if(num==9&&((A[0]+A[1]+A[2]+A[3])==(A[3]+A[4]+A[5]+A[6]))&&((A[3]+A[4]+A[5]+A[6])==(A[6]+A[7]+A[8]+A[0]))){
ans++;
return ;//dfs出口
}
for(int i=0;i<9;i++){
if(B[i]==0){
A[num]=i+1;//对数组进行赋值
B[i]=1;//表示该位置已经赋值
dfs(num+1);
B[i]=0;//回溯
}
}
}
}
💖题解分析：
💦（1）该题主要用到（dfs+全排列）的思想
（关于dfs博主有一篇里面有两道经典的dfs算法题）
💦（2）关于dfs，博主提一句，三个要素非常重要：
1.入口参数设置
2.dfs的出口设置
3.是否需要回溯
😉3、取球游戏
🎯题目描述
今盒子里有 n个小球，A、B 两人轮流从盒中取球，每个人都可以看到另一个人取了多少个，也可以看到盒中还剩下多少个，并且两人都很聪明，不会做出错误的判断。
我们约定：
每个人从盒子中取出的球的数目必须是：1，3，7 或者 8 个。轮到某一方取球时不能弃权！A 先取球，然后双方交替取球，直到取完。被迫拿到最后一个球的一方为负方（输方）
请编程确定出在双方都不判断失误的情况下，对于特定的初始球数，A 是否能赢？
输入描述
先是一个整数 n (n<100)，表示接下来有 n 个整数。
然后是 n个整数，每个占一行（整数< 10^4），表示初始球数。
输出描述
程序则输出 n 行，表示 A 的输赢情况（输为 0，赢为 1）。
输入输出样例
示例
输入
４ １ ２ 10 18输出
0 1 1 0运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
🎪暴力解法
package Day_Day_work;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* @author yx
* @date 2022-03-10 19:59
*/
//有点类似于爬楼梯的递归模式
public class 取球游戏__暴力解法 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Integer> l = new ArrayList<>();
for (int i = 0; i < n; i++) {
l.add(scanner.nextInt());
}
for (int j = 0; j < n; j++) {
if(A(l.get(j))){
System.out.println(1);
}
else {
System.out.println(0);
}
}
}
public static boolean A(int m) {
if (m >= 1) {
switch (m) {
case 1:
return false;//当你要去拿球时，并且最后只剩下1个球时，输
case 3:
return false;//当你要去拿球时，并且最后只剩下3个球时，输
case 7:
return false;//输
case 8:
return true;//赢
default:return (!A(m-1)||!A(m-3)||!A(m-7)||!A(m-8));//这个时候表示自己拿1或3或7或8个球，然后这时对象变成了对面的一个人，所以要加！
}
}
return false;
}
}
💖题解分析：
💦暴力枚举解法，虽然很容易想到，但是会直接炸（仔细看，我们会发现，每一次遍历，会重复很多次冗余，从而导致超时），所以我们暂时先不考虑，但是也可以参考一下，体会一下它的思路，顺便也避免下次自己踩坑！
🎪dp解法
package Day_Day_work;
import java.util.Scanner;
/**
* @author yx
* @date 2022-03-10 20:25
*/
//dp解法
public class 取球游戏__动态规划 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
boolean[] A = new boolean[10009];//因为n<10^4
A[0] = true;
for (int i = 1; i < 10009; i++) {
A[i] = (!(A[i - 1]) || (i >= 3 && !A[i - 3]) || (i >= 7 && !A[i - 7]) || (i >= 8 && !A[i - 8]));//这个时候表示自己拿1或3或7或8个球，然后这时对象变成了对面的一个人，所以要加！
}
//为了方便输出
int[]B=new int[n+1];
for (int i = 1; i <= n; i++) {
int j = scanner.nextInt();
if(!A[j]){
B[i]=0;
}
else {
B[i]=1;
}
}
for (int k=1;k<=n;k++){
System.out.println(B[k]);
}
}
}
💖题解分析：
💦这个题目有点像走楼梯的题目，“我”最开始取球，对应有四种取法，取完球之后就是对方取球，如果对方赢了，那反之我们不就是输了吗（所以我们取完球之后要加一个“！”），但是我们用“||”来选择四种取法，表示只要有一种取法能够赢，那我们最后就是赢的
💦每一种取法取的一定是最优值，就比如说有4个球，取法有：
1，1，1，1（我输）
3、1（我赢）
那么四个球的取法结果就是我赢
💦注意看，我们每次遍历的时候，数组都会将对应的结果给记录下来，这样跟暴力枚举解法比起来，就省去了大量的冗余计算过程
💖写在最后
每日一题，我们一直在路上！
送给大家一句话：
“当你真的拼尽全力去做一件事情的时候，结果已经变得不那么重要了”
- 点赞
- 收藏
- 关注作者
评论（0）