21xrx.com
2024-06-03 06:54:31 Monday
登录
文章检索 我的文章 写文章
2021年蓝桥杯C++中级组真题与答案
2023-07-06 10:19:29 深夜i     --     --
蓝桥杯 2021年 C++ 中级组 真题 答案

蓝桥杯是中国知名的计算机竞赛，分为初赛、复赛和总决赛三个阶段。其中初赛参加人数最多，每年数十万人次参赛。2021年的蓝桥杯中级组比赛已经结束，本文将为大家介绍一下2021年蓝桥杯C++中级组的真题及参考答案。

第一题：数学公式计算

题目描述：

输入一个数学公式，包含+$,-,*,/,^,(,)$六种运算符和无数个数字，求出最终结果并输出，保留两位小数。其中$+$,$-$,$*$,$/$的优先级与数学中规定的优先级相同，即先算乘除，后算加减；$^$表示幂运算。

输入格式：

输入一行包含一个数学公式，其中运算符和数字之间均以空格隔开。

输出格式：

输出该公式的运算结果，保留两位小数。

样例输入：

$1\ +\ 2\ *\ 3\ ^\ 2\ -\ 3\ +\ 4\ /\ 2$

样例输出：

$19.00$

解题思路：

本题需要使用栈来进行运算符的优先级判断和计算。将输入的字符串按照空格分隔开，依次遍历字符串中的每个元素，如果是数字则直接将其压入数字栈。如果是运算符，则需要进行运算。我们可以将当前运算符与运算符栈栈顶元素的优先级进行比较，如果当前运算符大于栈顶元素，则直接将当前运算符入栈，否则取出栈中运算符和数字进行运算，并将结果再次压入数字栈，直到当前运算符可以入栈为止。在遍历完整个字符串后，将栈中剩余的运算符和数字进行计算，最终得到结果。

参考代码：

 c++

#include <iostream>


#include <string>


#include <stack>


#include <iomanip>


using namespace std;


// 判断运算符优先级


bool is_higher_priority(char op1, char op2)


{


  int p1, p2; // 运算符优先级：+,- = 0，*，/ = 1，^ = 2


  switch (op1)


  {


    case '+':


    case '-':


      p1 = 0;


      break;


    case '*':


    case '/':


      p1 = 1;


      break;


    case '^':


      p1 = 2;


      break;


  }


  switch (op2)


  {


    case '+':


    case '-':


      p2 = 0;


      break;


    case '*':


    case '/':


      p2 = 1;


      break;


    case '^':


      p2 = 2;


      break;


  }


  return p1 >= p2;


}


int main()


{


  stack<double> nums; // 数字栈


  stack<char> ops; // 运算符栈


  string str; // 输入的字符串


  double num; // 当前数字


  char op; // 当前运算符


  getline(cin, str);


  for (int i = 0; i < str.length(); )


  {


    if (isdigit(str[i])) // 如果是数字，则将其转换成数字并压入数字栈


    {


      num = str[i++] - '0';


      while (i < str.length() && isdigit(str[i]))


      {


        num = num * 10 + str[i++] - '0';


      }


      nums.push(num);


    }


    else if (str[i] != ' ') // 如果是运算符，则从运算符栈中取出元素进行运算，并将结果压入数字栈


    {


      op = str[i++];


      while (!ops.empty() && is_higher_priority(ops.top(), op)) // 只要运算符栈不为空，且栈顶元素的优先级大于等于当前运算符，则取出元素进行运算


      {


        double num1 = nums.top();


        nums.pop();


        double num2 = nums.top();


        nums.pop();


        char c = ops.top();


        ops.pop();


        double result; // 计算结果


        switch (c) // 根据运算符进行计算


        {


          case '+':


            result = num2 + num1;


            break;


          case '-':


            result = num2 - num1;


            break;


          case '*':


            result = num2 * num1;


            break;


          case '/':


            result = num2 / num1;


            break;


          case '^':


            result = pow(num2, num1);


            break;


        }


        nums.push(result); // 将计算结果压入数字栈


      }


      ops.push(op); // 将当前运算符压入运算符栈


    }


    else // 如果是空格，则直接跳过


    {


      i++;


    }


  }


  // 计算最终结果


  while (!ops.empty())


  {


    double num1 = nums.top();


    nums.pop();


    double num2 = nums.top();


    nums.pop();


    char c = ops.top();


    ops.pop();


    double result;


    switch (c)


    {


      case '+':


        result = num2 + num1;


        break;


      case '-':


        result = num2 - num1;


        break;


      case '*':


        result = num2 * num1;


        break;


      case '/':


        result = num2 / num1;


        break;


      case '^':


        result = pow(num2, num1);


        break;


    }


    nums.push(result);


  }


  cout << fixed << setprecision(2) << nums.top();


  return 0;


}

