【算法题解】部分洛谷题解(下)

前言

本篇为我做过的洛谷题的部分题解，大多是我认为比较具有代表性的或者比较有意思的题目，包含我自己的思考过程和想法。

---

[NOIP2001 提高组] 一元三次方程求解

题目描述

有形如：$a{x}^3+b{x}^2+cx+d=0$ 这样的一个一元三次方程。给出该方程中各项的系数（$a,b,c,d$ 均为实数），并约定该方程存在三个不同实根（根的范围在 $-100$ 至 $100$ 之间），且根与根之差的绝对值 $\ge 1$。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 $2$ 位。

提示：记方程 $f(x)=0$，若存在 $2$ 个数 $x_1$ 和 $x_2$，且 $x_1<x_2$，$f(x_1)\times f(x_2)<0$，则在 $(x_1,x_2)$ 之间一定有一个根。

输入格式

一行，$4$ 个实数 $a,b,c,d$。

输出格式

一行，$3$ 个实根，从小到大输出，并精确到小数点后 $2$ 位。

样例 #1

样例输入 #1

1 -5 -4 20

样例输出 #1

-2.00 2.00 5.00

提示

【题目来源】

NOIP 2001 提高组第一题

---

这题是典型的二分查找法，因为题目要求求出近似解(保留小数点后两位，)，所以二分查找的边界需要注意一下。是当r-l<eps时，这个eps指一个很小的值，要比0.01要小，这里eps=1e-4，就认为找到了近似解，但是此时f(mid)并不等于0。

开始先一个for循环，也是题目提示我们的，从-100到100，然后利用高中学的零点定理，判断(i,i+1)这个区间内有没有零点，然后再对这个区间使用二分查找法。

完整代码

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define eps 1e-4
double a,b,c,d;
double f(double x){
	return a*x*x*x+b*x*x+c*x+d;
}
int main(){
	double y;
	cin>>a>>b>>c>>d;
	for(int i=-100;i<=100;i++){
		if(fabs(f(i*1.0))<eps){
			printf("%.2lf ",i*1.0);
			continue;
		}
		if(fabs(f((i+1)*1.0))<eps)
			continue;
		if(f(i)*f(i+1)<0){
			double l=i*1.0,r=(i+1)*1.0,mid;
			while(r-l>eps){
				mid=(l+r)/2;
				if(f(l)*f(mid)<0) r=mid;
				if(f(mid)*f(r)<0) l=mid;
				if(f(mid)==0) break;
			}
			printf("%.2lf ",mid);
		}
    }
	return 0;
} 

---

NASA的食物计划

题目背景

NASA（美国航空航天局）因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋，因此在各方压力下终止了航天飞机的历史，但是此类事情会不会在以后发生，谁也无法保证。所以，在遇到这类航天问题时，也许只能让航天员出仓维修。但是过多的维修会消耗航天员大量的能量，因此 NASA 便想设计一种食品方案，使体积和承重有限的条件下多装载一些高卡路里的食物。

题目描述

航天飞机的体积有限，当然如果载过重的物品，燃料会浪费很多钱，每件食品都有各自的体积、质量以及所含卡路里。在告诉你体积和质量的最大值的情况下，请输出能达到的食品方案所含卡路里的最大值，当然每个食品只能使用一次。

输入格式

第一行 $2$ 个整数，分别代表体积最大值 $h$ 和质量最大值 $t$。

第二行 $1$ 个整数代表食品总数 $n$。

接下来 $n$ 行每行 $3$ 个数 体积 $h_i$，质量 $t_i$，所含卡路里 $k_i$。

输出格式

一个数，表示所能达到的最大卡路里（int 范围内）

样例 #1

样例输入 #1

320 350
4
160 40 120
80 110 240
220 70 310
40 400 220

样例输出 #1

550

提示

对于 $100\%$ 的数据，$h,t,h_i,t_i\le 400$，$n\le 50$，$k_i\le 500$。

---

这道题是一道多维背包问题，一个商品有价值，重量，体积三个属性。把最初的01背包的二维数组改成三维数组即可。

