开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【新初二暑假集训第一期day1晚间测试】题解 -> 正文阅读

[数据结构与算法]【新初二暑假集训第一期day1晚间测试】题解

~~话说发的是不是晚了点~~

T1 性格公交车(bus.cpp)

考点：队列+栈

首先，我们都会想到写一个包含 $n u m$ 和 $s u m$ 的结构体，在完成输入后，按照如下方式排列：

bool cmp(node a,node b){
	return a.sum<b.sum;
}

具体含义不用赘述，排完之后，就会得到按照座位长度升序排序的座位号。

~~所以和队列跟栈有什么关系？~~

当然有！首先用一个队列把排序后的座位号塞进去。（此时，队列里的座位号都是空的）

接下来，处理各种人。

处理内向的人

内向的人总是选择两个座位都是空的一排。在这些空座位排当中，选择一排座位宽度最小的，并占了其中的一个座位

前面我们所定义的队列里的每一个座位号都是空的，而队首座位号对应的座位的长度是最短的

所以，我们需要输出队首的座位号，并将其压入栈（此时，栈里的座位号都只坐了 1 个人），再删掉。

处理外向的人

外向的人总是选择一个内向的人所占的那排座位。在这些座位排当中，选择一排座位宽度最大的，并在其中占据了空位。

我们分别从两段加黑文字中，得到两个信息：

外向的人的座位号必须在栈里面找（栈里的座位号都只坐了 1 个人）
外向的人的座位是栈顶【排序过后，先压入栈内的对应的座位的长度是较短的，后压入栈内的对应的座位的长度是较长的）的座位号

~~应该写的算清楚，都懂？~~

处理了外向的人之后，将栈顶座位号弹出即可。

T2 表达式求值

考点：栈

~~这不比这道简单百倍？~~

首先，处理输入。

输入方式应该是有多种，这里我采用了如下输入方式：

while(1){
	scanf("%lld%c",&n,&ch);//分别输入数字和字符
}

由于只求最后四位，所以进行预处理，即对 $n$ 取模 $10000$

接下来，考虑符号：

ch 是加号

我们直接将 $n$ 压入栈中，不做处理。

ch 是乘号

弹出栈顶元素，与 $n$ 相乘，再压入栈中（注意取模）。

ch 是其他符号

输入结束了，跳出输入循环。

完成输入后，我们就处理了所有乘号，只剩下了加号。

换言之，我们只需要将栈里面的元素全部相加即可。（注意取模）

个人认为是水题一道，也是考试当天上午的重点讲解题目（~~没做起的建议回炉重造~~），不再赘述，下一题。

T3 题海战

考点：set

~~话说我的做法和GM做法不太一样？~~

第 $2$ ~ $n + 1$ 行，先是 $1$ 个正整数 $p$ ，然后 $p$ 个整数表示第 $i$ 个学生的做题记录(可以重复做同一道题)。

从这段话中，我们可以得到两个信息：

做题顺序不一定是有序的
可能有重复做的题

所以，我们要做两个操作：排序和去重

~~养 set 千日，用 set 一时~~

首先，处理学生的题目。

考虑有多个学生，所以我们要定义一个 set 数组，即：

set<int> s[105];//set[i]表示第 i 个学生的完成的题目的升序排序后的结果

接下来，按照题目要求输入。（~~你不要告诉我你不会输入~~）

然后，处理每一场比赛或训练应该准备的题目

比赛

准备一个 int 类型的 $f l a g$ 数组，其中， $flag[\ i\ ]$ 表示有 $i$ 个要参加比赛的学生学生完成了第 $i$ 题。

一个两重循环即可完成该任务（第 $1$ 重循环枚举学生，第 $2$ 重循环枚举当前学生所完成的题目）。

亲测，不用去重，不会超时。

对于每场比赛，他要保证所出的题没有任何一道已有任何一个学生做过

所以，再用 $1$ 重循环枚举 $f l a g$ ，当 $flag[\ i\ ]=0$ 时，输出当前的 $i$ 。

~~我认为我应该讲清楚了~~

训练

前面的步奏和处理比赛一模一样，但最后一步有所不同。

而对于每场训练，他要保证所出的所有题都被每一个参赛学生做过

所以，用 $1$ 重循环枚举 $f l a g$ ，当 $flag[\ i\ ]=q$ （参赛学生数）时，输出当前的 $i$ 。

这题就完成了？

