开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【C++练习】2022年蓝桥杯第二次选拔赛 -> 正文阅读

[数据结构与算法]【C++练习】2022年蓝桥杯第二次选拔赛

【C++练习】蓝桥杯选拔赛

前言
A: 单调数列
- C++
- Java
B: 最大连续1的个数
- C++
- Java
C: 祖玛游戏
- Java
D: 因数
- Python
E: 计算24
- Python
- Java
F: 子集和
G: 最大整除
- C++
H: 种树
- C++

前言

写此篇仅为练习C++，刚好练练手，C++代码来源宋神sqr，研究大佬的C++代码，致谢！

附: 2022年蓝桥杯第一次选拔赛

A: 单调数列

题目描述
如果数组是单调递增或单调递减的，那么它是单调的。如果对于所有 i <= j，nums[i] <= nums[j]，那么数组 nums 是单调递增的。 如果对于所有 i <= j，nums[i]> = nums[j]，那么数组 nums 是单调递减的。当给定的数组 nums 是单调数组时输出"YES"，否则输出"NO"。

输入
第一行输入一个正整数n表示数组大小(1<=n<=100000)
第二行输入n个[1,100000000]整数

输出
当给定的数组 nums 是单调数组时输出"YES"，否则输出"NO"。
	
样例输入
4
4 3 2 1 

样例输出
YES

题解：

简单题，数组读入之后，判断是否是顺序和逆序。
时间复杂度：O(n)

C++

#pragma Gcc optimize(3,"inline","Ofast");
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
#define int ull
int a[1000010];
 
signed main(){
    ios::sync_with_stdio(0);
    int n;cin>>n;
    for(int i = 1;i<=n;++i)
        cin>>a[i];
    bool rs = true;
    for(int i = 2;i<=n;++i)
        if(a[i] < a[i - 1])
            rs = false;
    if(rs) cout<<"YES";
    else{
        bool rs = true;
        for(int i = 2;i<=n;++i)
            if(a[i] > a[i - 1])
                rs = false;
        if(rs) cout<<"YES";
        else cout<<"NO";
    }
}

Java

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int flag = -1;
        boolean f = true;
        int pre = sc.nextInt();
        while (n-- > 1) {
            int x = sc.nextInt();
            if (flag == -1) {
                if (x < pre) {
                    flag = 1;  // jian
                } else {
                    flag = 0;  // zeng
                }
            } else {
                if (flag == 1) {
                    if (x > pre) {
                        f = false;
                        break;
                    }
                } else {
                    if (x < pre) {
                        f = false;
                        break;
                    }
                }
            }
            pre = x;
        }
        if (f)
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}

B: 最大连续1的个数

题目描述

给定一个正整数n，请你计算n在二进制表示下最大连续1的个数。例如：正整数55的二进制表示为110111，则答案为3。	

输入
输入一个正整数n(1<=n<=1e9)	

输出
输出n在二进制表示下最大连续1的个数	

样例输入
55

样例输出
3

题解：

读入之后，将数转为二进制，循环判断连续的1的个数，取最大值，别忘了在循环外面再去一次最大值
时间复杂度：O(log(n))

C++

#pragma Gcc optimize(3,"inline","Ofast");
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
#define int ull
 
signed main(){
    ios::sync_with_stdio(0);
    int a;cin>>a;
    int con = 0,mx = 0;
    while(a){
        if(a % 2 == 1)
        {
            con++;
            mx = max(mx,con);
        }
        else con = 0;
        a /= 2;
    }
    cout<<mx;
}

max(mx,con);：判断最大值

Java

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        int res = 0;
        int max = 0;
        while (n > 0) {
            if (n % 2 == 1) {
                res++;
            } else {
                res = 0;
            }
            max = Math.max(max, res);
            n >>= 1;
        }
        System.out.println(max);
    }
}

C: 祖玛游戏

题目描述

给你一个只含有小写字母的字符串s，请你从左至右在 s 中选择第一个 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。在执行完所有删除操作后，输出最终得到的字符串。