这里使用了数组压缩，简单01背包变为一维数组，多重背包就是二维数组。注意代表重量的j和代表体积的k要从后往前循环。

完整代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int MAX(int a,int b){
	if(a>b) return a;
	else return b;
}
int main(){
	int k,i,j,h,m,n,s[51],v[51],c[51],f[401][401];
    memset(f,0,sizeof(f));
	scanf("%d%d%d",&m,&h,&n);
	for(i=1;i<=n;i++)
	  scanf("%d%d%d",&v[i],&s[i],&c[i]);
	for(i=1;i<=n;i++)
	  for(j=m;j>=1;j--)
	    if(v[i]<=j) 
		  for(k=h;k>=1;k--)
		    if(s[i]<=k) f[j][k]=MAX(f[j][k],f[j-v[i]][k-s[i]]+c[i]);
	printf("%d",f[m][h]);	  
	return 0;	 
}

---

[NOIP2007 普及组] 守望者的逃离

题目背景

NOIP2007 普及组 T3

题目描述

恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。

守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。

为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。

守望者的跑步速度为 $17m/s$，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在 $1s$ 内移动 $60m$，不过每次使用闪烁法术都会消耗魔法值 $10$ 点。守望者的魔法值恢复的速度为 $4$ 点每秒，只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值 $M$，他所在的初始位置与岛的出口之间的距离 $S$，岛沉没的时间 $T$。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。

注意：守望者跑步、闪烁或休息活动均以秒为单位，且每次活动的持续时间为整数秒。距离的单位为米。

输入格式

输入数据共一行三个非负整数，分别表示 $M$，$S$，$T$。

输出格式

输出数据共两行。

第一行一个字符串 $\text{Yes}$ 或 $\text{No}$，即守望者是否能逃离荒岛。

第二行包含一个整数。第一行为 $\text{Yes}$ 时表示守望者逃离荒岛的最短时间；第一行为 $\text{No}$ 时表示守望者能走的最远距离。

样例 #1

样例输入 #1

39 200 4

样例输出 #1

No
197

样例 #2

样例输入 #2

36 255 10

样例输出 #2

Yes
6

提示

对于 $30\%$ 的数据，$1\le T\le 10$，$ 1 \le S \le 100$；

对于 $50\%$ 的数据，$1\le T\le 10^3$，$ 1 \le S \le 10^4$；

对于 $100\%$ 的数据，$1\le T\le 3\times 10^5$，$0\le M\le 10^3$，$ 1 \le S \le 10^8$。

---

这道题应该属于动态规划，像是基于时间轴的动态规划，不太常规，没有一个大的动态规划状态转移方程。

定义一个数组f[i]，代表第i秒能走的最远距离。

1. 首先能闪烁就闪烁，没能量了就停下来休息回能，循环一遍时间t，记录所有的f[i]。

2. 然后再循环一遍时间t，这次循环用普通的走路(17m/s他简直就是超人)。每次走路发现如果比闪烁方法更优(更远)的话，就更新f[i]，可以用一个式子来表示就是f[i]=Max(f[i],f[i-1]+17)。如果到了终点就退出然后输出Yes。

完整代码

#include<cstdio>
#include<cstring>
using namespace std;
int Max(int a,int b){
	return a>b?a:b;
}
int main(){
	int m,t,s,f[300010];
	memset(f,0,sizeof(f));
	scanf("%d%d%d",&m,&s,&t);
	for(int i=1;i<=t;i++){
		if(m>=10){
			m-=10;
			f[i]=f[i-1]+60;
		}else{
			m+=4;
			f[i]=f[i-1];
		}
	}
	for(int i=1;i<=t;i++){
		f[i]=Max(f[i-1]+17,f[i]);
		if(f[i]>=s){
			printf("Yes\n%d",i);
			return 0;
		}
	}
	printf("No\n%d",f[t]);
	return 0;
}

---

[USACO10OCT] Lake Counting S

题面翻译

由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 $N\times M(1\le N\le 100,1\le M\le 100)$ 的网格图表示。每个网格中有水（W） 或是旱地（.）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。

输入第 $1$ 行：两个空格隔开的整数：$N$ 和 $M$。

