自学内容网 自学内容网

【算法】2022年第十三届蓝桥杯大赛软件类省赛Java大学C组真题

 个人主页:NiKo

算法专栏:算法设计与分析


目录

题目 2680:纸张尺寸 

题目 2664:求和

题目 2681: 矩形拼接

题目 2665: 选数异或

题目 2682: GCD

题目 2667: 青蛙过河

题目 2683: 因数平方和

题目 2668: 最长不下降子序列


题目 2680:纸张尺寸 

  • 题目描述

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

  • 输入格式

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

  • 输出格式

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

  • 样例输入

    A0
  • 样例输出

    1189
    841
  • 题解

#include<stdio.h>
int main()
{
    char let;
    int num;
    int long_ = 1189,short_ = 841;
    int newlong = long_,newshort = short_;
    scanf("%c%d",&let,&num);
    int type = num;
    if(type==0){
        printf("%d\n",1189);
        printf("%d",841);
    }else{
        while(type){
            // 长边对折
            newlong = long_ / 2;
            if(newlong < short_){
                int temp = short_;
                short_ = newlong;
                long_ = temp;
            }
            type--;
        }
        printf("%d\n",long_);
        printf("%d",short_);
    }
    return 0;
}

题目 2664:求和

  • 题目描述

            给定 n 个整数 a1, a2, · · · , an ,求它们两两相乘再相加的和,即 S = a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an-2 · an-1 + an-2 · an + an-1 · an.

  • 输入格式

    输入的第一行包含一个整数 n 。 

    第二行包含 n 个整数 a1, a2, · · · an。

  • 输出格式

    输出一个整数 S,表示所求的和。请使用合适的数据类型进行运算。

  • 样例输入

    4
    1 3 6 9
  • 样例输出

    117
  • 提示

    对于 30% 的数据,1 ≤ n ≤ 1000,1 ≤ ai ≤ 100。

    对于所有评测用例,1 ≤ n ≤ 200000,1 ≤ ai ≤ 1000。

  • 题解

#include<bits/stdc++.h>
using namespace std;
int main(void){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin>>n;
    long long sum[200001];
    long long ans=0;
    int a;
    cin>>a;
    sum[1]=a;
    for(int i=2;i<=n;++i){
        cin>>a;
        sum[i]=sum[i-1]+a;
        ans+=a*sum[i-1];
    }
    cout<<ans;
    return 0;
}

题目 2681: 矩形拼接

  • 题目描述

    已知 3 个矩形的大小依次是 a1 × b1, a2 × b2 和 a3 × b3。用这 3 个矩形能拼出的所有多边形中,边数最少可以是多少?例如用 3 × 2 的矩形(用 A 表示)、4 × 1 的矩形(用 B 表示)和 2 × 4 的矩形(用 C 表示)可以拼出如下 4 边形。

    蓝桥杯2022年第十三届省赛真题矩形拼接1

    例如用 3 × 2 的矩形(用 A 表示)、3 × 1 的矩形(用 B 表示)和 1 × 1 的矩形(用 C 表示)可以拼出如下 6 边形。

    蓝桥杯2022年第十三届省赛真题矩形拼接2

  • 输入格式

    输入包含多组数据。

    第一行包含一个整数 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
  • 提示

    对于 10% 的评测用例,1 ≤ T ≤ 5,1 ≤ a1, b1, a2, b2, a3, b3 ≤ 10,a1 = a2 = a3。

    对于 30% 的评测用例,1 ≤ T ≤ 5,1 ≤ a1, b1, a2, b2, a3, b3 ≤ 10。

    对于 60% 的评测用例,1 ≤ T ≤ 10,1 ≤ a1, b1, a2, b2, a3, b3 ≤ 20。

    对于所有评测用例,1 ≤ T ≤ 1000,1 ≤ a1, b1, a2, b2, a3, b3 ≤ 100。

  • 题解

#include<bits/stdc++.h>
using namespace std;
int a[3][2];
int main()
{
int T;
cin >> T;
while (T--)
{
//输入三个矩形的长和宽
for (int i = 0; i < 3; i++)
cin >> a[i][0] >> a[i][1];
int ans = 8;//完全不匹配时的答案为8
for (int i = 0; i < 3; i++)//枚举第一个矩形
for (int j = 0; j < 3; j++)
if (i != j)//枚举第二个矩形
for (int k = 0; k < 3; k++)
if (i != k && j != k)//枚举第三个矩形
for (int ii = 0; ii <= 1; ii++)//枚举第一个矩形的长宽
for (int jj = 0; jj <= 1; jj++)//枚举第二个矩形的长宽
for (int kk = 0; kk <= 1; kk++)//枚举第三个矩形的长宽
{
//第一个矩形的长等于后两个矩形的长之和
if (a[i][ii] == a[j][jj] + a[k][kk])
{
ans = min(ans, 6);
//后面两个矩形的宽相等
if (a[j][1 - jj] == a[k][1 - kk])
ans = min(ans, 4);
}
//至少有一个矩形的长和第一个矩形的长相等
if (a[i][ii] == a[j][jj] || a[i][ii] == a[k][kk])
ans = min(ans, 6);
//三个矩形的长全部相等
if (a[i][ii] == a[j][jj] && a[i][ii] == a[k][kk])
ans = min(ans, 4);
}
cout << ans << endl;
}
return 0;
}