输入
整数k和字符串s,(2<=k<=5,1<=|s|<=1000000)	

输出
输出执行完所有删除操作后最终得到的字符串。

样例输入
3
deeedbbcccbdaa

样例输出
aa

题解：

利用栈压入字符串，若栈顶的k个元素相同，则将这k个元素弹出。可以采用数组模拟栈，然后直接操作栈里面的元素。
时间复杂度：O(log(n))

#pragma Gcc optimize(3,"inline","Ofast");
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
#define int ull
char st[10000100];
int top = 0,k = 0;
 
void add_st(char x){
    st[++top] = x;
}
 
bool checked(){
    if(top < k) return false;
    for(int j = 1;j<k;++j)
        if(st[top] != st[top - j])
            return false;
    return true;
}
 
signed main(){
    ios::sync_with_stdio(0);
    string s;
    cin>>k>>s;
    for(char c:s){
        add_st(c);
        if(checked())
            top -= k;
    }
    for (int i = 1;i<=top;++i)
        cout<<st[i];
}

值得学习！

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        String s = sc.next();
        Set<Character> set = new HashSet();
        for (char c : s.toCharArray()) {
            set.add(c);
        }
        ArrayList<String> arr = new ArrayList<>();
        for (char c : set) {
            String x = "";
            for (int i = 0; i < k; i++) {
                x+=c;
            }
            arr.add(x);
        }
        boolean flag = true;
     
        while (true) {
            flag = false;
            for (String ss: arr) {
                if (s.contains(ss)) {
                    s = s.replace(ss, "");
                    flag = true;
                }
            }
            if (!flag)
                break;
        }
        System.out.println(s);
    }
}

D: 因数

题目描述

给定正整数n，n只能被素因子2、3、5整除，请你求出正整数n能被2整除的因数个数。例如：n=6，6的因数为：1、2、3、6。答案为2。

输入
正整数n（1<=n<=1e16)	

输出
求出正整数n能被2整除的因数个数	

样例输入
6

样例输出
2

题解：

因为n只是由素因子2、3、5组成，即 $n=2^a* 3^b?5^c$ ，求出a、b、c。题中问的是n的因数中能被2整除的个数，所以答案为a*(b+1)*(c+1)
时间复杂度：O(log(n))

Python

n = eval(input())
b = n
m = {2:0,3:0,5:0}
while n != 1:
  if n % 2 == 0:
    m[2] += 1
    n //= 2
  if n % 3 == 0:
    m[3] += 1
    n //= 3
  if n % 5 == 0:
    m[5] += 1
    n //= 5
print((m[2]) * (m[3] + 1) * (m[5] + 1))

统计次数！

E: 计算24

题目描述

游戏规则是：对4个 1～10 之间的正整数，进行加、减、乘三种运算，要求运算结果等于二十四。乘法的优先级高于加、减，并且算式中不可以用括号，不可以改变4个数字出现的顺序。例如：若给出的 44个操作数是：10、2、4、8，则有2种可能的解答方案：10+2+4+8=24，10*2-4+8=24。现在给你4个1～10 之间的正整数，请你计算解答方案数。

输入
4个 1～10 之间的正整数	

输出
输出方案总数	

样例输入
10 2 4 8

样例输出
2

题解：

1、列举27种可能的计算表达式
2、DFS加表达式求值
使用深度优先搜索跑出所有的表达式，然后利用栈来处理表达式，计算答案。

Python

s = input().split(" ")
s = list(s)
st = {'+','-','*'}
rs = 0
for a in st:
  for b in st:
    for c in st:
      if eval(s[0] + a + s[1] + b + s[2] + c + s[3]) == 24:
        rs += 1
print(rs)

Java

import java.util.Scanner;
 
