【十三届蓝桥杯省赛解析javaC组】

A. 字母排序

题目描述

解题思路

A题相对比较简单，这题有两种解法
第一种是可以利用记事本把文本复制，然后自己手动排序
第二种是写代码：具体思路是定义一个字符串用来储存问文本，然后把文本转成字符型数组，利用Arrays.sort对字符型数组进行排序，最终实现字符的排序

代码示例

import java.util.Arrays;
import java.util.Scanner;public class A {static String str;static char[] chars;public static void main(String[] args) {Scanner scan = new Scanner(System.in);str = scan.next();chars = new char[str.length()];trans();Arrays.sort(chars);print();}private static void trans() {for (int i = 0; i < str.length(); i++) {chars[i]=str.charAt(i);}}private static void print(){for (char a:chars) {System.out.print(a);}}
}

B. 特殊时间

题目描述

2022年2月22日22:2022:20 是一个很有意义的时间, 年份为2022,由3个2和1个0
组成, 如果将月和日写成4位, 为0222,也是由3个2和1个0组成, 如果将时间中的
时和分写成4位, 还是由 3个2 和1个0组成。小蓝对这样的时间很感兴趣, 他还找到了其它类似的例子, 比如111年10月11日
01:11,220201:11,2202 年2月22日22:0222:02等等。请问, 总共有多少个时间是这种年份写成4位月日写成4 位时间写成4位后由3个
一种数字和 1 个另一种数字组成。注意1111年11月11日11: 1111:11不算，因为
它里面没有两种数字

解题思路

因为时间里面只有两个不同的数字，我们可以通过对两个数字的遍历去组成不同的四位数，然后通过check_month和check_time函数去判别组成的四位数是否合格（是否符合时间或者是日期的标准）最后累加在一起就可以求出最终的结果

代码示例

public class B {static  int[] day_month ={0,31,28,31,30,31,30,31,31,30,31,30,31};/**检查年月日是否合法*/public static int check_month(int D){int M = D/100;//取得月份int day = D%100;//取得天数if(M<1||M>12)return 0;if (day<=1||day>day_month[M])return 0;return 1;}/**判断时间是否合法*/public static int check_time(int m){int H = m/100;//取得小时int M = m%100;//取得分钟数if (H<0||H>23) return 0;if (M<0||M>59) return 0;return 1;}public static void main(String[] args) {int count=0;//记录匹配个数/**因为时间里只包含两个数字，所以我们这里只开两重循环*/for (int a = 0; a <= 9; a++)for (int b = 0; b <= 9; b++)if(a!=b){int year =4;//两个数字可以匹配到的年份有四种int month=0;//与之匹配的月份我们要去做检查月份天数是否成立，所以放在下面赋值int time=0;//同上月份一样要放在上边进行与之匹配int[] A = new int[]{a,a,a,a};//枚举四种情况即aaab，aaba，abaa，baaa；for (int i = 0; i < 4; i++) {A[i]=b;int num = 0;//用来拼接与之对应的情况的数字for (int j = 0; j < 4; j++) {num = num * 10 + A[j];}month += check_month(num);time += check_time(num);//与之匹配的时间可能会多，每匹配一次就去加1A[i]=a;}count+=year*month*time;//每调整一次数字位置就计算一次}System.out.println(count);}
}

C. 纸张尺寸

题目描述

在 ISO国际标准中定义了A0 纸张的大小为1189mm×841mm, 将A0纸沿长边对折后
为A1纸, 大小为841mm× 594mm, 在对折的过程中长度直接取下整 (实际裁剪时可
能有损耗)。将 A1 纸沿长边对折后为A2 纸, 依此类推。
输入纸张的名称, 请输出纸张的大小。

输入格式

输入一行包含一个字符串表示纸张的名称, 该名称一定是 A0、A1、A2、 A3、A4、A5、A6、A7、A8、A9 之一。

输出格式

输出两行，每行包含一个整数，依次表示长边和短边的长度。

输入样例

A0

输出样例

1189
841

解题思路

按照题目详情我们可以知道，要根据输入的纸张型号去输出相对的纸张大小，题目有两种思路：
其一：自己计算出每种纸张的大小，然后通过字符比对去输出相对型号的相对大小（若是自己写不出代码的话建议放弃）
其二：用Integer的pareseInt函数把输入的第二个字符转化成数字，然后通过for循环去计算出与之对应的纸张大小，然后输出
可以把我最后的if else删掉，放在那里只是为了严谨一些

代码示例

import java.util.Scanner;public class C {static int Long=1189;static int wide=841;static String size;//用来获取纸张型号static int sizeID;public static void main(String[] args) {Scanner scan = new Scanner(System.in);size= scan.next();sizeID=Integer.parseInt(String.valueOf(size.charAt(1)));for (int i = 0; i < sizeID; i++) {if (Long > wide) {Long/=2;}else{wide/=2;}}if (Long > wide) {System.out.println(Long);System.out.println(wide);}else{System.out.println(wide);System.out.println(Long);}}
}

D. 求和

题目描述

给定N个数让他们两两相乘再相加即如下：
S=A1⋅A2+A1⋅A3+⋯+A1⋅An+A2⋅A3+⋯+An−2⋅An−1+An−2⋅An+An−1⋅An
本人口头描述，可能与题目有所不符，但大概是这个样子

输入格式

输入一行包含一个字符串表示纸张的名称, 该名称一定是 A0、A1、A2、 A3、A4、A5、A6、A7、A8、A9 之一。

输出格式

输出两行，每行包含一个整数，依次表示长边和短边的长度。

输入样例

A0

输出样例

1189
841

解题思路

代码示例：

import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();long[] a = new long[n + 10];long[] b = new long[n + 10];for(int i = 1; i <= n; i++){a[i] = in.nextLong();//预处理前缀和b[i] = b[i - 1] + a[i];}long S = 0;for(int i = 1; i <= n; i++)S += a[i] * (b[n] - b[i]);System.out.println(S);}
}

E. 矩形拼接

题目描述

已知 3 个矩形的大小依次是 a1Xb1, a2Xb2,a3Xb3 用这 3 个矩形能拼出的所有多
边形中, 边数最少可以是多少?
例如用3×2的矩形（用 A 表示)、4×1 的矩形 (用 B 表示) 和 2×4的矩形(用C表示)
可以拼出如下4边形（如图一所示）。
例如用 3×2 的矩形 (用 A 表示)、3×1 的矩形（用B表示) 和 1×1 的矩 形（用C 表示）可以拼出如下6边形。(如图二所示)