题目 2665: 选数异或

  • 题目描述

    给定一个长度为 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
  • 提示

    显然整个数列中只有 2, 3 的异或为 1。

    对于 20% 的评测用例,1 ≤ n, m ≤ 100;

    对于 40% 的评测用例,1 ≤ n, m ≤ 1000;

    对于所有评测用例,1 ≤ n, m ≤ 100000 ,0 ≤ x < 2的20次方 ,1 ≤ li ≤ ri ≤ n , 0 ≤ Ai < 2的20次方。 

  • 题解

#include<bits/stdc++.h>
using namespace std;
int main(void){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m,x;
    cin>>n>>m>>x;
    int arry[100002];
    unordered_map<int,vector<int>> Map; //记录值和所有下标
    vector<vector<int>> ans;
    for(int i=1;i<=n;++i){//O(n)
        cin>>arry[i];
        if(Map.find(arry[i])==Map.end())
            Map[arry[i]]={i};
        else Map[arry[i]].emplace_back(i);
    }
    for(int i=1;i<=n;++i){//O(n*pair)
        if(Map.find(arry[i]^x)!=Map.end()){
            //i 与 Map[arry[i]^x] 这俩位置可以异或为x
            int temp=arry[i]^x;
            for(int j=0;j<Map[temp].size();++j){
            //由于答案是成对出现的,这里肯定会出现重复,但是不一定对称
                ans.push_back({min(i,Map[temp][j]),max(i,Map[temp][j])});
            }
        }
    }
    while(m--){
        int left,right;
        cin>>left>>right;
        bool flag=true;
        for(int j=0;j<ans.size();++j){//O(m*pair)
            if(left<=ans[j][0]&&right>=ans[j][1]){
                cout<<"yes"<<'\n';
                flag=false;
                break;
            }
        }
        if(flag)
            cout<<"no"<<'\n';
    }
    return 0;
}

题目 2682: GCD

  • 题目描述

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

  • 输入格式

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

  • 输出格式

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

  • 样例输入

    5 7
  • 样例输出

    1
  • 提示

    对于 20% 的评测用例,a < b ≤ 10的5次方 ;
    对于 40% 的评测用例,a < b ≤ 10的9次方 ;
    对于所有评测用例,1 ≤ a < b ≤ 10的18次方 。

  • 题解

#include<iostream>
using namespace std; 
 
int main()
 
{
    long long a,b,c,d;
 
    cin>>a>>b;
 
    if(a>b){
        long long t=a;
        a=b;
        b=t;
    }
    c=b-a;
    d=a/c;
 
    if(a%c) 
        d++;
 
    cout<<d*c-a<<endl;
    return 0;
} 

题目 2667: 青蛙过河

  • 题目描述

    小青蛙住在一条河边,它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。

    河里的石头排成了一条直线,小青蛙每次跳跃必须落在一块石头或者岸上。不过,每块石头有一个高度,每次小青蛙从一块石头起跳,这块石头的高度就会下降 1,当石头的高度下降到 0 时小青蛙不能再跳到这块石头上(某次跳跃后使石头高度下降到 0 是允许的)。

    小青蛙一共需要去学校上 x 天课,所以它需要往返 2x 次。当小青蛙具有一个跳跃能力 y 时,它能跳不超过 y 的距离。

    请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。

  • 输入格式

    输入的第一行包含两个整数 n, x,分别表示河的宽度和小青蛙需要去学校的天数。请注意 2x 才是实际过河的次数。

    第二行包含 n − 1 个非负整数 H1, H2, · · · , Hn-1,其中 Hi > 0 表示在河中与小青蛙的家相距 i 的地方有一块高度为 Hi 的石头,Hi = 0 表示这个位置没有石头。

  • 输出格式

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

  • 样例输入

    5 1
    1 0 1 0
  • 样例输出

    4
  • 提示

    由于只有两块高度为 1 的石头,所以往返只能各用一块。第 1 块石头和对岸的距离为 4,如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少需要 4 的跳跃能力。 

    对于 30% 的评测用例,n ≤ 100;

    对于 60% 的评测用例,n ≤ 1000;

    对于所有评测用例,1 ≤ n ≤ 10的5次方 , 1 ≤ x ≤ 10的9次方 , 1 ≤ Hi ≤ 10的4次方。

  • 题解

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
typedef long long LL;
typedef pair<int,int>pii;
const int mod = 1e9 + 7 , INF = 0x3f3f3f3f , N = 1e5 + 10;
 
