3.19美团笔试代码记录
当时只a了两道，太菜了。下来自己把题目全写了一遍，在此记录分享。
第一题
点外卖用折扣价还是用满减，直接模拟就行。唯一的坑是满减只能用最接近的券，比如商品总原价100，我有满100减10的券和满50-30的券，则只能用前者。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long[] originPrice = new long[n];
long[] discountPrice = new long[n];
long sum = 0;
for(int i = 0; i < n; ++i) {
sum += in.nextInt();
originPrice[i] = sum;// 前i件商品原始价
}
sum = 0;
for(int i = 0; i < n; ++i) {
sum += in.nextInt();
discountPrice[i] = sum;
}
int m = in.nextInt();
int[] c = new int[m];
int[] d = new int[m];
for(int i = 0; i < m; ++i){
c[i] = in.nextInt();
}
for(int i = 0; i < m; ++i) {
d[i] = in.nextInt();
}
String res = "";
for(int i = 0; i < n; ++i) { // n件商品
long curManPrice = originPrice[i];
for(int j = 0; j < m; ++j) {
if(originPrice[i] >= c[j]) {
curManPrice = Math.min(curManPrice, originPrice[i] - d[j]);
}
else {
break;
}
}
if(curManPrice > discountPrice[i]) {
res += "Z";
}
else if(curManPrice < discountPrice[i]) {
res += "M";
}
else {
res += "B";
}
}
System.out.println(res);
}
}
第二题
加解密，直接模拟就行。这里可不自己用StringBuilder，因为字符串的加操作会自动优化为StringBuilder。
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int t = in.nextInt();
String str = in.next();
//System.out.println(str);
ArrayList<Character> list = new ArrayList<>();
for(char c : str.toCharArray()) {
list.add(c);
}
String res = "";
if(t == 2) { // 解密
while(list.size() > 0) {
char c = list.remove(list.size()-1);
int pos = res.length() / 2;
String s1 = res.substring(0,pos);
String s2 = res.substring(pos);
res = s1 + c + s2;
}
}
if(t == 1) { // 加密
while(list.size() > 0) {
int pos = list.size() % 2 == 0 ? list.size()/2-1 : (list.size()/2);
res += list.remove(pos);
}
}
System.out.println(res);
} 第三题
区间覆盖，双重循环，判断任意两个区间有无交集即可。注意，一台机器上本身的区间之间可能有重合，可以先进行区间合并，也可以直接用set记录。
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m1 = in.nextInt();
int m2 = in.nextInt();
int[][] intervals1 = new int[m1][2];
for(int i = 0; i < m1; ++i) {
intervals1[i][0] = in.nextInt();
}
for(int i = 0; i < m1; ++i) {
intervals1[i][1] = in.nextInt();
}
int[][] intervals2 = new int[m2][2];
for(int i = 0; i < m2; ++i) {
intervals2[i][0] = in.nextInt();
}
for(int i = 0; i < m2; ++i) {
intervals2[i][1] = in.nextInt();
}
Arrays.sort(intervals1, (v1, v2) -> (v1[0] - v2[0])); // 按区间左端点排序
Arrays.sort(intervals2, (v1, v2) -> (v1[0] - v2[0]));
Set<Integer> set = new HashSet<>(); // 去重
for(int i = 0; i < m1; ++i) {
for(int j = 0; j < m2; ++j) {
if(intervals1[i][0] > intervals2[j][1] || intervals1[i][1] < intervals2[j][0]) { // 没有交集
continue;
}
// 有交集：找交集的左右端点
int left = Math.max(intervals1[i][0], intervals2[j][0]);
int right = Math.min(intervals1[i][1], intervals2[j][1]);
for(int k = left; k <= right; ++k) {
set.add(k);
}
}
}
System.out.println(set.size());
}
} 第四题
给定n个元素的集合，从集合中选k个元素求和，使其和能被k1整除，不能被k2整除。（1 <= k <= n） 参考力扣78. 子集，直接回溯遍历所有可能的和，再依次判断。不能全a，但能快速拿一些分支的分。
import java.util.Scanner;
//5 3 4
//6 8 -2 -5 2
//输出：9 2 表示6、8、-5
public class Main {
private static int maxSum = 0;
private static int maxSumPlans = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(); // 5个数
int k1 = in.nextInt();
int k2 = in.nextInt();
int[] nums = new int[n];
for(int i = 0; i < n; ++i) {
nums[i] = in.nextInt();
}
// 输出总和与方案数
dfs(nums, 0, 0, k1, k2);
System.out.println(maxSum + " " + maxSumPlans);
}
private static void dfs(int[] nums, int curSum, int begin, int k1, int k2) {
for(int i = begin; i < nums.length; ++i) {
curSum += nums[i] % 998244353;
if(curSum % k1 == 0 && curSum % k2 != 0) { // 可被k1整除而不能被k2整除
if(curSum > maxSum) {
maxSum = curSum;
maxSumPlans = 1;
}
else if(curSum == maxSum) {
maxSumPlans++;
}
}
dfs(nums, curSum, i+1, k1, k2);
curSum -= nums[i];
}
}
} 第五题
当时没时间写了，把题目抄了下来，然后发现这道题甚至是5道里最简单的一题。。。直接模拟。不能全a，但能拿一大半分支的分。
对于一个序列A，我们定义序列(A+1)为将序列A里每个元素值都加1得到的序列。 例如：[3, 4, 2]+1=[4, 5, 3]，[1, 2, 1]+1=[2, 3, 2]。 对于序列A和B，我们定义序列C=A*B表示序列C是由序列A和序列B拼接而成（序列A在前，序列B在后）。 例如：[2, 3, 1]*[1, 2, 1]=[2, 3, 1, 1, 2, 1]； [1, 2, 3]*[2, 3]*[5, 4]=[1, 2, 3, 2, 3]*[5, 4]=[1, 2, 3, 2, 3, 5, 4]。 小团得到了一个魔法盒子。 将序列A放入魔法盒子内，将会弹出序列(A+1)*A*(A+2)。 小团先将仅由一个数0构成的序列[0]放入魔法盒子，然后不断将魔法盒子弹出的序列再次放入。现在小团想问，他这样操作第n次时魔法盒子弹出序列中第k个位置的值是多少？ 例如：一开始的序列为[0]，第1次放入后弹出的结果是[1, 0, 2]，第2次是[2, 1, 3, 1, 0, 2, 3, 2, 4]，第3次是[3, 2, 4, 2, 1, 3, 4, 3, 5, 2, 1, 3, 1, 0, 2, 3, 2, 4, 4, 3, 5, 3, 2, 4, 5, 4, 6]。 一行两个空格隔开的整数n，k，表示初始序列为[0]，小团想知道第n次弹出的序列的第k个数是多少。 输入：n k 数据保证 ：1<=n<=35, 1<=k<=3^n 输出：一个整数，表示第n次弹出的序列的第k个数。
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
ArrayList<Integer> list = new ArrayList<>();
list.add(0);
while (n-- > 0) {
Box(list);
}
System.out.println(list.get(k - 1));
}
private static void Box(ArrayList<Integer> list) {
ArrayList<Integer> temp = new ArrayList<>(list);
ArrayList<Integer> temp1 = new ArrayList<>(list);
for(int i = 0; i < list.size(); ++i) {
list.set(i, temp.get(i)+1); // (A+1)
}
list.addAll(temp); // (A+1)*A
for(int i = 0; i < temp1.size(); ++i) {
temp1.set(i, temp1.get(i)+2);
}
list.addAll(temp1); // (A+1)*A*(A+2)
}
} 