第 $2$ 行到第 $N+1$ 行：每行 $M$ 个字符，每个字符是 W 或 .，它们表示网格图中的一排。字符之间没有空格。

输出一行，表示水坑的数量。

题目描述

Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John’s field, determine how many ponds he has.

输入格式

Line 1: Two space-separated integers: N and M * Lines 2…N+1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them.

输出格式

Line 1: The number of ponds in Farmer John’s field.

样例 #1

样例输入 #1

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

样例输出 #1

3

提示

OUTPUT DETAILS: There are three ponds: one in the upper left, one in the lower left, and one along the right side.

---

很好的题目，使我英语水平提升

这个题目更是深搜和广搜中的典中典。这里我用深搜来写。

首先for循环遍历整个地图，遇到湖水就开始深搜并且ans++。dfs搜索九宫格的8个方向，把是湖水的地方，就把他改成陆地。遍历整张地图后ans就是湖泊的数量。

完整代码

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,map[110][110]={0};
int dx[8]={0, 0, 1, 1, 1,-1,-1,-1};
int dy[8]={1,-1, 1,-1, 0, 0, 1,-1};
void dfs(int x,int y){
	for(int k=0;k<8;k++){
		int tx=x+dx[k];
		int ty=y+dy[k];
		if(tx<1 || ty<1 || tx>n || ty>m)
			continue;
		if(map[tx][ty]==1){
			map[tx][ty]=0;
			dfs(tx,ty);
		}	
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			char ch;
			cin>>ch;
			if(ch=='W') map[i][j]=1;
			else map[i][j]=0;
		}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++)
//			printf("%d",map[i][j]);
//		printf("\n");
//		}	
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(map[i][j]==1){
				map[i][j]=0;
				ans++;
				dfs(i,j);
			}
		
	printf("%d",ans);
	
	return 0;
}

---

单词方阵

题目描述

给一 $n\times n$ 的字母方阵，内可能蕴含多个 yizhong 单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 $8$ 个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉，因此有可能共用字母。输出时，将不是单词的字母用 * 代替，以突出显示单词。

输入格式

第一行输入一个数 $n$。$(7\le n\le 100)$。

第二行开始输入 $n\times n$ 的字母矩阵。

输出格式

突出显示单词的 $n\times n$ 矩阵。

样例 #1

样例输入 #1

7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa

样例输出 #1

*******
*******
*******
*******
*******
*******
*******

样例 #2

样例输入 #2

8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg

样例输出 #2

*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g

---

纯纯暴力枚举，就是for循环有点多。

因为是字符输入，输入的时候记得把回车给过滤掉。

完整代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main(){
	int n;
	char map[110][110];
	int b[110][110];
	memset(b,0,sizeof(b));
	const char str[] = "yizhong";
	const int len = 7;
	//cout<<str<<endl;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			cin>>map[i][j];
		getchar(); // 读掉多余的回车 
	}
	int dx[8]={0,1,0,-1,1,-1,1,-1};
	int dy[8]={1,0,-1,0,1,1,-1,-1};
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(map[i][j]=='y'){
				for(int k=0;k<8;k++){
					int tx=i,ty=j;
					int flag = 0;
					for(int l=1;l<len;l++){
						tx += dx[k];
						ty += dy[k];
						if(tx <= 0 || ty <=0 || tx > n || ty > n){
							flag = 1;
							break;
						}
						if(map[tx][ty]!=str[l]){
							flag = 1;
							break;
						}
					}
					if(flag)
						continue;
					// 代表匹配出了一个yizhong 
					tx=i,ty=j; 
					//cout<<i<<" "<<j<<endl;
					for(int l=0;l<len;l++){
						b[tx][ty] = 1;
						tx += dx[k];
						ty += dy[k];
					}
				}
			}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			if(b[i][j])
				printf("%c",map[i][j]);
			else
				printf("*");
		printf("\n");
	}
	return 0;
} 

---

[NOIP2000 提高组] 单词接龙

题目背景

注意：本题为上古 NOIP 原题，不保证存在靠谱的做法能通过该数据范围下的所有数据。

本题为搜索题，本题不接受 hack 数据。关于此类题目的详细内容

