（首先說明一點哈：這是我第一次寫博客，寫的不好大家見諒）

自我介紹：一個腦子不好的大一學生，c語言接觸還沒到半年，若涉及到效率等問題，各位都可以在評論區(qū)提出見解，謝謝啦

1.dfs題：奇怪的電梯

（題目鏈接：P1135 奇怪的電梯 - 洛谷 | 計算機科學教育新生態(tài) (luogu.com.cn)）

我一開始用的是比較常見類似與組合的那種回溯格式，雖然答案正確，可是第二組數(shù)據(jù)就超時了，以下為較為簡潔的AC代碼；

#include<stdio.h>
#include<math.h>
#include<string.h>
int n, a, b, book[250] = { 0 }, lou[250] = { 0 };
//book數(shù)組：標記到達每樓時需要多少步，lou數(shù)組：記錄每樓可以上下多少樓
void dfs(int step,int count)
{//step表示現(xiàn)在所在樓層
    if ( step > n || step < 1)return;//判斷樓層是否合格，放開頭
    if (book[step] != -1 &&/**/count >= book[step])return;//注意是與不是或；注意答案要求為最少步數(shù)，因此大于的要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));//將數(shù)組內(nèi)所有元素賦值為-1
    dfs(a, 0);
    printf("%d\n",book[b]);
    return 0;
}

2.dfs題：n皇后

(題目鏈接：https://www.luogu.com.cn/problem/P1219）

要對行和列對角線和反對角線進行查找，但該題并不要用到二維數(shù)組，用一維數(shù)組就好，把行當作遞歸函數(shù)的形參就好

#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數(shù)組來記錄皇后在每一行的位置，其他數(shù)組為標記是否可放皇后
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相等，但為了避免[]里為負數(shù)，因此都加上了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);//注意是在主函數(shù)才打印總數(shù)
	return 0;
}

3.dfs題：海戰(zhàn)

（題目鏈接：P1331 海戰(zhàn) - 洛谷 | 計算機科學教育新生態(tài) (luogu.com.cn)）

代碼看起來很長，但都是簡單函數(shù)構(gòu)成

#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數(shù)組：標記哪些點已計數(shù)過，避免重復計數(shù)
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還原，因為可能在主函數(shù)的循環(huán)部分重復計數(shù)***/
		}
	}
}
int check(int x,int y)//check函數(shù)：判斷相撞
{		
		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;
				//不用跳出循環(huán)，直接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 迷宮尋路 - 洛谷 | 計算機科學教育新生態(tài) (luogu.com.cn)）

以下為自己所寫代碼，可AC

#include<stdio.h>
#include<math.h>
#include<string.h>
int n, m, book[110][110] = { 0 };//book數(shù)組：記錄哪些地方走過了
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 - 洛谷 | 計算機科學教育新生態(tài) (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];//注意：一定對相應(yīng)可賣數(shù)量進行調(diào)換位置
                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不用排序，而是在排序函數(shù)里面進行了相應(yīng)調(diào)換
    
        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 彈珠游戲 - 洛谷 | 計算機科學教育新生態(tài) (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的，后續(xù)再對其進行減減操作
    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 - 洛谷 | 計算機科學教育新生態(tài) (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 - 洛谷 | 計算機科學教育新生態(tài) (luogu.com.cn)）

該題一定要開long long,int 類型過不了

該題關(guān)鍵：因數(shù)越小越可能區(qū)間越大

#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 - 洛谷 | 計算機科學教育新生態(tài) (luogu.com.cn)）

#include<stdio.h>
#include<math.h>
#include<string.h>
#define ll long long
//該題寫出來很簡單，就是得想到關(guān)鍵：奇數(shù)加奇數(shù)等于偶數(shù)，偶數(shù)加偶數(shù)還是偶數(shù)，所以其和必定為偶數(shù)才符合
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 - 洛谷 | 計算機科學教育新生態(tài) (luogu.com.cn)）

//該題關(guān)鍵：算積與和，再根據(jù)其進行情況分類
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;
}

以上就是我最近所寫題目中的一部分總結(jié)啦，如果各位有任何對代碼或者本人注釋的建議，都歡迎在評論區(qū)提出來，共同進步?。ńK于熬夜肝完了）文章來源地址http://www.zghlxwxcb.cn/news/detail-768646.html

到了這里，關(guān)于過去一周寫過的算法題的一部分（dfs，貪心）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！