注意：这里有个大坑点！！！

每行的第1个整数type表示是训练或者比赛(1为训练，非1为比赛)

所以，我们应该写成：

if(type==1){
	训练代码
}else{
	比赛代码
}

而不是：

if(type==0){
	比赛代码
}else{
	训练代码
}

相信大家都应该看得出来。下一题。

T4 四色地图

考点：DFS

输入有些麻烦，结合代码：

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d ",&m);			//处理第 m 个区域
		char ch;
		while(1){			//由于我们不知道第 m 个区域与多少个区域相连，所以使用无限循环
			scanf("%d%c",&x,&ch);			//输入数字以及其后面的字符
			len[m]++;			//与第 m 个区域相邻的区域的数量增加
			a[m][len[m]]=x;			//记录
			if(ch!=' '){			//如果 ch 不是空格，说明已经换行了，跳出循环，进行第 m+1 个区域的输入
				break;
			}
		}
	}
	dfs(1);			//开始搜索
	return 0;
}

关于搜索，方法很多。以下仅代表个人观点。

我们可以定义一个 $f l a g$ 二维数组。

其中： $flag[\ i\ ][\ j\ ]$ 表示第 $i$ 个区域是否可以涂 $j$ 号颜色。

对于每一个区域 $i$ ，我们可以从 $1\sim4$ 进行遍历，当 $flag[\ i\ ][\ j\ ]$ 为 $0$ 时，说明我们可以选择该颜色进行填涂，那么我们将该颜色 $j$ 存储在一个 $a n s$ 数组里，并将所有与 $i$ 区域相邻的 $k$ 区域标记： $flag[\ k\ ][\ j\ ]=1$ （即第 $k$ 个区域不能用颜色 $j$ 填涂）

完成了这些处理之后，我们就可以进行下一步搜索了。

当搜索完成后，我们只需要输出 $a n s$ 数组即可。

T5 潜水员

考点： 二维费用背包

这是一道变式二维背包，首先，回顾一下一般二维背包的状态定义以及状态转移方程。

定义状态：

$dp[\ i\ ][\ j\ ][\ k\ ]$ 表示选择前 $i$ 个物品，氧气最多为 $j$ ，氮气最多为 $k$ 时的最小重量。

对于第 $i$ 个物品，我们都有选与不选两种状态，则我们容易得到状态转移方程：

$dp[\ i\ ][\ j\ ][\ k\ ]=\min(dp[\ i-1\ ][\ j\ ][\ k\ ],dp[\ i-1\ ][\ j-a[\ i\ ]\ ][\ k-b[\ i\ ]\ ]+c[\ i\ ])$

当然，这个方程太复杂了，所以，我们可以~~降维打击~~，简化状态转移方程：

$dp[\ j\ ][\ k\ ]=\min(dp[\ j\ ][\ k\ ],dp[\ j-a[\ i\ ]\ ][\ k-b[\ i\ ]\ ]+c[\ i\ ])(1\leqslant i \leqslant n)$

注意初始化:

$dp[\ j\ ][\ k\ ]=\begin{cases}0&j=0,k=0\\2^{31}-1&j\neq0,k\neq0\end{cases}$

但是！

如果不能恰好带这么多气体，允许多带一些(先考虑氧气最小，再考虑氮气最小)。

所以，我们在进行循环跑 DP 时，就需要用一些小技巧：

for(int i=1;i<=n;i++){			//n 个物品
	for(int j=u+100;j>=a[i];j--){			//因为可以允许多带一些气体，所以我们应该从 u+一些数 开始跑循环
											//而题目已知 ai 和 bi 都在区间 [1,100] 以内，所以，我们就应该从 u+100 开始跑循环
		for(int k=v+100;k>=b[i];k--){			//同上
			dp[j][k]=min(dp[j][k],dp[j-a[i]][k-b[i]]+c[i]);
		}
	}
}

但是，因为我们进行了特殊的处理，所以答案不应该在 $dp[\ u\ ][\ v\ ]$ 中。

for(int i=u;i<=u+100;i++){			//因为可以多带，所以要进行循环枚举
	for(int j=v;j<=v+100;j++){
		if(dp[i][j]!=0x3f3f3f3f){			//该情况是有解的
			printf("%d",dp[i][j]);			//直接输出，因为题目要求先考虑氧气最小，再考虑氮气最小
				return 0;
		}
	}
}
printf("-1");			//无解