第二题：序列操作

题目描述：

给定一个数列$A$，支持两种操作，一种是将$A$中的所有元素都加上一个值$x$（$-10^4\le x\le 10^4$），另一种是查询一个数列区间$[l,r]$之间的最大值。

输入格式：

第一行是数列$A$的长度$n$（$1\le n\le 10^5$），第二行是$n$个数（$-10^9\le a_i\le 10^9$）。接下来的一行是操作次数$Q$（$1\le Q\le 10^5$），接下来$Q$行，每行对应一次操作，这些操作均为上述两种操作之一，其中$x\in[-10^4,10^4]$，查询操作中的$l,r$均满足$1\le l\le r\le n$。

输出格式：

对于每次查询操作，输出区间$[l,r]$之间的最大值。

样例输入：

5

1 2 3 4 5

2

1 2 4

2 3 5

样例输出：

$4\ 5$

解题思路：

本题需要使用线段树来维护区间操作，并查询区间最大值。线段树是一种二叉树结构，并且满足根节点表示整个区间，左右子树分别表示区间的左半部分和右半部分。根据题目要求，我们需要实现两个操作：$update$ 和 $query$。其中，$update$ 表示将区间$[L,R]$中的元素加上$x$，$query$ 表示查询区间$[L,R]$中的最大值。

参考代码：

 c++

#include <iostream>


#include <algorithm>


using namespace std;


const int N = 1e5 + 10;


int a[N], cnt;


struct Node


r;


  int maxn;


  int add;


tr[N * 4];


// 建树


void build(int u, int l, int r)


{


  tr[u] = -0x3f3f3f3f;


  if (l == r)


  {


    tr[u].maxn = a[l];


  }


  else


  {


    int mid = l + r >> 1;


    build(u << 1, l, mid);


    build(u << 1 | 1, mid + 1, r);


    tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);


  }


}


// 下传标记


void pushdown(int u)


{


  tr[u << 1].add += tr[u].add;


  tr[u << 1 | 1].add += tr[u].add;


  tr[u << 1].maxn += tr[u].add;


  tr[u << 1 | 1].maxn += tr[u].add;


  tr[u].add = 0;


}


// 区间修改


void modify(int u, int l, int r, int x)


{


  if (tr[u].l >= l && tr[u].r <= r)


  {


    tr[u].maxn += x;


    tr[u].add += x;


    return;


  }


  pushdown(u);


  int mid = tr[u].l + tr[u].r >> 1;


  if (l <= mid)


    modify(u << 1, l, r, x);


  if (r > mid)


    modify(u << 1 | 1, l, r, x);


  tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);


}


// 区间查询


int query(int u, int l, int r)


{


  if (tr[u].l >= l && tr[u].r <= r)


  {


    return tr[u].maxn;


  }


  pushdown(u);


  int res = -0x3f3f3f3f;


  int mid = tr[u].l + tr[u].r >> 1;


  if (l <= mid)


    res = max(res, query(u << 1, l, r));


  if (r > mid)


    res = max(res, query(u << 1 | 1, l, r));


  return res;


}


int main()


