题目一
题目描述
年龄巧合
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小明和他的表弟一起去看电影，有人问他们的年龄。小明说：今年是我们的幸运年啊。我出生年份的四位数字加起来刚好是我的年龄。表弟的也是如此。已知今年是 2014 年，并且，小明说的年龄指的是周岁。
请推断并填写出小明的出生年份。
运行限制
最大运行时间：1s
最大运行内存: 128M
题解
public class Main { 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); } } }
注：确定区间（1950，2014），结果为2006，1988，他是我表弟，故为2006年出生
答案： 我 ：1988 他 ：2006
题目二
题目描述
纸牌三角形
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
A,2,3,4,5,6,7,8,9共 9 张纸牌排成一个正三角形（A 按 1 计算）。要求每个边的和相等。 下图就是一种排法。
这样的排法可能会有很多。
如果考虑旋转、镜像（对称）后相同的算同一种，一共有多少种不同的排法呢？
请你计算并提交该数字。
运行限制
最大运行时间：1s
最大运行内存: 256M
题解
public class Main { 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) { 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; } for (int i = 0; i < 9; i++) { if (B[i] == 0) { A[num] = i + 1;// 对数组进行赋值 B[i] = 1;// 表示该位置已经赋值 dfs(num + 1); B[i] = 0;// 回溯 } } } }
注：dfs搜索，全排列，抓住三个要素最为关键
入口的参数设置
dfs的出口设置
是否需要回溯
答案：144
题目三
题目描述
取球游戏
今盒子里有 n个小球，A、B 两人轮流从盒中取球，每个人都可以看到另一个人取了多少个，也可以看到盒中还剩下多少个，并且两人都很聪明，不会做出错误的判断。
我们约定：
每个人从盒子中取出的球的数目必须是：1，3，7 或者 8 个。轮到某一方取球时不能弃权！A 先取球，然后双方交替取球，直到取完。被迫拿到最后一个球的一方为负方（输方）
请编程确定出在双方都不判断失误的情况下，对于特定的初始球数，A 是否能赢？
输入描述
先是一个整数 n (n<100)，表示接下来有 n 个整数。
然后是 n个整数，每个占一行（整数< 10^4），表示初始球数。
输出描述
程序则输出 n 行，表示 A 的输赢情况（输为 0，赢为 1）。
输入样例
4 1 2 10 18
输出样例
0 1 1 0
运行限制
最大运行时间：1s
最大运行内存: 256M
题解
(暴力求解)
import java.util.ArrayList; import java.util.List; import java.util.Scanner; //类似于爬楼梯的递归模式 public class Main { 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求解）
import java.util.Scanner; //dp解法 public class Main { 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]); } } }
暴力求解：代码冗余，重复率较高，显得笨重且繁琐
dp求解：结果只有两种 ，他赢或我赢，是非的关系，用“||”来选择四种取法，表示只要有一种取法能够赢，那我最后就是赢的，取法都是最优值。
eg:4个球
1，1，1，1（我输了）
3，1（我赢了）
遍历计算结果，进行累计
