第13届蓝桥杯javaB组
试题 A 星期计算
问题描述
已知今天是星期六，请问 \(20^{22}\) 天后是星期几？
注意用数字 \(1\) 到 \(7\) 表示星期一到星期日。
思路一
因为每七天一个循环，所以计算 \(20^{22}\ mod\ 7\) 的值，在从星期六向后数对应的天数即可。
又由于取余运算是封闭的，即乘的过程中取余不影响最终结果，因此可以不使用高精度运算。
public class Main {
public static void main(String[] args) {
int diff = 1;
for (int i = 0; i < 22; ++i) {
diff *= 20;
diff %= 7;
}
int ans = (6 + diff) % 7;
if (ans == 0) ans = 7;
System.out.println(ans);
}
}
思路二
由同余的性质得，\(20\equiv-1(mod\ 7)\)，即 \(20\) 与 \(-1\) 在模 \(7\) 的意义下相等。
所以 \(20^{22}\ mod\ 7={(-1)}^{22}\ mod\ 7=1\)
因此，向后数一天，即星期日。
试题 B 山
问题描述
这天小明正在学数数。
他突然发现有些正整数的形状像一座“山”，比如 \(123565321\)、\(145541\)，它们左右对称（回文）且数位上的数字先单调不减，后单调不增。
小明数了很久也没有数完，他想让你告诉他在区间 \([2022, 2022222022]\) 中有多少个数的形状像一座“山”。
思路
先判断对应位置的数是否相等，在判断相邻两个数字是否满足单调性质。
转化为字符串寻找对应位置的数更为简便。
public class Main {
static boolean check(int x) {
String s = Integer.toString(x);
for (int left = 0, right = s.length() - 1; left < right; ++left, --right) {
if (s.charAt(left) != s.charAt(right) || s.charAt(left) > s.charAt(left + 1) || s.charAt(right - 1) < s.charAt(right)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int ans = 0;
for (int i = 2022; i <= 2022222022; ++i)
if (check(i)) ++ans;
System.out.println(ans);//3138
}
}
试题 C 字符统计
问题描述
给定一个只包含大写字母的字符串 \(S\)，请你输出其中出现次数最多的字母。
如果有多个字母均出现了最多次，按字母表顺序依次输出所有这些字母。
思路
先记录下每个字母的出现次数，找出出现次数最大的数，再循环判断每个出现次数是否等于最大的。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] numbers = new int[26];
String line = sc.nextLine();
for (int i = 0; i < line.length(); ++i) {
++numbers[line.charAt(i) - 'A'];
}
int max = -1;
for (int i = 0; i < 26; ++i) {
max = Math.max(max, numbers[i]);
}
for (int i = 0; i < 26; ++i) {
if (numbers[i] == max) {
System.out.print((char)(i + 'A'));
}
}
sc.close();
}
}
试题 D 最少刷题数
问题描述
小蓝老师教的编程课有 \(N\) 名学生，编号依次是 \(1\cdots N\)。第 \(i\) 号学生这学期刷题的数量是 \(A_i\)。
对于每一名学生，请你计算他至少还要再刷多少道题，才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。
题目简单来说就是，刷最少的题 让 刷题多的少于或等于刷题少的（用最少的努力达到中等或偏上的排名）
思路一
找到刷题数排在正中间的人，其刷题数记为 \(midValue\)
- 如果刷题数大于 \(midValue\)，则说明他已经满足刷题多的少于刷题少的了（已经中等偏上了）
- 如果刷题数等于 \(midValue\)，则需要计算比他刷题数（即 \(midValue\)）少的人的个数 和 刷题数比他多的人的个数，确定最少需要超过多少人，由于已经是中位数了，最多只用刷一道题即可达成目标。
- 如果刷题数小于 \(midValue\)，则需要判断刷题数比 \(midValue\) 少的人的个数 和 多的人的个数，如果多的人的个数大于少的人的个数，则需要刷题数至 \(midValue+1\)，否则刷题数至 \(midValue\)。
注意：当前这个人多刷题后，刷题数比他少的人数要排去当前这个人。
对于如何知道 \(midValue\) 的值，有三种方法：
- 排序后，求中位数，时间复杂度 \(O(nlog(n))\)
- 小根堆，与堆排序的方法类似，只需将弹出堆顶元素次数改为 \(k\) 次，时间复杂度 \(O(klog(n))=O(\dfrac{n}{2}log(n))=O(nlog(n))\)
- 依据快排相类似的思想，时间复杂度 \(O(\sum{n+\dfrac{n}{4}}+\dfrac{n}{8}+\cdots+1)=O(2n)=O(n)\)
此处使用第三种方法求 \(midValue\)
时间复杂度 \(O(n)\)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Random;
public class Main {
public static void swap(int arr[], int l, int r) {
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
/*
* 作用：对数组进行划分，选择一个基准pivot，放在它排序后的位置，即左边的数比它小，右边的数比它大
* 描述：返回基准下标（快速排序所用）
*/
public static int partition(int[] arr, int l, int r, int pos) {
int pivot = arr[pos];
swap(arr, l, pos);
while (l < r) {
while (l < r && arr[r] >= pivot) --r;
arr[l] = arr[r];
while (l < r && arr[l] <= pivot) ++l;
arr[r] = arr[l];
}
arr[l] = pivot;
return l;
}
public static Random rand = new Random();
/*
* 作用：找到数组[l,r]排序后下标为k的数
*/
public static int nthElement(int[] arr, int l, int r, final int k) {
int pos = partition(arr, l, r, rand.nextInt(r - l + 1) + l);
if (pos == k) return arr[pos];
if (k < pos) return nthElement(arr, l, pos - 1, k);
return nthElement(arr, pos + 1, r, k);
}
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int get() throws Exception {
in.nextToken();
return (int) in.nval;
}
public static void main(String[] args) throws Exception {
final int n = get();
int[] a = new int[n], b = new int[n];
for (int i = 0; i < n; ++i) {
b[i] = a[i] = get();
}
int midValue = nthElement(b, 0, n - 1, n / 2);
int less = 0, more = 0;
for (int val : a) {
if (val < midValue) ++less;
else if (val > midValue) ++more;
}
StringBuilder ans = new StringBuilder();
for (int val : a) {
if (val > midValue) {
ans.append("0 ");
} else if (val == midValue) {
if (more <= less)
ans.append("0 ");
else
ans.append("1 ");
} else {
if (more <= less - 1)
ans.append((midValue - val) + " ");
else
ans.append((midValue - val + 1) + " ");
}
}
System.out.println(ans);
}
}
思路二
运用到二分的知识。
具体思路见注释。
时间复杂度 \(O(nlog(max(A_i)))\)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Main {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int get() throws Exception {
in.nextToken();
return (int) in.nval;
}
public static void main(String[] args) throws Exception {
int n = get();
int[] a = new int[n];
final int N = 100000;
// num[i]为i的个数
int[] num = new int[N + 1];
int max = -1;
for (int i = 0; i < n; ++i) {
a[i] = get();
max = Math.max(max, a[i]);
++num[a[i]];
}
// sum[i]为比i小的个数
int[] sum = new int[max + 1];
for (int i = 1; i <= max; ++i) {
sum[i] = num[i - 1] + sum[i - 1];
}
// 比i小的数的个数为sum[i]
// 比i大的数的个数为n-sum[i]-num[i]
StringBuilder ans = new StringBuilder();
for (int i = 0; i < n; ++i) {
if (n - sum[a[i]] - num[a[i]] <= sum[a[i]]) {
ans.append("0 ");
} else {
// 定义l最后落到应该刷的最少的题目数
// 不可能取到max+1
int l = a[i] + 1, r = max, mid;
while (l <= r) {
mid = l + r >> 1;
// 比i刷题少的个数要减去当前这个人
if (n - (sum[mid] - 1) - (num[mid] + 1) <= sum[mid] - 1)
r = mid - 1;
else
l = mid + 1;
}
ans.append((l - a[i]) + " ");
}
}
System.out.println(ans);
}
}