{


  int n;


  cin >> n;


  for (int i = 1; i <= n; i++)


    scanf("%d", &a[i]);


  build(1, 1, n);


  int q;


  cin >> q;


  while (q--)


  {


    int op, l, r, x;


    scanf("%d", &op);


    if (op == 1) // 区间加


    {


      scanf("%d%d%d", &l, &r, &x);


      modify(1, l, r, x);


    }


    else // 区间查询


    {


      scanf("%d%d", &l, &r);


      printf("%d ", query(1, l, r));


    }


  }


  return 0;


}

第三题：分糖果

题目描述：

给定$n$个小朋友和$m$颗糖果，每位小朋友都有一个糖果期望值$a_i$（$0\le a_i\le 2\times 10^9$），每颗糖果有一个吸引指数$x_i$（$0\le x_i\le 2\times 10^9$）。你可以将一颗糖果分配给一个小朋友，使得分配给这名小朋友的糖果吸引指数与该小朋友的糖果期望值的差的绝对值最小，求所有小朋友吸引指数与其分配到的糖果吸引指数之差的绝对值之和。

输入格式：

第一行是两个数$n,m$，表示小朋友和糖果的数量，接下来一行是$n$个数$a_i$，表示每名小朋友的糖果期望值，接下来一行是$m$个数$x_i$，表示每颗糖果的吸引指数。

输出格式：

输出所有小朋友吸引指数与其分配到的糖果吸引指数之差的绝对值之和。

样例输入：

3 3

1 2 3

1 2 3

样例输出：

$2$

解题思路：

本题需要使用贪心算法来求解若干个小朋友和若干个糖果之间的最优匹配。具体的算法思路为：先将所有糖果按照吸引指数从小到大进行排序，再将所有小朋友按照糖果期望值从小到大进行排序。然后，我们依次将每个糖果分配给离其期望值最近的小朋友，直到所有糖果都被分配完为止。

参考代码：

 c++

#include <iostream>


#include <algorithm>


#include <vector>


using namespace std;


const int N = 1e5 + 10;


// 小朋友


struct Child


  int exp; // 糖果期望值


  int idx; // 下标


;


// 糖果


struct Candy


  int attr; // 吸引指数


  int idx; // 下标


;


bool cmp1(Candy a, Candy b)


  return a.attr < b.attr;


bool cmp2(Child a, Child b)


  return a.exp < b.exp;


int main()


{


  int n, m;


  cin >> n >> m;


  vector<Candy> c(m); // 糖果数组


  vector<Child> ch(n); // 小朋友数组


  for (int i = 0; i < n; i++)


  {


    scanf("%d", &ch[i].exp);


    ch[i].idx = i; // 保存小朋友下标


  }


  for (int i = 0; i < m; i++)


  {


    scanf("%d", &c[i].attr);


    c[i].idx = i; // 保存糖果下标


  }


  sort(c.begin(), c.end(), cmp1); // 按吸引指数升序排列


  sort(ch.begin(), ch.end(), cmp2); // 按糖果期望值升序排列


  vector<pair<int, int>> ans(m); // 记录所有小朋友拿到的糖果


  int ptr = 0; // 记录当前分配给第 i 个小朋友的糖果


  // 贪心求解


  for (int i = 0; i < n; i++)


  {


    while (ptr < m && c[ptr].attr < ch[i].exp)


    {


      ptr++;


    }


    if (ptr == m) break; // 如果所有糖果都已经被分配完毕，则直接退出循环


    int diff = abs(ch[i].exp - c[ptr].attr); // 计算当前小朋友与当前糖果的吸引指数差的绝对值


    ans[c[ptr].idx] = {ch[i].idx + 1, diff}; // 记录当前糖果分配给哪个小朋友，并记录差的绝对值


    ptr++;


  }


  // 输出答案


  int res = 0;


  for (int i = 0; i < m; i++)


  {


    if (ans[i].first > 0)


      res += ans[i].second;


  }


  cout << res << endl;


  return 0;


}
  
  

评论区

{{item['qq_nickname']}}
()
回复
回复