“廉颇老矣，尚能饭否？”，事隔两个月，为了备战期末重出江湖啦！和我一起一晚上速成C++吧~
问题 A: 区间素数个数统计
题目描述
给定两个整数 L 和 R（1 ≤ L ≤ R ≤ 10000），请你统计区间 [L, R] 内的素数个数。素数的定义为：一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除；1 不是素数。
输入
输入仅一行，包含两个整数 L 和 R，分别表示区间的左端点和右端点。
输出
输出一个整数，表示区间 [L, R] 内的素数个数。
输入输出样例
样例输入 #1
1 10样例输出 #1
4欧拉筛，不解释。
#include<algorithm> #include<vector> #include<iostream> #define int long long using namespace std; signed main() { int l, r; cin >> l >> r; vector<bool>is_prime(r + 10, true); vector<int>primes; for (int i = 2;i <= r;i++) { if (is_prime[i]) primes.push_back(i); for (auto e : primes) { if (i * e > r) break; is_prime[i * e] = false; if (i % e == 0) break; } } int cnt = 0; for (auto e : primes) { if (e >= l && e <= r) cnt++; } cout << cnt; return 0; }问题 B: 快来统计
题目描述
给定一个字符串，分别统计大写字母、小写字母、数字、其他字符的个数（包括空格）
输入
一个字符串s，长度不超过1000
输出
a b c d四个数字注意依次为大写字母、小写字母、数字、其他字符的个数
输入输出样例
样例输入 #1
12345asdfgASDFG###样例输出 #1
5 5 5 3有空格，所以用getline
#include<algorithm> #include<vector> #include<iostream> #include<string> #define int long long using namespace std; signed main() { //大写字母、小写字母、数字、其他字符的个数 string s; getline(cin, s); int lar = 0; int sma = 0; int num = 0; int oth = 0; for (auto e : s) { if (e >= 'A' && e <= 'Z') lar++; else if (e >= 'a' && e <= 'z') sma++; else if (e >= '0' && e <= '9') num++; else oth++; } cout << lar << " " << sma << " " << num << " " << oth; return 0; }问题 C: 无限递归递归递归递归递归~
题目描述
这一天的忧郁忧郁起来~
对于一个递归函数w(a,b,c)
- 如果a≤0 或b≤0 或c≤0 就返回值 1。
- 如果a>20 或b>20 或c>20 就返回w(20,20,20)
- 如果a<b并且b<c就返回w(a,b,c−1)+w(a,b−1,c−1)−w(a,b−1,c)。
- 其它的情况就返回w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1)
这是个简单的递归函数，但实现起来可能会有些问题。当a,b,c均为 15 时，调用的次数将非常的多。你要想个办法才行。
注意：例如w(30,−1,0) 又满足条件 1 又满足条件 2，请按照最上面的条件来算，答案为 1。
输入
输入三个整数a,b,c
保证输入的数在 [-100,100] 之间，并且是整数。
输出
直接输出结果即可
输入输出样例
样例输入 #1
1 1 1样例输出 #1
2提示
如果发现时间超限可以试试这招哦：
把每一组w函数的值保存起来，下一次如果遇到直接用就可以。
提示代码：
long long int fun(ll x, ll y, ll z) { if (x <= 20 && y <= 20 && z <= 20 && x >= 0 && y >= 0 && z >= 0) { if (f[x][y][z]) { return _______; } } if ((x <= 0) || (y <= 0) || (z <= 0)) { return _______; } if ((x > 20) || (y > 20) || (z > 20)) { return ____; } if ((x < y) && (y < z)) { return f[x][y][z] = ______; } return f[x][y][z] = _______; }1.这题很良心了，还提示会超时记得开记忆数组。
2.有一点要注意的是数组下标不能是负数，所以我加了100的偏移量。
#include<algorithm> #include<vector> #include<iostream> #include<string> #define int long long using namespace std; int f[200][200][200]; int fun(int x, int y, int z) { if (x <= 120 && y <= 120 && z <= 120 && x >= 100 && y >= 100 && z >= 100) { if (f[x][y][z]!=0) { return f[x][y][z]; } } if ((x <= 100) || (y <= 100) || (z <= 100)) { return 1; } if ((x > 120) || (y > 120) || (z > 120)) { return fun(120, 120, 120); } if ((x < y) && (y < z)) { //w(a,b,c−1)+w(a,b−1,c−1)−w(a,b−1,c) f[x][y][z] = fun(x, y, z - 1) + fun(x, y - 1, z - 1) - fun(x, y - 1, z - 1); return f[x][y][z]; } //w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1) f[x][y][z] = fun(x - 1, y, z) + fun(x - 1, y - 1, z) + fun(x - 1, y, z - 1) - fun(x - 1, y - 1, z - 1); return f[x][y][z]; } signed main() { int x, y, z; cin >> x >> y >> z; x += 100, y += 100, z += 100; cout << fun(x, y, z); return 0; }问题 D: 这样查找效率高
题目描述
在 nnn 个整数构成的有序序列中，找到关键字 keykeykey 在序列中出现的位置。当 keykeykey 在序列中不出现时，输出No。
为了提高查找效率，利用待查找序列有序的特征，程序使用“二分查找”的算法。二分查找的做法是：首先，将表中间位置记录的关键字与查找关键字 keykeykey 比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
在提示部分已经给出部分代码，将程序补充完整，并提交规定的部分。
输入
先输入 nnn 个表示待查找的序列中的元素个数。
再输入 nnn 个整数作为待查找序列，这些整数按从小到大的顺序排列。
最后输入要查找的数 keykeykey。
输出
输出 keykeykey 在序列出现的位置，若不出现，输出No。
输入输出样例
样例输入 #1
复制
10 2 4 5 6 8 22 37 65 75 88 5样例输出 #1
复制
3提示
#include <stdio.h> #define SIZE 100 int find(int *, int, int); int main() { int d[SIZE], i; int n, key, index; scanf("%d", &n); for (i= 0; i < n; i++) scanf("%d", &d[i]); scanf("%d", &key); index=find(d,n,key); if (index >= 0) printf("%d\n", index+1); else printf("No\n"); return 0; } /*******只提交下面的部分********/ int find(int *d, int n, int k) { int low= 0, high= n-1, mid, index= -1; while (_____1______) { mid= _____2_____; if (d[mid] == k) { index= mid; _____3_____; } else if (_____4_____) high= mid-1; else low= mid+1; } return index; }int find(int* d, int n, int k) { int low = 0, high = n - 1, mid, index = -1; //注意这里带等号。 while (low <= high) { mid = low + (high - low) / 2; if (d[mid] == k) { index = mid; return index; } else if (d[mid] > k) high = mid - 1; else low = mid + 1; } return index; }问题 E: 小A点菜
题目描述
uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。
uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。
不过 uim 由于买了一些书，口袋里只剩 MMM 元 (M≤10000)(M \le 10000)(M≤10000)。
餐馆虽低端，但是菜品种类不少，有 NNN 种 (N≤100)(N \le 100)(N≤100)，第 iii 种卖 aia_iai 元 (ai≤1000)(a_i \le 1000)(ai≤1000)。由于是很低端的餐馆，所以每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
由于小 A 肚子太饿，所以最多只能等待 111 秒。
输入
第一行是两个数字，表示 NNN 和 MMM。
第二行起 NNN 个正数 aia_iai（可以有相同的数字，每个数字均在 100010001000 以内）。
输出
一个正整数，表示点菜方案数，保证答案的范围在 int 之内。
输入输出样例
样例输入 #1
复制
4 4 1 1 2 2样例输出 #1
复制
3这题刚开始我没意识到是01背包，用dfs写，出来答案不对。问了一下，发现重复统计了好多情况。因为就算答案改对了也不能解决超时，所以懒得改了。
01背包变形，记得逆序遍历体积，这样可以保证第 i 个物品只被放入一次。
#include <iostream> #include<vector> #include<algorithm> using namespace std; int main() { int n,V; cin>>n>>V; vector<int>v(n); for(int i=0;i<n;i++) cin>>v[i]; //dp[j]表示总花费恰好为j的方案数 vector<int>dp(V+1); dp[0]=1;//花费为0的方案数为1（什么都不选） for(int i=0;i<n;i++) { for(int j=V;j>=v[i];j--) { dp[j]+=dp[j-v[i]]; } } cout<<dp[V];//输出刚好花完 M 元的方案数 return 0; }问题 G: 马走日
题目描述
马在中国象棋中以日字规则移动。
编写一段程序，给定 n×mn \times mn×m 大小的棋盘 (n<10(n \lt 10(n<10，m<10)m \lt 10)m<10) 以及马的初始位置 (x,y)(x, y)(x,y)，要求不能重复经过棋盘上的同一个点，计算马有多少条路径可以遍历棋盘上所有点。
输入
第一行为整数 TTT（T<10T \lt 10T<10），表示测试数据的组数。
每一组测试数据包含一行，为 444 个整数，分别为棋盘的大小以及初始位置坐标 n,m,x,yn, m, x, yn,m,x,y (0≤x≤n−1(0 \le x \le n-1(0≤x≤n−1，0≤y≤m−10 \le y \le m-10≤y≤m−1，m<10m \lt 10m<10，n<10)n \lt 10)n<10)。
输出
每组测试数据输出一行，为一个整数，表示马能遍历棋盘的路径总数，000 为无法遍历一次。
输入输出样例
样例输入 #1
复制
1 5 4 0 0样例输出 #1
复制
32一眼dfs，往下翻翻看到数据范围也很友好（0-10），更放心了。两个月没碰搜索居然能一遍过，运气真好🤭
#include <iostream> #include<vector> #include<algorithm> #define int long long using namespace std; int cnt=0; int n,m,sx,sy; int dx[8]={1,1,-1,-1,2,2,-2,-2}; int dy[8]={2,-2,2,-2,1,-1,1,-1}; void dfs(vector<vector<int>>&vis,int x,int y,int cur) { if(cur==n*m) { cnt++; return; } for(int i=0;i<8;i++) { int nx=x+dx[i]; int ny=y+dy[i]; if(nx<0||nx>=n||ny<0||ny>=m) continue; if(vis[nx][ny]) continue; vis[nx][ny]=true; dfs(vis,nx,ny,cur+1); vis[nx][ny]=false; } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { cin>>n>>m>>sx>>sy; vector<vector<int>>vis(n,vector<int>(m,false)); cnt=0; vis[sx][sy]=true; dfs(vis,sx,sy,1); cout<<cnt<<"\n"; } return 0; }问题 H: 填空题-迷宫问题
题目描述
定义一个二维数组：
int maze[5][5]= { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0 };它表示一个迷宫，其中的 111 表示墙壁，000 表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
请补全下列C语言程序
#include <stdio.h> int map[6][6]; //地图 int vis[6][6]; //判重 int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; struct node{ int x,y; //坐标 int c; //上一点 }queue[36]; void print(int head) { while(queue[head].c != -1) { print(queue[head].c); printf("(%d,%d)\n",queue[head].x,queue[head].y); return; } printf("(0,0)\n"); } void bfs(int x,int y) { int head = 0,tail = 1; int i; queue[0].x = 0; queue[0].y = 0; queue[0].c = -1; struct node now; while(head < tail) { if(queue[head].x == 4 && queue[head].y == 4) { print(head); return; } for(i = 0;i < 4;i++) { now.x = queue[head].x + dir[i][0]; now.y = queue[head].y + dir[i][1]; now.c = head; if(now.x >= 0 && now.x <= 4 && now.y >= 0 && now.y <= 5) { if(!vis[now.x][now.y] && !map[now.x][now.y]) { /* 在此处输入你的代码 记录当前位置为已走过 进行入队操作 修改队尾的位置 */ } } } head++; } } int main() { int i,j; for(i = 0;i < 5;i++) { for(j = 0;j < 5;j++) { scanf("%d",&map[i][j]); } } memset(vis,0,sizeof(vis)); bfs(0,0); return 0; }输入
一个 5×55 \times 55×5 的二维数组，表示一个迷宫。数据保证有唯一解。
输出
左上角到右下角的最短路径，格式如样例所示。
输入输出样例
样例输入 #1
复制
0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0样例输出 #1
复制
(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)提示
提交部分代码即可
第一眼看到最短路我不用手搓我喜极而泣，第二眼看到队列的实现要逐行分析代码我潸然泪下。
vis[now.x][now.y]=1; queue[tail].x = now.x; queue[tail].y = now.y; queue[tail].c = head; tail++;问题 I: 成绩排序
题目描述
有n名同学，每名同学有语文、数学、英语三科成绩，你需要按照如下规则对所有同学的成绩从高到低排序：
- 比较总分，高者靠前；
- 如果总分相同，则比较语文和数学两科的总分，高者靠前；
- 如果仍相同，则比较语文和数学两科的最高分，高者靠前；
- 如果仍相同，则二人并列。
你需要输出每位同学的排名，如遇x人并列，则他们排名相同，并留空后面的x−1 个名次。例如，有 3 名同学并列第 1，则后一名同学自动成为第 4 名。
C：
#include <stdio.h> #include <stdlib.h> typedef struct { int ci, mi, ei; int total, sum_cm, max_cm; int idx; // 记录原始输入序号，用于按原顺序输出 } Student; // qsort比较函数：按题目要求从高到低排序 int cmp(const void *a, const void *b) { const Student *p1 = (const Student *)a; const Student *p2 = (const Student *)b; if (p1->total != p2->total) { return p2->total - p1->total; } else if (p1->sum_cm != p2->sum_cm) { return ____; // 1. 语数总分不同，高者排前面 } else { return ____; // 2. 语数总分相同，最高分高者排前面 } } int main() { int N; scanf("%d", &N); Student students[10001]; for (int i = 0; i < N; i++) { scanf("%d%d%d", &students[i].ci, &students[i].mi, &students[i].ei); students[i].total = students[i].ci + students[i].mi + students[i].ei; students[i].sum_cm = students[i].ci + students[i].mi; students[i].max_cm = students[i].ci > students[i].mi ? students[i].ci : students[i].mi; students[i].idx = ____; // 3. 记录原始输入序号 } qsort(students, N, sizeof(Student), cmp); int rank[10001]; rank[students[0].idx] = 1; for (int i = 1; i < N; i++) { // 4. 判断是否与前一名并列（所有排序关键字都相同） if (____) { rank[students[i].idx] = rank[students[i-1].idx]; } else { rank[students[i].idx] = ____; // 5. 不并列，计算当前排名 } } // 按原始输入顺序输出排名 for (int i = 0; i < N; i++) { printf("%d\n", rank[i]); } return 0; }C++：
#include <iostream> #include <algorithm> // 用于sort排序函数 using namespace std; struct Student { int ci, mi, ei; int total, sum_cm, max_cm; int idx; // 记录原始输入序号，用于按原顺序输出 }; // sort比较函数：返回true表示a应该排在b前面 bool cmp(const Student& a, const Student& b) { if (a.total != b.total) { return a.total > b.total; // 总分降序 } else if (a.sum_cm != b.sum_cm) { return ____; // 1. 语数总分不同，高者排前面 } else { return ____; // 2. 语数总分相同，最高分高者排前面 } } int main() { int N; cin >> N; Student students[10001]; for (int i = 0; i < N; i++) { cin >> students[i].ci >> students[i].mi >> students[i].ei; students[i].total = students[i].ci + students[i].mi + students[i].ei; students[i].sum_cm = students[i].ci + students[i].mi; students[i].max_cm = max(students[i].ci, students[i].mi); // C++内置max函数 students[i].idx = ____; // 3. 记录原始输入序号 } sort(students, students + N, cmp); // C++标准排序函数 int rank[10001]; rank[students[0].idx] = 1; for (int i = 1; i < N; i++) { // 4. 判断是否与前一名并列（所有排序关键字都相同） if (____) { rank[students[i].idx] = rank[students[i-1].idx]; } else { rank[students[i].idx] = ____; // 5. 不并列，计算当前排名 } } // 按原始输入顺序输出排名 for (int i = 0; i < N; i++) { cout << rank[i] << endl; } return 0; }输入
第一行一个整数N，表示同学的人数。
接下来N行，每行三个非负整数ci,mi,ei 分别表示该名同学的语文、数学、英语成绩。
输出
输出N行，按输入同学的顺序，输出他们的排名。
注意：请不要按排名输出同学的序号，而是按同学的顺序输出他们各自的排名。
输入输出样例
样例输入 #1
6 140 140 150 140 149 140 148 141 140 141 148 140 145 145 139 0 0 0样例输出 #1
1 3 4 4 2 6提示
保证2≤N≤104，0≤ci,mi,ei≤150。
注意第五是i+1.
#include <iostream> #include <algorithm> // 用于sort排序函数 using namespace std; struct Student { int ci, mi, ei; int total, sum_cm, max_cm; int idx; // 记录原始输入序号，用于按原顺序输出 }; // sort比较函数：返回true表示a应该排在b前面 bool cmp(const Student& a, const Student& b) { if (a.total != b.total) { return a.total > b.total; // 总分降序 } else if (a.sum_cm != b.sum_cm) { return a.sum_cm>b.sum_cm; // 1. 语数总分不同，高者排前面 } else { return a.max_cm>b.max_cm; // 2. 语数总分相同，最高分高者排前面 } } int main() { int N; cin >> N; Student students[10001]; for (int i = 0; i < N; i++) { cin >> students[i].ci >> students[i].mi >> students[i].ei; students[i].total = students[i].ci + students[i].mi + students[i].ei; students[i].sum_cm = students[i].ci + students[i].mi; students[i].max_cm = max(students[i].ci, students[i].mi); // C++内置max函数 students[i].idx = i; // 3. 记录原始输入序号 } sort(students, students + N, cmp); // C++标准排序函数 int rank[10001]; rank[students[0].idx] = 1; for (int i = 1; i < N; i++) { // 4. 判断是否与前一名并列（所有排序关键字都相同） if (students[i].total==students[i-1].total &&students[i].sum_cm==students[i-1].sum_cm &&students[i].max_cm==students[i-1].max_cm) { rank[students[i].idx] = rank[students[i-1].idx]; } else { rank[students[i].idx] = i+1; // 5. 不并列，计算当前排名 } } // 按原始输入顺序输出排名 for (int i = 0; i < N; i++) { cout << rank[i] << endl; } return 0; }问题 J: 4.买糖果
题目描述
果店开业了，老板收到若干订单，贪心的老板喜欢先将订单总价值多的客户先发货，毕竟以盈利为主嘛，现在老板收到 nnn 份订单 (n<20)(n \lt 20)(n<20) 以及这 nnn 份订单的详细信息，请按照订单总价值从大到小排序，并输出客户昵称（数据保证没有总价值相同的订单）。
输入
分 n+1n+1n+1 行，第一行输入正整数 nnn 表示订单总数，剩下 nnn 行输入订单信息，第一个数字代表糖果单价（浮点数），第二个数字代表购货总数（正整数），第三个字符串代表客户昵称。
输出
按照订单总价由大到小分n行输出客户昵称。
输入输出样例
样例输入 #1
复制
2 1 100 Mike 1.2 60 Joy样例输出 #1
复制
Mike Joy
