（首先说明一点哈：这是我第一次写博客，写的不好大家见谅）
自我介绍：一个脑子不好的大一学生，c语言接触还没到半年，若涉及到效率等问题，各位都可以在评论区提出见解，谢谢啦
1.dfs题：奇怪的电梯
（题目链接：P1135 奇怪的电梯 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）
我一开始用的是比较常见类似与组合的那种回溯格式，虽然答案正确，可是第二组数据就超时了，以下为较为简洁的AC代码；
#include<stdio.h> #include<math.h> #include<string.h> int n, a, b, book[250] = { 0 }, lou[250] = { 0 }; //book数组：标记到达每楼时需要多少步，lou数组：记录每楼可以上下多少楼 void dfs(int step,int count) {//step表示现在所在楼层 if ( step > n || step < 1)return;//判断楼层是否合格，放开头 if (book[step] != -1 &&/**/count >= book[step])return;//注意是与不是或；注意答案要求为最少步数，因此大于的要return; book[step] = count; dfs(step +lou[step], count + 1);//上楼 dfs(step - lou[step], count + 1);//下楼 } int main() { scanf("%d%d%d", &n, &a, &b); for (int i = 1; i <= n; i++) { scanf("%d", &lou[i]); } memset(book,-1,sizeof(book));//将数组内所有元素赋值为-1 dfs(a, 0); printf("%d\n",book[b]); return 0; }2.dfs题：n皇后
(题目链接：https://www.luogu.com.cn/problem/P1219）
要对行和列对角线和反对角线进行查找，但该题并不要用到二维数组，用一维数组就好，把行当作递归函数的形参就好
#include<stdio.h> #include<math.h> #include<string.h> int n, count = 0, a[15] = { 0 }, lie[30] = { 0 }, dui[30] = { 0 }, fandui[30] = { 0 }; //a数组来记录皇后在每一行的位置，其他数组为标记是否可放皇后 void dfs(int row) { if (row == n + 1)//+1原因：第一步行和列都是从1开始的 { count++; if (count <= 3)//打印前三项 { for (int j = 1; j <= n; j++)printf("%d ", a[j]); printf("\n"); } return;//返回 上一层 ！ } for (int j = 1; j <= n; j++) { a[row] = j;//记录第row行皇后在j的位置 if (lie[j] || dui[row + j] || fandui[row- j + n]) continue; //判断列和对角线和反对角线//对角线上：行加列相等，反对角线上i-j相等，但为了避免[]里为负数，因此都加上了n lie[j] = dui[row + j] = fandui[row - j + n] = 1; //标记该列和对角线，反对角线 dfs(row + 1); //进入下一行 lie[j] = dui[row + j] = fandui[row - j + n] = 0; //回溯 } } int main() { scanf("%d", &n); dfs(1); printf("%d\n", count);//注意是在主函数才打印总数 return 0; }3.dfs题：海战
（题目链接：P1331 海战 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）
代码看起来很长，但都是简单函数构成
#include<stdio.h> #include<math.h> #include<string.h> int r, c, count = 0, dx[4] = { 0,0,-1,1 }, dy[4] = { -1,1,0,0 }, book[1010][1010] = { 0 }; //book数组：标记哪些点已计数过，避免重复计数 char a[1010][1010] = { 0 }; int judge(int x, int y) { if (x > r|| x<0||y<0|| y > c) return 0; return 1; } void dfs(int x, int y) { book[x][y] = 1; if (judge(x, y) == 1) { for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (a[nx][ny] == '#' && book[nx][ny] == 0 && judge(nx,ny) == 1) /*!!!!!!!!注意一定要写条件才能递归，不然一直递归!!!!!!*/ dfs(nx, ny); //book[nx][ny] = 0; /***不可将book还原，因为可能在主函数的循环部分重复计数***/ } } } int check(int x,int y)//check函数：判断相撞 { int sum = 0; if (a[x][y] == '#') sum++; if (a[x + 1][y] == '#') sum++; if (a[x][y + 1] == '#') sum++; if (a[x + 1][y + 1] == '#') sum++; if (sum == 3)//这里很巧妙 return 0; return 1; } int main() { int i, j; scanf("%d%d", &r, &c); for (i = 0; i < r; i++) { for (j = 0; j < c; j++) { scanf(" %c", &a[i][j]); } } for (i = 0; i < r; i++) { for (j = 0; j < c; j++) { if(check(i, j) == 0) { printf("Bad placement.\n"); return 0; //不用跳出循环，直接return } else { if(a[i][j]=='#'&&book[i][j]==0) { dfs(i, j); count++;//注意是在这里加加 } } } } printf("There are %d ships.\n",count); return 0; }4.dfs题：迷宫寻路
（题目链接：B3625 迷宫寻路 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）
以下为自己所写代码，可AC
#include<stdio.h> #include<math.h> #include<string.h> int n, m, book[110][110] = { 0 };//book数组：记录哪些地方走过了 char a[110][110] = { 0 }; int dfs(int e, int f) { if (book[e][f] == 1)return 0;//注意在开头判断 book[e][f] = 1;//标记该点已走过 if (e > n || e <= 0 || f<=0 || f>m)//判断越界 return 0; if (a[e][f] == '#')//遇见墙就返回 return 0; if (e == n && f == m) { return 1; } if ((dfs(e + 1, f) == 1) || (dfs(e, f + 1) == 1) || (dfs(e- 1, f) == 1) || (dfs(e, f - 1) == 1)) //四个方向都要走，而不是三个方向 return 1; return 0; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { for(int j=1;j<=m;j++) { scanf(" %c", &a[i][j]); } } int b=dfs(1,1); if (b == 1) printf("Yes\n"); else printf("No\n"); return 0; }5.贪心题：Mixing Milk
（题目链接：P1208 [USACO1.3] 混合牛奶 Mixing Milk – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）
#include<stdio.h> #include<math.h> #include<string.h> int n, m, p[5200] = { 0 }, a[5200]={0}, max = 0,money=0,sum=0; void pai_xu(int b[]) { for (int i = 1; i <= m-1; i++) { for(int j=i+1;j<=m;j++) { if (b[i] >b[j]) { int t = b[i]; b[i] = b[j]; b[j] = t; int c = a[i];//注意：一定对相应可卖数量进行调换位置 a[i] = a[j]; a[j] = c; } } } return; } int main() { scanf("%d%d", &n, &m); for(int i=1;i<=m;i++) { scanf("%d%d", &p[i], &a[i]); } pai_xu(p); //pai_xu(a);//注意：a不用排序，而是在排序函数里面进行了相应调换 for (int j = 1; j<= m; j++) { int x = sum; sum += a[j]; if (sum <= n) money += p[j] * a[j]; if (sum > n) { money += (n - x) * p[j]; break; } } printf("%d\n", money); return 0; }6.贪心题：弹珠游戏
（题目链接：P2356 弹珠游戏 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）
#include<stdio.h> #include<math.h> #include<string.h> int a[1010][1010] = { 0 },m=0,max=0, hang[1010] = { 0 }, lie[1010] = { 0 }; int main() { int n,i,j,flag=0; scanf("%d", &n); for (i = 0; i < n; i++) { for(j=0;j<n;j++) { scanf("%d", &a[i][j]); hang[i] += a[i][j];/*******/ lie[j] += a[i][j];/*******/ if (a[i][j] == 0) { flag = 1; } } } if ( flag == 0)//没有一个点是0，即没有容身之地 { printf("Bad Game!\n"); return 0;//直接return } for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (a[i][j] == 0) m = hang[i] + lie[j]; if (m > max)//更换最大值 max=m; } } printf("%d\n",max ); return 0; }7.贪心题：独木舟
（题目链接：题目-独木舟 (51nod.com)）
int n, m, w[10010] = { 0 }, flag = 0; void pai_xu(int b[]) { for (int i = 0; i <= n - 2; i++) { for (int j = i + 1; j <= n-1; j++) { if (b[i] > b[j]) { int t = b[i]; b[i] = b[j]; b[j] = t; } } } return; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { scanf("%d", &w[i]); } pai_xu(w);//先对其进行排序 int sum = n;//注意这里sum是等于n的，后续再对其进行减减操作 int i = 0; int j = n - 1;//是n-1，而不是n while(i<j) { if (w[i] + w[j] <= m) { i++; j--; sum--; } else { j--;//只有j改变，i不变 } } printf("%d\n", sum); return 0; }8.贪心题：Chips on the Board
（题目链接：Chips on the Board – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）
int n, a[300010] = { 0 }, b[300010] = { 0 }; int main() { int t; scanf("%d", &t); while(t--) { int minb=1000000001,mina= 1000000001; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); mina = a[i] < mina ? a[i] : mina;//核心：是要小的 } for (int i = 0; i < n; i++) { scanf("%d", &b[i]); minb = b[i]<minb?b[i]:minb;//核心：是要小的 } int sum2=0, sum1=0,sum; for (int i = 0; i < n; i++) { sum1 += mina + b[i]; // 核心：是要小的 sum2 += minb + a[i]; // 核心：是要小的 } sum = sum1 < sum2 ? sum1 : sum2;// 核心：是要小的 printf("%d\n", sum); } return 0; }9.贪心题： Longest Divisors Interval
（题目链接：Longest Divisors Interval – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）
该题一定要开long long,int 类型过不了
该题关键：因数越小越可能区间越大
#include<stdio.h> #include<math.h> #include<string.h> #define ll long long int main() { ll n,t; scanf("%lld", &t); while (t--) { ll count = 0,max=0; scanf("%lld", &n); for (ll i = 1;i<=n; i++) { if (n % i == 0) { count++; continue; } else break; } printf("%lld\n", count); } return 0; }10.贪心题：Array Coloring
（题目链接：Array Coloring – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）
#include<stdio.h> #include<math.h> #include<string.h> #define ll long long //该题写出来很简单，就是得想到关键：奇数加奇数等于偶数，偶数加偶数还是偶数，所以其和必定为偶数才符合 int main() { int n, t, a[55] = { 0 },sum=0; scanf("%d", &t); while (t--) { sum = 0;/**/ scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); sum+=a[i]; } if (sum % 2 == 0) printf("YES\n"); else printf("NO\n"); } return 0; }11.贪心题： Unit Array
（题目链接：Unit Array – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）
//该题关键：算积与和，再根据其进行情况分类 int main() { int n, t, a[110] = { 0 }; scanf("%d", &t); while (t--) { int count = 0,sum=0,cheng=1/**/; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); sum += a[i]; cheng *= a[i]; } //情况： //sum>=0,cheng<0; // sum>=0,cheng>0 // sum<0,cheng>0 // sum<0,cheng<0 if (sum >= 0) { if(cheng==1) printf("0\n"); else printf("1\n"); continue; } else { while (sum < 0) { sum += 2; cheng *= (-1); count++; } if (cheng == -1) count++; printf("%d\n", count); } } return 0; }以上就是我最近所写题目中的一部分总结啦，如果各位有任何对代码或者本人注释的建议，都欢迎在评论区提出来，共同进步！（终于熬夜肝完了）
版权声明：本文为博主作者：脑子不好的小菜鸟原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/2301_79293429/article/details/134752671