NOIP2000 提高组 T3

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish，如果接成一条龙则变为 beastonish，另外相邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。

输入格式

输入的第一行为一个单独的整数 $n$ 表示单词数，以下 $n$ 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出格式

只需输出以此字母开头的最长的“龙”的长度。

样例 #1

样例输入 #1

5
at
touch
cheat
choose
tact
a

样例输出 #1

23

提示

样例解释：连成的“龙”为 atoucheatactactouchoose。

$n\le 20$。

---

这是一道关于字符串的搜索题，自然也要用上string的相关的函数，搜索用DFS。算上是一道好题。

完整代码

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
int n,book[30],ans=0,x;
char fletter;
string word[30];
bool check(string s1,string s2){
	int len1,len2;
	len1=s1.size();
	len2=s2.size();
	int j=0;
	for(int i=len1-1;i>=1;i--){
	    j++;
		if(j==len2) break;
		if(s1.substr(i)==s2.substr(0,j)){
			x=j;
			return true;
		}				
	}
	return false;	
}
void dfs(int len,int last){
	if(len>ans) ans=len;
	for(int i=1;i<=n;i++)
		if(book[i]<2 && check(word[last],word[i])){
			book[i]++;
			dfs(len+word[i].size()-x,i);
			book[i]--;
		}	
	return ;
}
int main(){
	scanf("%d",&n);
	memset(book,0,sizeof(book));
	for(int i=1;i<=n;i++)
		cin>>word[i];
	cin>>fletter;
	for(int i=1;i<=n;i++)
		if(word[i][0]==fletter){
			book[i]=1;
			dfs(word[i].size(),i);
			memset(book,0,sizeof(book));
		}
	printf("%d",ans);	
	return 0;
}

---

迷宫

题目描述

给定一个 $N\times M$ 方格的迷宫，迷宫里有 $T$ 处障碍，障碍处不可通过。

在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。

输入格式

第一行为三个正整数 $N,M,T$，分别表示迷宫的长宽和障碍总数。

第二行为四个正整数 $SX,SY,FX,FY$，$SX,SY$ 代表起点坐标，$FX,FY$ 代表终点坐标。

接下来 $T$ 行，每行两个正整数，表示障碍点的坐标。

输出格式

输出从起点坐标到终点坐标的方案总数。

样例 #1

样例输入 #1

2 2 1
1 1 2 2
1 2

样例输出 #1

1

提示

对于 $100\%$ 的数据，$1\le N,M\le 5$，$1\le T\le 10$，$1\le SX,FX\le n$，$1\le SY,FY\le m$。

---

也是一道典型的搜索题，这里我用DFS，把输入数据转换成一张map地图，用01标记可以走和不可以走。用book数组标记是否走过这块地方。

在dfs递归的地方一定要记得回溯，把book[tx][ty] = 0改回来。dfs深搜边界就是xy到了终点，ans++。最后输出ans。

还有一个坑，就是起点要标记为已经走过了，book[sx][sy] = 1。不然会有部分测试点过不了。

完整代码

#include<cstdio>
#include<cstring>
using namespace std;
int map[10][10],book[10][10];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int n,m,fx,fy,ans=0;
void dfs(int x,int y){
	if(x==fx && y==fy){
		ans++;
		return ;
	}
	for(int k=0;k<4;k++){
		int tx = x + dx[k];
		int ty = y + dy[k];
		if(tx<=0 || ty<=0 || tx>n || ty>m)
			continue;
		if(map[tx][ty] == 0 && book[tx][ty] == 0){
			book[tx][ty] = 1;
			dfs(tx,ty);
			book[tx][ty] = 0;
		}
	}
}
int main(){
	int t,sx,sy;
	memset(map,0,sizeof(map));
	scanf("%d%d%d%d%d%d%d",&n,&m,&t,&sx,&sy,&fx,&fy);
	for(int i=1;i<=t;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		map[x][y] = 1;
	}
	memset(book,0,sizeof(book));
	book[sx][sy] = 1; // 不然就会是40分 
	dfs(sx,sy);		
	printf("%d",ans);
	return 0;
}

后记

本篇为洛谷题解后7篇。