图一

图二

输入格式

输入包含多组数据。
第一行包含一个整数 T, 代表数据组数。
以下T行, 每行包含 6 个整数 a1, b1, a2, b2, a3, b3,
其中 a1, b1是第一个矩 形的边长, 
a2, b2是第二个矩形的边长,  
a3，b3是第三个矩形的边长。

输出格式

对于每组数据, 输出一个整数代表答案。

输入样例

2
2 3 4 1 2 4
1 2 3 4 5 6

输出样例

4
6

解题思路

考虑所有拼接的情况，由于只需要最少边，所以拼接出来的可能只有三种，分别是4,6,8边

代码示例：

import java.util.Scanner;public class E {static int n;//用来获取输入正方形的组数static int[][] a;//用来存放正方形的边数static int[] b;//用来存储每组正方形的拼接的最小变public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt();b = new int[n];int ans;//按照所有边不等来赋初始值for (int i = 0; i < n; i++) {a = new int[3][2];for (int j = 0; j < 3; j++) {a[j][0]=scan.nextInt();a[j][1]= scan.nextInt();}ans = 8;for (int j = 0; j < 3; j++) {for (int k = 0; k < 3; k++)if (k != j) {for (int d = 0; d < 3; d++)if (d != j && d != k) {for (int jj = 0; jj < 2; jj++)for (int kk = 0; kk < 2; kk++)for (int dd = 0; dd < 2; dd++) {if (a[j][jj] == a[k][kk] || a[j][jj] + a[k][kk] == a[d][dd]){//六条边的情况ans = Math.min(ans, 6);}if (a[j][jj] == a[k][kk] &&a[j][1 - jj] + a[k][1 - kk] == a[d][dd]) {//四条边的情况1ans = Math.min(ans, 4);}if (a[j][jj] == a[k][kk] && a[j][jj] == a[d][dd]) {//四边情况2ans = Math.min(ans, 4);}}}}}b[i]=ans;}for (int i = 0; i < n; i++) {System.out.println(b[i]);}}
}

F. 选数异或

题目描述

给定一个长度为n的数列 A1, A2,...... , An和一个非负整数 x, 
给定m次查询, 每次询问能否从某个区间[l,r]中选择两个数
使得他们的异或等于x。

输入格式

输入的第一行包含三个整数n,m,x。
第二行包含n个整数 A1,A2,...., An
接下来m行，每行包含两个整数 li, ri表示询问区间[li, ri]。

输出格式

对于每个询问, 如果该区间内存在两个数的异或为x则输出yes, 否则输出no.

输入样例

4 4 1
1 2 3 4
1 4
1 2
2 3
3 3

输出样例

yes
no
yes
no

解题思路

记录每个区间的异或值，然后这里由于查询会超时，是用线段树存储的

代码示例：

