【新初二暑假集训第一期day1晚间测试】题解

题解"/>

【新初二暑假集训第一期day1晚间测试】题解

话说发的是不是晚了点

T1 性格公交车(bus.cpp)

考点：队列+栈

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

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

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

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

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

接下来，处理各种人。

1. 处理内向的人

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

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

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

2. 处理外向的人

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

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

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

应该写的算清楚，都懂？

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

T2 表达式求值

考点：栈

这不比这道简单百倍？

首先，处理输入。

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

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

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

接下来，考虑符号：

1. ch 是加号

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

2. ch 是乘号

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

3. ch 是其他符号

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

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

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

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

T3 题海战

考点：set

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

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

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

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

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

养 set 千日，用 set 一时

首先，处理学生的题目。

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

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

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

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

1. 比赛

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

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

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

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

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

我认为我应该讲清楚了

2. 训练

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

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

所以，用 1 1 1 重循环枚举 f l a g flag flag ，当 f l a g [ i ] = q flag[\ i\ ]=q flag[ i ]=q（参赛学生数）时，输出当前的 i i 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 flag 二维数组。

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

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

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

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

T5 潜水员

考点： 二维费用背包

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

定义状态：

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

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

d p [ i ] [ j ] [ k ] = min ⁡ ( d p [ i − 1 ] [ j ] [ k ] , d p [ i − 1 ] [ j − a [ i ] ] [ k − b [ i ] ] + c [ i ] ) dp[\ i\ ][\ j\ ][\ k\ ]=\min(dp[\ i-1\ ][\ j\ ][\ k\ ],dp[\ i-1\ ][\ j-a[\ i\ ]\ ][\ k-b[\ i\ ]\ ]+c[\ i\ ]) dp[ i ][ j ][ k ]=min(dp[ i−1 ][ j ][ k ],dp[ i−1 ][ j−a[ i ] ][ k−b[ i ] ]+c[ i ])

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

d p [ j ] [ k ] = min ⁡ ( d p [ j ] [ k ] , d p [ j − a [ i ] ] [ k − b [ i ] ] + c [ i ] ) ( 1 ⩽ i ⩽ n ) dp[\ j\ ][\ k\ ]=\min(dp[\ j\ ][\ k\ ],dp[\ j-a[\ i\ ]\ ][\ k-b[\ i\ ]\ ]+c[\ i\ ])(1\leqslant i \leqslant n) dp[ j ][ k ]=min(dp[ j ][ k ],dp[ j−a[ i ] ][ k−b[ i ] ]+c[ i ])(1⩽i⩽n)

注意初始化:

d p [ j ] [ k ] = { 0 j = 0 , k = 0 2 31 − 1 j ≠ 0 , k ≠ 0 dp[\ j\ ][\ k\ ]=\begin{cases}0&j=0,k=0\\2^{31}-1&j\neq0,k\neq0\end{cases} dp[ j ][ k ]={0231−1​j=0,k=0j​=0,k​=0​

但是！

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

所以，我们在进行循环跑 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]);}}
}

但是，因为我们进行了特殊的处理，所以答案不应该在 d p [ u ] [ v ] dp[\ u\ ][\ v\ ] 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");			//无解

那么这题也就完成了。