public class Main {
    static int max = 0;
    static int[] x;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        x = new int[4];
        for (int i = 0; i < 4; i++) {
            x[i] = sc.nextInt();
        }
        dfs(0, "");
        System.out.println(max);
    }
    public static void dfs(int i, String cur) {
        if (i == 3) {
            int res = 0;
            if (!cur.contains("*")) {
                res = x[0];
                for (int j = 0; j < 3; j++) {
                    if (cur.charAt(j) == '+') {
                        res += x[j+1];
                    } else {
                        res -= x[j+1];
                    }
                }
            } else {
     
                if (cur.charAt(0) == '*' && cur.charAt(2) == '*' && cur.charAt(1) == '*')
                    res = x[0]*x[1]*x[2]*x[3];
                else if (cur.charAt(0) == '*' && cur.charAt(1) == '*') {
                    res = x[0]*x[1]*x[2];
                    if (cur.charAt(2) == '+')
                        res += x[3];
                    else
                        res -= x[3];
                } else if (cur.charAt(0) == '*' && cur.charAt(2) == '*') {
                    res = x[0]*x[1];
                    if (cur.charAt(1) == '+')
                        res += x[2]*x[3];
                    else
                        res -= x[2]*x[3];
                }  else if (cur.charAt(1) == '*' && cur.charAt(2) == '*') {
                    res = x[1]*x[2]*x[3];
                    if (cur.charAt(0) == '+')
                        res += x[0];
                    else
                        res = x[0]-res;
                } else if (cur.charAt(0) == '*') {
                    res = x[0]*x[1];
                    if (cur.charAt(1) == '+')
                        res += x[2];
                    else
                        res -= x[2];
                    if (cur.charAt(2) == '+')
                        res += x[3];
                    else
                        res -= x[3];
                } else if (cur.charAt(1) == '*') {
                    res = x[1]*x[2];
                    if (cur.charAt(0) == '+')
                        res += x[0];
                    else
                        res = x[0] - res;
                    if (cur.charAt(2) == '+')
                        res += x[3];
                    else
                        res -= x[3];
                } else if (cur.charAt(2) == '*') {
                    res = x[2]*x[3];
                    if (cur.charAt(1) == '+')
                        res += x[1];
                    else
                        res = x[1] - res;
                    if (cur.charAt(0) == '+')
                        res += x[0];
                    else
                        res = x[0]-res;
                }
             
            }
            if (res == 24) {
                max++;
            }
             
            return;
        }
        dfs(i+1, cur+"+");
        dfs(i+1, cur+"-");
        dfs(i+1, cur+"*");
    }
}

利用栈来处理表达式~

F: 子集和

题目描述

给你一个元素个数不超过30的整数集合，请你计算该集合所有子集的元素之和。例如集合{1，4}，则该集合的子集共四个{{空集}、{1}、{4}、{1、4}}，则子集的元素之和为1+4+1+4=10。

输入
第一行一个正整数n（1<=n<=30)
第二行n个大小在[1,1000000]范围内的正整数

输出
输出给定集合所有子集的元素之和	

样例输入
2 
1 4 

样例输出
10

题解：

考虑每个数对答案的贡献，即考虑每个数被选出来后可能出现在多少个集合中，若现在有n个数，选出来一个数后，余下（n-1）个数的子集个数为 $2^{n?1}$ 。所以我们答案为 $_1^na[i]?2^{n?1}$
时间复杂度：O(n)

C++

#pragma Gcc optimize(3,"inline","Ofast");
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
#define int ull
int a[10000100];
int n;
 
signed main(){
    ios::sync_with_stdio(0);
    cin>>n;
    int sum = 0;
    for(int i = 1;i<=n;++i){
        cin>>a[i];
        sum += a[i];
    }
    cout<<sum * (((ull)1) << (n - 1));
}

Python

n = eval(input())
s = input().split(" ")[0:-1]
s = list(map(int,s))
print(sum(s) * (2 ** (n - 1)))

Java

import java.util.Scanner;
 
