等成绩太无聊了，不如来写个题解，纪念一下大学参加的最后一个比赛，以下是个人题解，不代表官方答案
试题 A: 整数范围
【问题描述】
用 8 位二进制（一个字节）来表示一个非负整数，表示的最小值是 0，则
一般能表示的最大值是多少？
答：255
试题 B: 纯质数
【问题描述】
如果一个正整数只有 1 和它本身两个约数，则称为一个质数（又称素数）。
前几个质数是：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, · · · 。
如果一个质数的所有十进制数位都是质数，我们称它为纯质数。例如：2,
3, 5, 7, 23, 37 都是纯质数，而 11, 13, 17, 19, 29, 31 不是纯质数。当然 1, 4, 35
也不是纯质数。
请问，在 1 到 20210605 中，有多少个纯质数？
答：1903
代码：
public class Q02 {
public static Set<Character> set = new HashSet<>();
static {
set.add('2');
set.add('3');
set.add('5');
set.add('7');
}
public static void main(String[] args) {
int sum = 0;
out: for (int i = 1; i <= 20210605; i++) {
String s = String.valueOf(i);
char[] arr = s.toCharArray();
for (int j = 0; j < arr.length; j++) {
if (!set.contains(arr[j])) continue out;
}
if (isZhi(i)) sum++;
}
System.out.println(sum);
}
private static boolean isZhi(int value) {
for (int i = 2; i < (value / 2) + 1; i++) {
if (value % i == 0) return false;
}
return true;
}
}
试题 C: 完全日期
【问题描述】
如果一个日期中年月日的各位数字之和是完全平方数，则称为一个完全日
期。
例如：2021 年 6 月 5 日的各位数字之和为 2 + 0 + 2 + 1 + 6 + 5 = 16，而
16 是一个完全平方数，它是 4 的平方。所以 2021 年 6 月 5 日是一个完全日期。
例如：2021 年 6 月 23 日的各位数字之和为 2 + 0 + 2 + 1 + 6 + 2 + 3 = 16，
是一个完全平方数。所以 2021 年 6 月 23 日也是一个完全日期。
请问，从 2001 年 1 月 1 日到 2021 年 12 月 31 日中，一共有多少个完全日
期？
答：977
代码：
public class Q03 {
public static Set<Integer> set = new HashSet<>();
static {
set.add(1);
set.add(4);
set.add(9);
set.add(16);
set.add(25);
set.add(36);
set.add(49);
set.add(64);
set.add(81);
}
public static void main(String[] args) {
LocalDate start = LocalDate.of(2001, 1, 1);
LocalDate temp = start;
int sum = 0;
while (true) {
char[] year = String.valueOf(temp.getYear()).toCharArray();
char[] month = String.valueOf(temp.getMonthValue()).toCharArray();
char[] day = String.valueOf(temp.getDayOfMonth()).toCharArray();
System.out.println(temp.getYear() + ":" + temp.getMonthValue() + ":" + temp.getDayOfMonth());
int value = 0;
for (int i = 0; i < year.length; i++) value += (year[i] - '0');
for (int i = 0; i < month.length; i++) value += (month[i] - '0');
for (int i = 0; i < day.length; i++) value += (day[i] - '0');
if (set.contains(value)) sum++;
if (temp.getYear() == 2021 && temp.getMonthValue() == 12 && temp.getDayOfMonth() == 31) break;
temp = temp.plusDays(1);
}
System.out.println(sum);
}
}
试题 D: 最小权值
【问题描述】
对于一棵有根二叉树 T，小蓝定义这棵树中结点的权值 W(T) 如下：
空子树的权值为 0。
如果一个结点 v 有左子树 L, 右子树 R，分别有 C(L) 和 C® 个结点，则
W(v) = 1 + 2W(L) + 3W® + (C(L))
2 C®。
树的权值定义为树的根结点的权值。
小蓝想知道，对于一棵有 2021 个结点的二叉树，树的权值最小可能是多
少？
答：2653631372
代码：
public class Q04 {
public static void main(String[] args) {
long[] dp = new long[2022];
Arrays.fill(dp, -1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i < dp.length; i++) {
long min = Long.MAX_VALUE;
for (int j = 0; j < i; j++) {
int leftNum = j;
int rightNum = i - j - 1;
long temp = 1 + 2 * dp[leftNum] + 3 * dp[rightNum] + leftNum * leftNum * rightNum;
min = Math.min(min, temp);
}
dp[i] = min;
}
System.out.println(Arrays.toString(dp));
System.out.println(dp[2021]);
}
}
试题 E: 大写
【问题描述】
给定一个只包含大写字母和小写字母的字符串，请将其中所有的小写字母
转换成大写字母后将字符串输出。
代码：
public class Q05 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String text = sc.next();
System.out.println(text.toUpperCase());
sc.close();
}
}
试题 F: 123
【问题描述】
小蓝发现了一个有趣的数列，这个数列的前几项如下：
1, 1, 2, 1, 2, 3, 1, 2, 3, 4, …
小蓝发现，这个数列前 1 项是整数 1，接下来 2 项是整数 1 至 2，接下来
3 项是整数 1 至 3，接下来 4 项是整数 1 至 4，依次类推。
小蓝想知道，这个数列中，连续一段的和是多少。
答：估计暴力解会超时，所以用了等差数列求和公式
代码：
public class Q06 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while (n-- > 0) {
long left = sc.nextLong();
long right = sc.nextLong();
System.out.println(solution(left, right));
}
sc.close();
}
public static long solution(long left, long right) {
long startLun = 1;
while (true) {
if (left <= num(startLun)) break;
startLun++;
}
long endLun = startLun;
while (true) {
if (right <= num(endLun)) break;
endLun++;
}
long sum = 0;
if (startLun != endLun) {
long start = left - num(startLun - 1);
sum += ((start + startLun) * (startLun - start + 1) / 2);
for (long i = startLun + 1; i < endLun; i++) sum += num(i);
long end = right - num(endLun - 1);
sum += num(end);
} else {
long lastLunNum = num(startLun - 1);
sum = (left - lastLunNum + right - lastLunNum) * (right - left + 1) / 2;
}
return sum;
}
public static long num(long value) {
if (value == 0) return 0;
return (value * value + value) / 2;
}
}
试题 G: 和与乘积
【问题描述】
给定一个数列 A = (a1, a2, · · · , an)，问有多少个区间 [L, R] 满足区间内元素
的乘积等于他们的和，即 aL · aL+1 · · · aR = aL + aL+1 + · · · + aR 。
答：dp，但是感觉有可能会超时
代码：
public class Q07 {
public static final long MAX = 200000 * 200000;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
System.out.println(solution(n, arr));
sc.close();
}
private static long solution(int n, int[] arr) {
long[] mult = new long[n];
long[] add = new long[n];
long sum = 0;
for (int i = 0; i < n; i++) {
sum++;
for (int j = 0; j < i; j++) {
if (mult[j] > MAX) continue;
mult[j] *= arr[i];
add[j] += arr[i];
if (mult[j] == add[j]) sum++;
}
mult[i] = arr[i];
add[i] = arr[i];
}
return sum;
}
}
试题 H: 巧克力
【问题描述】
小蓝很喜欢吃巧克力，他每天都要吃一块巧克力。
一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力，每种巧
克力有自己的价格、数量和剩余的保质期天数，小蓝只吃没过保质期的巧克力，
请问小蓝最少花多少钱能买到让自己吃 x 天的巧克力。
答：从最后一天到第一天，然后贪心，这次比赛用的是jdk1.8，在这之前用的是1.6，但是为了小心起见，写比较器的时候还是没有用Lambda来写
代码：
public class Q08 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int need = sc.nextInt();
int types = sc.nextInt();
Food[] foods = new Food[types];
for (int i = 0; i < types; i++) {
foods[i] = new Food(i, sc.nextInt(), sc.nextInt(), sc.nextInt());
}
System.out.println(solution(need, foods));
sc.close();
}
private static long solution(int need, Food[] foods) {
TreeSet<Food> noReady = new TreeSet<Food>(new Comparator<Food>() {
@Override
public int compare(Food o1, Food o2) {
if (o1.day != o2.day)
return o2.day - o1.day;
return o1.index - o2.index;
}
});
TreeSet<Food> hasReady = new TreeSet<Food>(new Comparator<Food>() {
@Override
public int compare(Food o1, Food o2) {
if (o1.price != o2.price)
return o1.price - o2.price;
return o1.index - o2.index;
}
});
for (Food f : foods) {
if (f.day >= need) hasReady.add(f);
else noReady.add(f);
}
long cost = 0;
while (need > 0) {
if (hasReady.isEmpty()) return -1;
Food hasReadyFood = hasReady.first();
hasReadyFood.num--;
if (hasReadyFood.num <= 0) hasReady.remove(hasReadyFood);
cost += hasReadyFood.price;
need--;
while (!noReady.isEmpty() && noReady.first().day >= need) {
Food firstFood = noReady.first();
noReady.remove(firstFood);
hasReady.add(firstFood);
}
}
return cost;
}
static class Food {
int index;
int price;
int day;
int num;
public Food(int index, int price, int day, int num) {
this.index = index;
this.price = price;
this.day = day;
this.num = num;
}
}
}
试题 I: 翻转括号序列
【问题描述】
给定一个长度为 n 的括号序列，要求支持两种操作：
- 将 [Li, Ri] 区间内（序列中的第 Li 个字符到第 Ri 个字符）的括号全部翻转（左括号变成右括号，右括号变成左括号）。
- 求出以 Li 为左端点时，最长的合法括号序列对应的 Ri （即找出最大的Ri 使 [Li, Ri] 是一个合法括号序列）。
答：没有好的思路，只能用直接按题目要求上了
代码：
public class Q09 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int len = sc.nextInt();
int times = sc.nextInt();
sc.nextLine();
boolean[] kuo = new boolean[len];
char[] arr = sc.nextLine().toCharArray();
for (int i = 0; i < arr.length; i++) {
kuo[i] = (arr[i] == '(');
}
for (int i = 0; i < times; i++) {
int type = sc.nextInt();
if (type == 1)
typeOne(kuo, sc.nextInt(), sc.nextInt());
else
System.out.println(typeTwo(kuo, sc.nextInt()));
}
sc.close();
}
public static void typeOne(boolean[] kuo, int left, int right) {
for (int i = left - 1; i < right - 1; i++) {
kuo[i] = !kuo[i];
}
}
public static int typeTwo(boolean[] kuo, int left) {
Stack<Boolean> stack = new Stack<Boolean>();
int maxRight = 0;
for (int i = left - 1; i < kuo.length; i++) {
if (kuo[i]) {
stack.add(kuo[i]);
} else if (stack.isEmpty()) {
return maxRight;
} else {
stack.pop();
if (stack.isEmpty()) maxRight = i + 1;
}
}
return maxRight;
}
}
试题 J: 异或三角
【问题描述】
给定 T 个数 n1, n2, · · · , nT，对每个 ni 请求出有多少组 a, b, c 满足：
- 1 ≤ a, b, c ≤ ni；
- a ⊕ b ⊕ c = 0，其中 ⊕ 表示二进制按位异或；
- 长度为 a, b, c 的三条边能组成一个三角形。
答：比赛做到这道题的时候去前面几道题看了一遍，估计都没什么可以改的了，然后这道题看了很久，但是最后还是没有想出来，用的暴力剪枝，看了一下测试用例，50%的用例是t=1，n<2^20，剪枝后在我的电脑跑这种用例大概两秒，希望跑题的机器能好点让我骗点分。
剪枝思路：因为三个数异或为0，所以三个数在每一位上的排列不可能为两个0一个1，其他的排列都有可能，然后看数的第一个位，因为要组成三角形，所以三个数的首位排列是两个1一个0。此外确定了两个数之后可以用异或算出第三个数，再用三角形检验一下是否符合，最后算出的结果乘上3的全排列，也就是6。剪枝后的复杂度小于O(n2)。
代码：
public class Q10 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int i = 0; i < t; i++) {
System.out.println(solution(sc.nextInt()));
}
sc.close();
}
public static long solution(int value) {
if (value < 6) return 0;
int start = 2;
int end = (start << 1);
long sum = 0;
while (value > start) {
if (value <= end) end = value + 1;
for (int i = start; i < end; i++) {
for (int j = i + 1; j < end; j++) {
int three = 0 ^ (i ^ j);
if (j < i + three) sum++;
}
}
start = end;
end = start << 1;
}
return sum * 6;
}
}