【C++练习】2022年蓝桥杯第二次选拔赛

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

前言A: 单调数列

C++Java B: 最大连续1的个数

C++Java C: 祖玛游戏

Java D: 因数

Python E: 计算24

PythonJava F: 子集和

C++PythonJava 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
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
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< 
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
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>>s;
    for(char c:s){
        add_st(c);
        if(checked())
            top -= k;
    }
    for (int i = 1;i<=top;++i)
        cout< 
值得学习！ 
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 set = new HashSet();
        for (char c : s.toCharArray()) {
            set.add(c);
        }
        ArrayList 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
         
        
       
       
        n=2^a* 3^b∗5^c
       
      
     n=2a∗3b∗5c，求出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
          
         
        
       
       
        2^{n−1}
       
      
     2n−1。所以我们答案为
     
      
       
        
         
          ∑
         
         
          1
         
         
          n
         
        
        
         a
        
        
         [
        
        
         i
        
        
         ]
        
        
         ∗
        
        
         
          2
         
         
          
           n
          
          
           −
          
          
           1
          
         
        
       
       
        ∑_1^na[i]∗2^{n−1}
       
      
     ∑1na[i]∗2n−1时间复杂度：O(n) 
C++ 
#pragma Gcc optimize(3,"inline","Ofast");
#include
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< 
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
        
        
         ]
        
       
       
        dp[i][j]
       
      
     dp[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
        
        
         ]
        
       
       
        dp[i][j]=max(dp[i-1][j],dp[i-1][(j-a[i]%k+k)%k]+a[i])
       
      
     dp[i][j]=max(dp[i−1][j],dp[i−1][(j−a[i]时间复杂度：O(n*k) 
C++ 
#pragma Gcc optimize(3,"inline","Ofast");
#include
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< 
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
         
         
          )
         
        
        
         num1*(q-p)
        
       
      num1∗(q−p),则购买的花费为一个等差数列：
      
       
        
         
          n
         
         
          u
         
         
          m
         
         
          1
         
         
          ∗
         
         
          （
         
         
          q
         
         
          −
         
         
          p
         
         
          ）
         
         
          (
         
         
          p
         
         
          +
         
         
          q
         
         
          −
         
         
          1
         
         
          )
         
         
          /
         
         
          2
         
        
        
         num1*（q-p）(p+q-1)/2
        
       
      num1∗（q−p）(p+q−1)/2，然后优先队列中压入{q,num1+num2};否则就购买便宜的那一类树苗，花费也是一个等差数列。
 最终可能所有的树苗价格都是一样的，我们只需要用等差数列就可以计算出花费了。
  时间复杂度：O(n*log(n))  
C++ 
#pragma Gcc optimize(3,"inline","Ofast");
#include
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< 
 
 
加油! 
感谢! 
努力!

【C++练习】2022年蓝桥杯第二次选拔赛

Java相关栏目本月热门文章