当前位置：首页 > news >正文

第十六次CCF-CSP认证（含C++源码）

news 来源：原创 2025/8/3 13:14:00

第十六次CCF-CSP认证

小中大
- 满分思路
- 遇到的问题
二十四点（表达式求值）
- 难点
- 满分思路

小中大

这次我觉得是非常难的只有一道easy 做的时候看这个通过率就有点不对劲上官网看了一眼平均分 106 就是人均A一道的水准一开始看了半天第三题几乎还是下不了手这也比较能接受了哈哈
能把前两道拿满已经非常不错啦~
在这里插入图片描述

题目链接

满分思路

//基本思路：对于一个升序或者降序的数组，它的最大值最小值总是能在端点处找到
//那对于中位数我们需要对输入的n进行判断，如果是偶数则取中间两个数的平均值
//所以这题为了方便，我们for循环读入的时候最好是从1开始的，那这样的话中间的数字的下标就是（n+1）/ 2

遇到的问题

其实一开始我写的时候，我用的是整型来存储中位数，根据中位数的计算规则是很有可能涉及到除法的，那用整型来存明显是不合适的也就是没有考虑到中位数可能是小数的情况，
那可以改用double或者float
然后对于输出的时候需要对于mid进行判断就好了

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int s[N];int main() {int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> s[i];}int minVal, maxVal;double mid;if (s[n] > s[1]) {maxVal = s[n];minVal = s[1];} else {maxVal = s[1];minVal = s[n];}int x = n / 2;if (n % 2 == 0) {mid = (s[x] + s[x + 1]) / 2.0;} else {mid = s[(n + 1) / 2];}double little = mid - (int)mid;if (little == 0) {cout << maxVal << ' ' << (int)mid << ' ' << minVal;} else {cout << maxVal << ' ' << mid << ' ' << minVal;}return 0;
}

二十四点（表达式求值）

其实这个题目的基础模版就是我们在学习栈的过程中学习到的表达式求值
懒猫老师的视频讲解
在这里插入图片描述
题目链接

难点

1. 运算符优先级处理（比较难以想到）
在算术运算里，不同运算符有着不同的优先级，像乘法和除法的优先级就高于加法和减法。要正确计算表达式的值，就必须依据运算符的优先级来确定运算顺序。例如在表达式 3 + 2 * 4 中，得先计算 2 * 4，再将结果与 3 相加。
在代码实现时，得有一种机制去判断当前运算符和栈顶运算符的优先级，从而决定是立即进行运算，还是把当前运算符压入栈中。像代码里借助 unordered_map 来存储运算符优先级，再在处理运算符时比较优先级，这就是为了解决此难点。
1. 括号匹配与处理
括号能够改变运算的优先级，所以需要正确处理括号内的子表达式。遇到左括号时，要把它压入操作符栈，等遇到右括号时，就得从操作符栈中弹出运算符并进行运算，直至遇到对应的左括号。
例如在表达式 (3 + 2) * 4 中，得先计算括号内的 3 + 2，再将结果与 4 相乘。代码里通过 while(op.top() != ‘(’) eval(); 这一循环来处理括号内的运算，保证括号内的表达式优先计算。
1. 栈的使用与状态管理
使用栈来存储运算符和数字时，要保证栈的状态在整个计算过程中是正确的。每次运算时，得从栈中正确取出元素，运算结束后又要把结果正确压入栈中。而且在处理每个新的测试用例之前，要清空栈，保证各个测试用例之间的计算互不干扰。
代码里通过 op = stack(); 和 num = stack(); 来清空栈，确保每次测试用例开始时栈为空。

满分思路

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <unordered_map>using namespace std;// 定义操作符栈，用于存储运算符
stack<char> op; 
// 定义数字栈，用于存储运算过程中的数字
stack<int> num; // 该函数用于执行具体的运算操作
// 从数字栈中取出两个数字，从操作符栈中取出一个运算符，进行相应的运算，并将结果压入数字栈
void eval()
{// 取出数字栈顶的数字，作为运算的第二个操作数auto b = num.top(); num.pop();// 取出数字栈顶的数字，作为运算的第一个操作数auto a = num.top(); num.pop();// 取出操作符栈顶的运算符auto c = op.top(); op.pop();int x;// 根据运算符进行相应的运算if(c == '+') x = a + b;else if(c == '-') x = a - b;else if(c == 'x') x = a * b;else x = a / b;// 将运算结果压入数字栈num.push(x);
}int main()
{int T;// 读取测试用例的数量cin >> T;// 循环处理每个测试用例while (T -- ){string s;// 读取当前测试用例的表达式cin >> s;// 清空操作符栈，确保每次测试用例开始时栈为空op = stack<char>();// 清空数字栈，确保每次测试用例开始时栈为空num = stack<int>();// 定义运算符的优先级，使用无序映射存储// 其中 '+' 和 '-' 的优先级为 1，'x' 和 '/' 的优先级为 2unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'x', 2}, {'/', 2}}; // 遍历输入的表达式字符串for(int i = 0; i < s.size(); i ++ ){// 如果当前字符是数字if(isdigit(s[i])) {// 用于记录当前数字的起始位置int j = i;// 用于存储当前数字的值int x = 0;// 连续读取数字字符，将其转换为整数while(isdigit(s[j]) && j < s.size())x = x * 10 + s[j ++ ] - '0';// 将转换后的整数压入数字栈num.push(x);// 更新循环变量 i，跳过已经处理的数字字符i = j - 1;}// 如果当前字符是左括号else if(s[i] == '(') {// 将左括号压入操作符栈op.push(s[i]);}// 如果当前字符是右括号else if(s[i] == ')') {// 不断进行运算，直到遇到左括号while(op.top() != '(') eval();// 弹出左括号op.pop(); }// 如果当前字符是运算符else {// 当操作符栈不为空，栈顶不是左括号，且栈顶运算符优先级大于等于当前运算符优先级时// 先进行运算，以保证高优先级运算符先计算while(op.size() && op.top() != '(' && pr[op.top()] >= pr[s[i]]) eval();// 将当前运算符压入操作符栈op.push(s[i]);}}// 处理操作符栈中剩余的运算符，完成所有运算while(op.size()) eval();// 判断最终的运算结果是否等于 24if(num.top() == 24) puts("Yes");else puts("No");}return 0;
}

第十六次CCF-CSP认证

小中大

满分思路

遇到的问题

二十四点（表达式求值）

难点

满分思路

相关文章：