【十三届蓝桥杯省赛解析javaC组】-Toy模板网

这篇具有很好参考价值的文章主要介绍了【十三届蓝桥杯省赛解析javaC组】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

A. 字母排序

题目描述

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

解题思路

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);//与之匹配的时间可能会多，每匹配一次就去加1
                    A[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边形。(如图二所示)

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

输入格式

输入包含多组数据。
第一行包含一个整数 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]) 
                                 {//四条边的情况1
                                                ans = Math.min(ans, 4);
                                  }
                                  if (a[j][jj] == a[k][kk] && a[j][jj] == a[d][dd]) 
                                  {//四边情况2
                                    ans = 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.

输入样例

输出样例

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");
            else
                System.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

输出样例

解题思路

九章算术-更相减损术
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

输出样例

解题思路

二分加前缀和。

代码示例：

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;
            }
            else
                l = 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的余数。

输入样例

输出样例

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

输出样例

解题思路

贪心，就假设连续的数字出现在每个位置，然后把每个位置的最长子序列求出，最后的大最大的子序列，这里用到的存储的是线段树(本人暂时不理解线段树这个操作原理，概念已经懂了)文章来源地址https://www.toymoban.com/news/detail-418876.html

代码示例：

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取max
    static 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());
    }
}