int n,m;
int a[N];
 
bool check(int x)
{
    // 如果所有长度为x的区间都大于等于m ,则true
    int s = 0;
    
    for (int i = 1 ; i <= min(n - 1,x) ; i ++)
        s += a[i];
        
    if (s < m)
        return false;
    for (int i = x + 1; i <= n - 1; i ++)
    {
        s -= a[i - x];
        s += a[i];
        if (s < m)
            return false;
    }
    
    return s >= m;
}
 
int main()
{
    cin >> n >> m;
    m *= 2;
    for (int i = 1 ; i <= n - 1 ; i ++)
        cin >> a[i];    
    int l = 0,r = n;
    
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    
    cout << r << endl;
    
}

题目 2683: 因数平方和

  • 题目

  •  题解

import java.time.format.DateTimeFormatter;
import java.time.LocalDateTime;
 
public class Test {
 
    public static void main(String[] args) { new Test().run(); }
 
    void run() {
        DateTimeFormatter date = DateTimeFormatter.ofPattern("MMdd");
        DateTimeFormatter time = DateTimeFormatter.ofPattern("HHmm");
        LocalDateTime start = LocalDateTime.of(0000, 01, 01, 00, 00);
        LocalDateTime end = LocalDateTime.of(0000, 12, 31, 23, 59);
        int[] buff = new int[128];
        int ans = 0;
        for (; start.compareTo(end) <= 0; start = start.plusMinutes(1)) {
            for (char i = '0'; i <= '9'; ++i) buff[i] = 0;
            for (byte b : start.format(date).getBytes()) ++buff[b];
            boolean flag1 = true, flag3 = true;
            for (char i = '0'; i <= '9'; ++i)
                if (buff[i] == 1) flag1 = false;
                else if (buff[i] == 3) flag3 = false;
            if (flag1 || flag3) continue;
            for (byte b : start.format(time).getBytes()) --buff[b];
            for (char i = '0'; i <= '9'; ++i)
                if (buff[i] != 0) flag1 = true;
            if (!flag1) ++ans;
        }
        System.out.println(4 * ans);
    }
}

题目 2668: 最长不下降子序列

  • 题目

  •  题解
package leetcode板块;

import java.util.Arrays;
import java.util.Scanner;

public class _题目2668蓝桥杯2022年第十三届省赛真题_最长不下降子序列 {
    /**
     *
     * @param args
     */
    public static void main(String[] args) {
        // 现在你有一次机会,将其中【连续的 K 个数】 修改成 【任意一个相同值】。
        // 请你计算如何修改可以使修改后的数列的最长不下降子序列最长,请输出这个最长的长度。
        // TODO 最长不下降子序列是指序列中的一个子序列,子序列中的每个数不小于在它之前的数。
        /*
            对于所有评测用例,1 ≤ K ≤ N ≤ 10^5,1 ≤ Ai ≤ 10^6。
         */
        Scanner scanner = new Scanner(System.in);
        //  长度为 N  , 将其中连续的 K 个数修改成任意一个相同值
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        int arrA [] = new int[N];
        for (int i = 0; i<N;i++){
            arrA[i] = scanner.nextInt();
        }
        scanner.close();
        // 重点 :  LNDS:longest non-decreasing subsequence
        int initLNDS = computeLNDS(arrA);
        int maxLNDS = initLNDS;
        // ----------------------------------------------
        for (int i = 0; i <= N-K;i++){
            int [] original = Arrays.copyOfRange(arrA,i,i+K);
            int uniqueVals [] = Arrays.stream(arrA).distinct().toArray();
            for (int value : uniqueVals){
                for (int j = i;j<i+K;j++){
                    arrA[j] = value;
                }
                int modifiedLNDS = computeLNDS(arrA);
                maxLNDS = Math.max(maxLNDS,modifiedLNDS);
            }
            System.arraycopy(original,0,arrA,i,K);
        }
        System.out.println(maxLNDS);
    }

    /**
     *
     * @param array
     * @return
     */
    private static int computeLNDS(int[] array) {
        int [] dp_computeLNDS = new int[array.length];
        int length = 0;
        for (int num : array){
            int pos = Arrays.binarySearch(dp_computeLNDS,0,length,num);
            if (pos < 0){
                pos = -(pos + 1);
            }
            dp_computeLNDS[pos] = num;
            if (pos == length){
                length++;
            }
        }
        return length;
    }
}


原文地址:https://blog.csdn.net/zwznzje/article/details/142414209

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!