2024 1-12

张

张建站

2026/7/6 21:32:15

10分钟阅读

【题目信息】1.餐费结算【新知识点】#include iostream // C输入输出#include cstdio // C输入输出---格式化更加方便 scanf(%lf, x);【易错点】【代码】#include iostream #include cstdio #include algorithm using namespace std; int main() { double cost, cheap; cin cost cheap; // 折扣 double rate 1.0; if (cost 200 cost 400) rate 0.95; else if (cost 400 cost 600) rate 0.9; else if (cost 600 cost 800) rate 0.85; else if (cost 800) rate 0.8; double discount_pay cost * rate; // 优惠券 double coupon_pay cost - min(cheap, cost/2); // 取最小值 double final_pay min(discount_pay, coupon_pay); printf(%.2lf, final_pay); return 0; }【题目信息】2.最终成绩【新知识点】【易错点】【代码】struct student{ double pingshi; double qimo; double bili; }; int main(){ int n; student arr[1000]; cinn; for(int i0;in;i){ cinarr[i].pingshiarr[i].qimoarr[i].bili; } for(int i0;in;i){ printf(%.2lf\n,arr[i].pingshi*arr[i].bili/100arr[i].qimo*(1.00-arr[i].bili/100)); } }【题目信息】3.直角三角形【新知识点】【易错点】【代码】int main(){ int n; cinn; int arr[21][21]; for(int i1;in;i){ for(int j1;ji;j){ if(ij||j1){cout*;} else if(in){cout*;} else cout ; } coutendl; } }【题目信息】4.七进制转换为十进制【新知识点】不要把七进制反转的公式混为一谈就如十进制反转一样此处只是转化没有反转就按照权重来即可【易错点】【代码】int main(){ int n; cinn; int result0; int weight1; while(n){ int tempn%10; resulttemp*weight; weight*7; n/10; } coutresult; }【题目信息】5.图像旋转【新知识点】【易错点】【代码】int main(){ int n,m; cinnm; int arr[101][101]; for(int i1;in;i){ for(int j1;jm;j){ cinarr[i][j]; } } //无非是从第一列从下往上遍历 for(int j1;jm;j){ for(int in;i1;i--){ coutarr[i][j]; } coutendl; } }【题目信息】6.两个班级期末成绩中位数【新知识点】双指针合并两个有序数组// 双指针合并两个有序数组int i 0, j 0, k 0;while (i m j n) {if (A[i] B[j]) {C[k] A[i];} else {C[k] B[j];}}// 处理剩余元素while (i m) C[k] A[i];while (j n) C[k] B[j];【易错点】没有将最后得到的数组进行sort排序【代码】#include iostream #include algorithm // 包含sort函数 using namespace std; int main() { int m, n; cin m n; int A[51], B[51], C[102]; for (int i 0; i m; i) cin A[i]; for (int i 0; i n; i) cin B[i]; // 修正B数组从0开始存 // 合并并排序 for (int i 0; i m; i) C[i] A[i]; for (int i 0; i n; i) C[m i] B[i]; sort(C, C m n); // 对整个C数组排序 // 计算中位数同方法1 if ((m n) % 2 ! 0) { cout C[(m n) / 2]; } else { double result (C[(m n) / 2 - 1] C[(m n) / 2]) / 2.0; printf(%.2lf, result); } return 0; }【题目信息】7.学生注册登记【新知识点】明知这些学好都有公共的基础那么减去这个基础用来当作下标另外直接判断数组而不是一直循环查找所需要的时间复杂度都会小很多。【易错点】【代码】#include iostream using namespace std; const int MAX_N 10000; const int START_ID 20240000; int main() { int N, M; cin N M; // 静态数组N最大10000多开5个防越界 bool registered[MAX_N 5] {false}; // 1. 读入已登记学号 for (int i 0; i M; i) { int id; cin id; // 学号映射到数组下标 int idx id - START_ID; if (idx 1 idx N) { registered[idx] true; } } // 2. 输出未登记学号控制空格 bool hasMissing false; bool isFirst true; for (int i 1; i N; i) { if (!registered[i]) { if (!isFirst) { cout ; // 非第一个前面加空格 } cout START_ID i; // 输出实际学号 isFirst false; hasMissing true; } } // 3. 如果全部登记 if (!hasMissing) { cout N; } return 0; }【题目信息】8.好串【新知识点】【易错点】【代码】#include iostream #include string using namespace std; string good(string str, int number); int main() { int n; cin n; cin.ignore(); // 忽略换行符避免getline读取空行 string str; getline(cin, str); cout good(str, n); return 0; } string good(string str, int number) { int count[26] {0}; // 只需要26个小写字母的计数初始为0 int min_idx 26; // 初始化为一个较大的值如26因为a-a0z-a25 for (char c : str) { int idx c - a; // 转换为0-25的索引 count[idx]; // 计数加1 if (count[idx] 1) { // 出现重复 return No; } if (idx min_idx) { // 更新最小字符的索引 min_idx idx; } } // 检查从min_idx开始的number个连续字符是否都为1即是否连续且无缺失 for (int i 0; i number; i) { int current_idx min_idx i; if (current_idx 26 || count[current_idx] ! 1) { // 超出字母表范围或计数不为1 return No; } } return Yes; }【题目信息】9.落花清理【新知识点】这实际上就是构造哈夫曼树每个石子堆是叶子节点合并消耗父节点权重总消耗所有非叶子节点权重和哈夫曼贪心选择性质每次合并两个最小的能保证总体最小【易错点】我又把他当作动态规划来做了【代码】手动找两个最小的值#include iostream #include algorithm using namespace std; const int MAX_N 10010; int main() { int n; cin n; int arr[MAX_N]; for (int i 0; i n; i) { cin arr[i]; } int total 0; int size n; // 每次循环找最小的两个数合并 while (size 1) { // 排序每次只排前size个元素 sort(arr, arr size); // 取最小的两个 int a arr[0]; int b arr[1]; // 合并 int sum a b; total sum; // 用sum替换a删除b arr[0] sum; // 将b的位置用最后一个元素填充 arr[1] arr[size - 1]; size--; } cout total endl; return 0; }【题目信息】10.图书查询【新知识点】字符串的函数运用如果加了using namespace std; 其余就不需要std了1.std::to_string()作用将整数int, long, long long 等转换为字符串头文件string用法int a 123; string s to_string(a); // s 123注意只能用于数值类型不能用于浮点数的精确控制如保留小数位2.std::string::rfind()作用从字符串末尾开始向前查找子串返回第一次出现的起始位置从0开始语法size_t rfind(const string str, size_t pos npos) const;返回值找到 → 返回子串起始索引0 ~ length-1没找到 → 返回string::npos通常是 -1但类型是size_t不能直接和 int 比较关键点它不是只找结尾而是从后往前找第一个匹配的位置如果子串出现在中间也可能返回有效位置3.std::sort()头文件algorithm用法sort(arr, arr n); // 对前n个元素升序排序注意对long long数组排序没问题排序后第一个匹配的就是最小的因为题目要最小图书编码4.std::string::length()/size()作用返回字符串长度字符个数用法string s abc; int len s.length(); // 3注意返回值是size_t类型无符号整型和负数比较时要小心对每个需求码arr1[i]转换为字符串str_suffix遍历所有图书编码arr[j]转换为字符串str_book判断str_book是否以str_suffix结尾如果是 → 输出arr[j]标记找到跳出循环如果遍历完都没找到 → 输出 -1数学思想也很好整数结尾无非就是取余除数是多少取决于要找的数是多少位【易错点】不检查子串长度是否超过主串长度s.rfind(t) s.length() - t.length()在t比s长时会因为无符号溢出和string::npos的值相等导致错误的匹配判断。所以必须先用if (s.length() t.length())过滤掉这种情况返回的是无符号数但是在数学语言上看就是-1【代码】#include iostream #include algorithm // 用于 sort #include string // 用于 to_string 和 string using namespace std; int main() { int n, m; cin n m; long long arr[1000]; // 图书编码 long long arr1[1000]; // 需求码 // 输入图书编码 for (int i 0; i n; i) { cin arr[i]; } // 输入需求码 for (int i 0; i m; i) { cin arr1[i]; } // 从小到大排序图书编码 sort(arr, arr n); // 处理每个需求码 for (int i 0; i m; i) { string suffix to_string(arr1[i]); // 需求码转字符串 bool found false; for (int j 0; j n; j) { string book to_string(arr[j]); // 书编码转字符串 // 判断是否以 suffix 结尾 if (book.length() suffix.length() book.substr(book.length() - suffix.length()) suffix) { found true; cout arr[j] endl; // 输出最小的因为已排序 break; } } if (!found) { cout -1 endl; } } return 0; }#include iostream #include algorithm // 包含sort函数 using namespace std; // 判断整数a是否以整数b结尾的函数 bool endsWith(long long a, long long b) { // 特殊情况处理如果b是0只需判断a的个位数是否为0 if (b 0) { return (a % 10 0); // a能被10整除即以0结尾 } // 计算b的位数对应的10的幂如b45是2位数计算10^2100 long long power 1; // 存储10的b的位数次方 long long temp b; // 临时变量用于计算b的位数 // 循环计算b的位数每次循环power乘以10 while (temp 0) { power * 10; // 10^1, 10^2, 10^3, ... temp / 10; // 去掉b的最后一位继续计算 } // 循环结束后power是10的(b的位数)次方 // 例如b452位数power100 // 核心判断a除以power的余数是否等于b // 例如a12345, b45, power100 // 12345 % 100 45, 45 45 返回true return (a % power b); } int main() { int n, m; // n:图书数量, m:查询数量 cin n m; long long books[1000]; // 存储图书编码 long long queries[1000]; // 存储查询码 // 读取图书编码 for (int i 0; i n; i) { cin books[i]; } // 读取查询码 for (int i 0; i m; i) { cin queries[i]; } // 对图书编码进行升序排序 // 排序后第一个满足条件的图书就是最小编码 sort(books, books n); // 处理每个查询 for (int i 0; i m; i) { long long query queries[i]; // 当前查询的编码 bool found false; // 标记是否找到符合条件的图书 // 遍历所有图书寻找以query结尾的图书 for (int j 0; j n; j) { // 如果当前图书以query结尾 if (endsWith(books[j], query)) { // 输出该图书编码由于已排序这是最小的符合条件的编码 cout books[j] endl; found true; // 标记已找到 break; // 跳出内层循环处理下一个查询 } } // 如果遍历完所有图书都没找到 if (!found) { cout -1 endl; // 输出-1表示未找到 } } return 0; // 程序正常结束 }【题目信息】11.餐厅评分【新知识点】拓扑排序小根堆若餐厅A一定在餐厅B之前那么从顶点A到B一定有一条有向路径什么叫拓扑排序首先找到入度为0的点删除它的边之后还能找到下一个入度为0的点【易错点】核心思路邻接矩阵存储graph[i][j] 1表示 i 优于 j手动查找最小值每次在未访问节点中找入度为0的最小编号模拟拓扑排序每次选一个节点更新其后继的入度【代码】#include iostream #include cstring using namespace std; const int MAXN 505; int main() { int N, M; cin N M; // 1. 定义静态数组 int graph[MAXN][MAXN] {0}; // 邻接矩阵 int indegree[MAXN] {0}; // 入度数组 int result[MAXN]; // 结果数组 bool visited[MAXN] {false}; // 标记是否已加入结果 int result_size 0; // 结果当前大小 // 2. 读入边构建图 for (int i 0; i M; i) { int P1, P2; cin P1 P2; graph[P1][P2] 1; // P1-P2 indegree[P2]; // P2入度1 } // 3. 拓扑排序手动实现优先队列选择最小编号 for (int step 1; step N; step) { // 寻找当前入度为0且编号最小的节点 int chosen -1; for (int i 1; i N; i) { if (!visited[i] indegree[i] 0) {//当既没有加入结果 if (chosen -1 || i chosen) {//并且编号要最小的就是几个拓扑排序最在前的序号 chosen i; } } } // 如果没有找到入度为0的节点说明有环 if (chosen -1) { cout No result endl; return 0; } // 将选中的节点加入结果 visited[chosen] true; result[result_size] chosen; // 更新后继节点的入度 for (int j 1; j N; j) { if (graph[chosen][j]) { indegree[j]--; } } } // 4. 输出结果 for (int i 0; i N; i) { if (i 0) cout ; cout result[i]; } cout endl; return 0; }【题目信息】12.快递站点的设置【新知识点】dp[i][j] dp[k-1][j-1] 最后一组[k,i]dp[i][j] 前i个元素分成j组的最小代价 min{ dp[k-1][j-1] cost(k,i) }k从j到i我要分j组...好先不管前面最后那组什么样最后那组是[k,i]那前面[1,k-1]就要分j-1组前面分j-1组的最小值我知道是dp[k-1][j-1]加上最后一组的代价就是总代价尝试所有可能的k取最小的每组必须是连续的最后那组一定是某个连续区间[k,i]前面[1,k-1]自然就是分j-1组两部分独立加起来就是总代价我们不知道k是多少所以枚举所有可能的k【易错点】k从j开始确保前面有足够多的楼分成j-1组要分成j组最后一组之前至少要有j-1栋楼所以最后一组最早从第j栋开始【代码】const int MAXN 505;//最多有多少楼 const int INF INT_MAX / 2; int main(){ int n,m; cinnm; int d[MAXN]{0};//相邻之间的距离 int pos[MAXN]{0};//固定的坐标位置是绝对的 //读入距离 for(int i1;in;i){ cind[i]; } //计算坐标 pos[1]0;//以第一栋楼为起点 for(int i2;in;i){ pos[i]pos[i-1]d[i-1]; } //动态规划数组 int dp[MAXN][MAXN]{0}; //初始化分成1组的情况 for(int i1;in;i){//i代表有几栋宿舍楼 //计算[1,i]区间内建一个站的最小距离 int min_costINF; //尝试在[1,i]区间的每个位置建站 for(int station1;stationi;station){ int cost0; //计算所有楼k到这个站station的距离 for(int k1;ki;k){ costabs(pos[k]-pos[station]); } if(costmin_cost){min_costcost;} } dp[i][1]min_cost;//i栋宿舍被分成1组的时候最小的代价是多少 } //动态规划分为j组 m是要设置的快递点 for(int j2;jm;j){ for(int ij;in;i){//前i栋楼 i不能小于快递点数 dp[i][j]INF; for(int kj;ki;k){// // 枚举最后一组的起点k// 前k-1栋楼分成j-1组最后一组是[k,i] // 计算最后一组[k,i]内建一个站的最小距离 int last_group_costINF; //尝试在[k,i]内每个位置建站 for(int stationk;stationi;station){ int cost0; for(int xk;xi;x){ costabs(pos[x]-pos[station]); } if(costlast_group_cost){last_group_costcost;} } // 总距离前k-1栋楼分j-1组最后一组 int total_costdp[k-1][j-1]last_group_cost; if (total_cost dp[i][j]) { dp[i][j] total_cost; } } } }