import java.util.*;
import java.io.*;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 65536);static StringTokenizer tokenizer = new StringTokenizer("");static int maxn = (int) 1e5 + 10, maxm = (1 << 20) + 10;static int[] tree = new int[maxn * 4];static int[] Left = new int[maxn];static int[] pos = new int[maxm];static int[] a = new int[maxn];static int n, m, x;public static void main(String[] args) {n = nextInt(); m = nextInt(); x = nextInt();for (int i = 1; i <= n; i++) {//预处理Left数组a[i] = nextInt();Left[i] = pos[a[i] ^ x];pos[a[i]] = i;}build(1, 1, n);//线段树建树while (m-- > 0) {int l = nextInt(), r = nextInt();if(query(1, 1, n, l, r) >= l)//查询Left数组的区间[l,r]最大值System.out.println("yes");elseSystem.out.println("no");}}//线段树模板static void build(int o, int l, int r){if(l == r){tree[o] = Left[l];return;}int mid = (l + r) >> 1;build(o << 1, l, mid);build(o << 1 | 1, mid + 1, r);tree[o] = Math.max(tree[o << 1], tree[o << 1 | 1]);}//查询区间[L,R]的最大值static int query(int o, int l, int r, int L, int R){if(L <= l && r <= R)return tree[o];int mid = (l + r) >> 1;int ans = 0;if(L <= mid)ans = Math.max(ans, query(o << 1, l, mid, L, R));if(R > mid)ans = Math.max(ans, query(o << 1 | 1, mid + 1, r, L, R));return ans;}static String next() {while (!tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(br.readLine());} catch (IOException e) {e.printStackTrace();}}return tokenizer.nextToken();}static int nextInt() {return Integer.parseInt(next());}static long nextLong() {return Long.parseLong(next());}
}

G. GCD（数论定理）

题目描述

给定两个不同的正整数a, b, 求一个正整数k使得gcd(a+k, b+k)尽可能大, 
其中gcd(a,b)表示 a和b的最大公约数, 如果存在多个k, 
请输出所有满足条件的k中最小的那个。

输入格式

输入一行包含两个正整数 a, b,用一个空格分隔。

输出格式

输出一行包含一个正整数k。

输入样例

5 7

输出样例

1

解题思路

九章算术-更相减损术
gcd 存在以下性质可以和加减法联系起来：gcd(a,b)=gcd(b-a,a)gcd(a,b)=gcd(b−a,a) ，这个式子就是更相减损术

代码示例：

import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);long a = in.nextLong(), b = in.nextLong();long r = a % (b - a), k;if(r == 0)k = 0;else k = (b - a) - r;System.out.println(k);}
}

H. 青蛙过河

题目描述

小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里
的石头跳到对岸。
河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。
不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 
这块石头的高度就会下降1, 当石头的高度下降到0时小青蛙不能再跳到这块石头上
（某次跳跃后使石头高度下降到0是允许的)。
小青蛙一共需要去学校上x天课, 所以它需要往返2x次当小青蛙具有一个跳跃能力y时,它能跳不超过y的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完x次课。

输入格式

输入的第一行包含两个整数n,x分别表示河的宽度和小青蛙需要去学校的天数。
请注意2x才是实际过河的次数。
第二行包含 n-1n−1 个非负整数 H1, H2, ...., Hn-1,
其中Hi>0表示在河中与小青蛙的家相距i的地方有一块高度为Hi的石头,Hi=0 表示这个位置没有石头。

输出格式

输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。

输入样例

5 1
1 0 1 0

输出样例

4

解题思路

二分加前缀和。

代码示例：

import java.util.*;
import java.io.*;public class Main {public static int n, x;//判定能力为y时，是否合法public static boolean check(int y, int[] Pre_Sum) {//枚举所有长度为y的区间for(int l = 1; l <= n - y; l++){int r = l + y - 1;if(Pre_Sum[r] - Pre_Sum[l - 1] < 2 * x)return false;}return true;}public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();x = in.nextInt();int[] H = new int[n + 10];int[] Pre_Sum = new int[n + 10];for(int i = 1; i <= n - 1; i++){H[i] = in.nextInt();//预处理前缀和Pre_Sum[i] = Pre_Sum[i - 1] + H[i];}//二分答案int l = 1, r = n, ans = -1;while(l <= r){int mid = (l + r) / 2;if(check(mid, Pre_Sum)){ans = mid;r = mid - 1;}elsel = mid + 1;}System.out.println(ans);}
}

I. 因数平方和

题目描述

给定一个数N，让你求该数所有因数的平方和取余10^9+7
例如：f（12）=(1^2+2^2+3^2+4^2+6^2+12^2)%(10^9+7)
本人口头描述，可能与题目有所不符，但大概是这个样子