public class Main {
    static int x[];
    static int k, n;
    static long max = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        x = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
        }
        dfs(0, 0);
         
        System.out.println(max);
    }
    public static void dfs(int i, long cur) {
        if (i == n) {
            max += cur;
            return;
        }
        dfs(i+1, cur+x[i]);
        dfs(i+1, cur);
    }
}

G: 最大整除

题目描述
给你一个正整数k和一个整数数组 a，请你求出能被k整除的元素最大和。	

输入
第一行两个正整数n和k，分别表示数组大小和题目中的k。（1<=n<=40000,2<=k<=20)
第二行n个[1,1000000]范围内的整数

输出
输出能被k整除的元素最大和。	

样例输入
5 3 
3 6 5 1 8

样例输出
18

提示
样例中选择3、6、1、8，3+6+1+8=18

题解：

本题解法为动态规划： $d p [i] [j]$ 表示前i个元素中我选取出来的数的和对k取模为j的最大值。
若当前元素为a[i],则有两种情况选或者不选。则 $d p [i] [j] = m a x (d p [i ? 1] [j], d p [i ? 1] [(j ? a [i]$
时间复杂度：O(n*k)

C++

#pragma Gcc optimize(3,"inline","Ofast");
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
 
int n,k,a[40010];
int dp[40010][21];
 
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>k;
    for(int i = 1;i<=n;++i)
        cin>>a[i];
    int w;
    memset(dp,-0x3f,sizeof dp);
    dp[0][0] = 0;
    for(int i = 1;i<=n;++i){
        w = a[i] % k;
        for(int j = 0;j < k;++j){
            dp[i][j] = max(dp[i - 1][((j - w) + k) % k] + a[i],dp[i - 1][j]);
        }
    }
    cout<<dp[n][0]<<"\n";
}

H: 种树

题目描述

A市为了响应国家碳达峰碳中和目标要求，欲购买一批树苗来净化A市的空气。现有n个树苗厂家，每个厂家有一个初始树苗单价（单位元），每购买一颗树苗后，树苗单价都会上涨1元。现需要购买m颗树苗，问最少需要多少元。	

输入

第一行两个正整数n和m（1<=n<=100000,1<=m<=1e10）
第二行n个[1,10]范围内的整数表示树苗厂家初始树苗单价。

输出
购买m颗树苗的最小花费	

样例输入
3 6 
1 2 3 

样例输出
14

题解：

本题考虑优先队列：但不能暴力使用优先队列，我们需要把相同价格的树苗合并。我们肯定优先购买便宜的树苗，假设最便宜的两种树苗价格和厂家数量分别为p,num1和q,num2。
若当前购买需求大于 $n u m 1 ? (q ? p)$ ,则购买的花费为一个等差数列： $n u m 1 ? （ q ? p ） (p + q ? 1) / 2$ ，然后优先队列中压入{q,num1+num2};否则就购买便宜的那一类树苗，花费也是一个等差数列。
最终可能所有的树苗价格都是一样的，我们只需要用等差数列就可以计算出花费了。
时间复杂度：O(n*log(n))

C++

#pragma Gcc optimize(3,"inline","Ofast");
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
#define int ull
 
int n,m,a[1000010];
int sum = 0,cost = 0;
 
int get(int a,int b){
    return (a + b) * (b - a + 1) / 2;
}
 
int getval(int i,int val,int need){
    int rss = 0;
    int k = need / i;
    rss += get(val,val + k - 1) * i;
    val = val + k;
    k = need % i;
    rss += val * k;
    return rss;
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for (int i = 1;i<=n;++i)
        cin>>a[i];
    a[n + 1] = 4e18;
    sort(a + 1,a + n + 1);
    for(int i = 1;i<=n;++i){
        if(sum + (a[i + 1] - a[i]) * i >= m){
            cost += getval(i,a[i],m - sum);
            cout<<cost;
            return 0;
        }else{
            sum += (a[i + 1] - a[i]) * i;
            cost += i * get(a[i],a[i + 1] - 1);
        }
    }
    cost += getval(n,a[n],m - sum);
    cout<<cost;
}