“廉颇老矣尚能饭否”事隔两个月为了备战期末重出江湖啦和我一起一晚上速成C吧~问题 A: 区间素数个数统计题目描述给定两个整数 L 和 R1 ≤ L ≤ R ≤ 10000请你统计区间 [L, R] 内的素数个数。素数的定义为一个大于 1 的自然数除了 1 和它自身外不能被其他自然数整除1 不是素数。输入输入仅一行包含两个整数 L 和 R分别表示区间的左端点和右端点。输出输出一个整数表示区间 [L, R] 内的素数个数。输入输出样例样例输入 #11 10样例输出 #14欧拉筛不解释。#includealgorithm #includevector #includeiostream #define int long long using namespace std; signed main() { int l, r; cin l r; vectorboolis_prime(r 10, true); vectorintprimes; 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四个数字注意依次为大写字母、小写字母、数字、其他字符的个数输入输出样例样例输入 #112345asdfgASDFG###样例输出 #15 5 5 3有空格所以用getline#includealgorithm #includevector #includeiostream #includestring #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。如果a20 或b20 或c20 就返回w(20,20,20)如果ab并且bc就返回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] 之间并且是整数。输出直接输出结果即可输入输出样例样例输入 #11 1 1样例输出 #12提示如果发现时间超限可以试试这招哦把每一组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的偏移量。#includealgorithm #includevector #includeiostream #includestring #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); indexfind(d,n,key); if (index 0) printf(%d\n, index1); 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 mid1; } 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 #includevector #includealgorithm using namespace std; int main() { int n,V; cinnV; vectorintv(n); for(int i0;in;i) cinv[i]; //dp[j]表示总花费恰好为j的方案数 vectorintdp(V1); dp[0]1;//花费为0的方案数为1什么都不选 for(int i0;in;i) { for(int jV;jv[i];j--) { dp[j]dp[j-v[i]]; } } coutdp[V];//输出刚好花完 M 元的方案数 return 0; }问题 G: 马走日题目描述马在中国象棋中以日字规则移动。编写一段程序给定 n×mn \times mn×m 大小的棋盘 (n10(n \lt 10(n10m10)m \lt 10)m10) 以及马的初始位置 (x,y)(x, y)(x,y)要求不能重复经过棋盘上的同一个点计算马有多少条路径可以遍历棋盘上所有点。输入第一行为整数 TTTT10T \lt 10T10表示测试数据的组数。每一组测试数据包含一行为 444 个整数分别为棋盘的大小以及初始位置坐标 n,m,x,yn, m, x, yn,m,x,y (0≤x≤n−1(0 \le x \le n-1(0≤x≤n−10≤y≤m−10 \le y \le m-10≤y≤m−1m10m \lt 10m10n10)n \lt 10)n10)。输出每组测试数据输出一行为一个整数表示马能遍历棋盘的路径总数000 为无法遍历一次。输入输出样例样例输入 #1复制1 5 4 0 0样例输出 #1复制32一眼dfs往下翻翻看到数据范围也很友好0-10更放心了。两个月没碰搜索居然能一遍过运气真好#include iostream #includevector #includealgorithm #define int long long using namespace std; int cnt0; 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(vectorvectorintvis,int x,int y,int cur) { if(curn*m) { cnt; return; } for(int i0;i8;i) { int nxxdx[i]; int nyydy[i]; if(nx0||nxn||ny0||nym) continue; if(vis[nx][ny]) continue; vis[nx][ny]true; dfs(vis,nx,ny,cur1); vis[nx][ny]false; } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cint; while(t--) { cinnmsxsy; vectorvectorintvis(n,vectorint(m,false)); cnt0; vis[sx][sy]true; dfs(vis,sx,sy,1); coutcnt\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行按输入同学的顺序输出他们的排名。注意请不要按排名输出同学的序号而是按同学的顺序输出他们各自的排名。输入输出样例样例输入 #16 140 140 150 140 149 140 148 141 140 141 148 140 145 145 139 0 0 0样例输出 #11 3 4 4 2 6提示保证2≤N≤1040≤ci​,mi​,ei​≤150。注意第五是i1.#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_cmb.sum_cm; // 1. 语数总分不同高者排前面 } else { return a.max_cmb.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].totalstudents[i-1].total students[i].sum_cmstudents[i-1].sum_cm students[i].max_cmstudents[i-1].max_cm) { rank[students[i].idx] rank[students[i-1].idx]; } else { rank[students[i].idx] i1; // 5. 不并列计算当前排名 } } // 按原始输入顺序输出排名 for (int i 0; i N; i) { cout rank[i] endl; } return 0; }问题 J: 4.买糖果题目描述果店开业了老板收到若干订单贪心的老板喜欢先将订单总价值多的客户先发货毕竟以盈利为主嘛现在老板收到 nnn 份订单 (n20)(n \lt 20)(n20) 以及这 nnn 份订单的详细信息请按照订单总价值从大到小排序并输出客户昵称数据保证没有总价值相同的订单。输入分 n1n1n1 行第一行输入正整数 nnn 表示订单总数剩下 nnn 行输入订单信息第一个数字代表糖果单价浮点数第二个数字代表购货总数正整数第三个字符串代表客户昵称。输出按照订单总价由大到小分n行输出客户昵称。输入输出样例样例输入 #1复制2 1 100 Mike 1.2 60 Joy样例输出 #1复制Mike Joy