输入格式

输入一行包含一个正整数n

输出格式

输出一个整数表示答案 f(n)除以10^9+7的余数。

输入样例

100000

输出样例

680584257

解题思路

数论的问题。

代码示例：

import java.util.*;
import java.io.*;public class Main {//模数public static long MOD = 1000000007;//6在模数MOD下的逆元public static long Inv = 166666668;//求数字1-n的平方和public static long S(long x) {return x * (x + 1) % MOD * (2 * x + 1) % MOD * Inv % MOD;}public static void main(String[] args) {Scanner in = new Scanner(System.in);long n = in.nextLong(), ans = 0;//枚举左端点for(long l = 1; l <= n;){long r = n / (n / l);if(r > n)r = n;ans = (ans + (n / l) * (S(r) + MOD - S(l - 1))) % MOD;l = r + 1;}System.out.println(ans);}
}

G. 最长不下降子序列

题目描述

给定一个长度为 NN 的整数序列: A1, A2,..., An
现在你有一次机会, 将其中连续的K个数修改成任意一个相同值。
请你计算如何修改可以使修改后的数列的最长不下降子序列最长,
请输出这个最长的长度。
最长不下降子序列是指序列中的一个子序列, 子序列中的每个数不小于在它之前的数。

输入格式

输入第一行包含两个整数N和K
第二行包含N个整数A1, A2,...., An。

输出格式

输出一行包含一个整数表示答案。

输入样例

5 1
1 4 2 8 5

输出样例

4

解题思路

贪心，就假设连续的数字出现在每个位置，然后把每个位置的最长子序列 求出，最后的大最大的子序列，这里用到的存储的是线段树(本人暂时不理解线段树这个操作原理，概念已经懂了)

代码示例：

import java.util.*;
import java.io.*;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 65536);static StringTokenizer tokenizer = new StringTokenizer("");static int maxn = (int) 1e5 + 10;static int[] tree = new int[maxn * 4];static int[] a = new int[maxn];static int[] b = new int[maxn];static int[] dp = new int[maxn];static int n, k;public static int lower_bound(int[] arr, int l, int r, int target){ //找到第一个大于等于x的数的位置while (l<r){int mid=l+(r-l)/2;if(arr[mid]>=target){r=mid;}else{l=mid+1;}}return l==arr.length?-1:l;}public static void main(String[] args) {SortedSet<Integer> set=new TreeSet<Integer>();n = nextInt(); k = nextInt();for (int i = 1; i <= n; i++) {a[i] = nextInt();b[i] = a[i];set.add(a[i]);}if(n == k){System.out.println(n);return;}//离散化int tot=0;for(int cur:set){b[tot++]=cur;}for(int i = 1; i <= n; i++){a[i] = lower_bound(b, 0, tot, a[i]) + 1;}//从前往后遍历a，放入权值线段树中int ans = 0;for(int i = 1; i <= n; i++){dp[i] = query(1, 1, tot, 1, a[i]) + 1;update(1, 1, tot, a[i], dp[i]);}//重新清空权值线段树tree = new int[maxn * 4];for(int i = n; i > k; i--){//a[i-k+1] ... a[i]相等 均等于a[i-k]//最后一段要注意：查询的是[a[i-k],tot]中的最大值ans = Math.max(ans, dp[i - k] + k - 1 + query(1, 1, tot, a[i - k], tot) + 1);int tmp = query(1, 1, tot, a[i], tot) + 1; //以a[i]开始的最长上升子序列长度ans = Math.max(ans, tmp + k);//插入的是a[i]update(1, 1, tot, a[i], tmp);}System.out.println(ans);}//更新下标为x，与val取maxstatic void update(int o, int l, int r, int x, int val){if(l == r){tree[o] = Math.max(tree[o], val);return;}int mid = (l + r) >> 1;if(x <= mid)update(o << 1, l, mid, x, val);else update(o << 1 | 1, mid + 1, r, x, val);tree[o] = Math.max(tree[o << 1], tree[o << 1 | 1]);}//查询区间[L,R]最大值static int query(int o, int l, int r, int L, int R){if(L <= l && r <= R)return tree[o];int mid = (l + r) >> 1;int ans = 0;if(L <= mid)ans = Math.max(ans, query(o << 1, l, mid, L, R));if(R > mid)ans = Math.max(ans, query(o << 1 | 1, mid + 1, r, L, R));return ans;}static String next() {while (!tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(br.readLine());} catch (IOException e) {e.printStackTrace();}}return tokenizer.nextToken();}static int nextInt() {return Integer.parseInt(next());}static long nextLong() {return Long.parseLong(next());}
}