单选题6个，每题2分，各个类型都有，比较简单。
多选题6个，每题4分，少选给1/3分，也不难，就是有的会比较纠结
编程题三道，一道easy，一道medium，一道hard。
第一题简单字符串模拟（14分），问密码情况，满足三个条件：
比较坑的点在于输出这些英文容易输错（可以cv），ACM模式下很多人不会正确的输入输出导致只有80%正确率，比如int后需要接受空格，字符串可能存在空格的情况。
关于java在ACM中的输入输出可以看我的这篇文章
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
String next = sc.nextLine();
HashSet<String> set = new HashSet<>();
for (int i = 0; i < t; i++) {
String str = sc.nextLine();
if (str.length() < 5 || str.length() > 12) System.out.println("字符串长度不合法");
else if (!isLetter(str)) System.out.println("非全英文字符串");
else if (set.contains(str)) System.out.println("字符串存储过了");
else {
set.add(str);
System.out.println("合法字符串");
}
}
}
private static boolean isLetter(String str) {
for (int i = 0; i < str.length(); i++) {
if (!Character.isLetter(str.charAt(i))) return false;
}
return true;
}
} 第二题（20分），没做出来，自己太菜了，做题也少。这道题看着挺简单的，然后0%通过就懵了，时间都花在第二题了，导致第三题没时间做。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int i = 0; i < t; i++) {
int[] nums = new int[5];
for (int j = 0; j < 5; j++) {
nums[j] = sc.nextInt();
}
Arrays.sort(nums);
// System.out.println(min1 + "\t" + min2 + "\t" + min3);
int res = 0;
if (nums[1] == nums[2]) {
res = nums[1];
} else {
res = nums[1] + Math.min(nums[0], nums[2] - nums[1]);
}
System.out.println(res);
}
} 0分，没想通。 第三题（30分）背包问题，参考大佬的题解，发现确实是01背包问题，不过贪心也可以过一些案例。
思路是只要斜率k=-a/b不一样，那么两条直线必相交。用一个map存储斜率和对应的条数，比如[1-2],[2-3],[3-4]，那么就和力扣416. 分割等和子集，494. 目标和，1049. 最后一块石头的重量 II这几道题一样了。
只有两个颜色，所以将对应的条数分为两堆，一堆为x（白色），一堆为y（黑色），题目要求xy最大，当且仅当x==y时最大，但是背包问题不一定满足两堆个数一样，所以最后结果就是x(sum-x)。
不得不说背包用来求子集划分问题还是很好用的。
这题我暴力就过了10%的案列，第二题懵了，第三题没时间看。class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); //key-斜率，value-个数 HashMap<Double, Integer> map = new HashMap<>(); for (int i = 0; i < t; i++) { int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();//c没用 double k = 1.0 * a / b;//用double，int会把1.1和1.9斜率算成一样 map.put(k, map.getOrDefault(k, 0) + 1); } int sum = 0, n = map.size(); int[] weight = new int[n], values = new int[n]; int index = 0; for (Map.Entry<Double, Integer> entry : map.entrySet()) { sum += entry.getValue(); weight[index] = entry.getValue(); values[index] = entry.getValue(); } int w = sum / 2; //dp[n][w]:针对所有的条数，不超过一半和的最大和，比如[1,3,3],凑不超过3的最大和，就是[3]了，所以一堆是3，一堆是4，结果12. //dp[i][j]:前i个物品，第i个物品的重量是weight[i],价值是value[i],背包容量是j，求最大价值。 int[][] dp = new int[n + 1][w + 1]; //base case //dp[0][...]=0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= w; j++) { if (j >= weight[i - 1]) {//能够装下第i个物品 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + values[i - 1]); } else { dp[i][j] = dp[i - 1][j];//装不下第i个物品 } } } System.out.println(dp[n][w] * (sum - dp[n][w]));//一堆和是x，一堆和是y } }
总结下来就是，时间没分配到位，选择题还检查了一遍（我也服了），以为最后一道题肯定hard所以就放弃了，但是这个确实还是比较接近leetcode原题的，给时间想想应该能想到，或者过多一些case，当然最主要还是太菜了。
全部评论
(11) 回帖