(首先说明一点哈:这是我第一次写博客,写的不好大家见谅)
自我介绍:一个脑子不好的大一学生,c语言接触还没到半年,若涉及到效率等问题,各位都可以在评论区提出见解,谢谢啦
(题目链接: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;
}
(题目链接: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;
}
(题目链接: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;
}
(题目链接: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;
}
(题目链接: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;
}
(题目链接: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;
}
(题目链接:题目-独木舟 (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;
}
(题目链接: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;
}
(题目链接: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;
}
(题目链接: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;
}
(题目链接: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;
}
以上就是我最近所写题目中的一部分总结啦,如果各位有任何对代码或者本人注释的建议,都欢迎在评论区提出来,共同进步!(终于熬夜肝完了)