XP03B班-复赛模拟赛-03 题解
2026-08-15 13:27:57
发布于：浙江
T1.
(.v.*))
时间限制：1000ms
内存限制：128MB
请编写C++程序，输出以下句子：
\(.v.*\))
输入格式
无。
输出格式
输出: \(.v.*\))
提示说明
答：
很明显直接输出"\(.v.*\))"
p.s.
反斜杠要输出两个
代码
#include<bits/stdc++.h>
using namespace std;
int main() {
cout<<"\\(.v.*\\))";
return 0;
}
T2.
到底谁是真的「别叫我敲代码」
时间限制：1000ms
内存限制：128MB
班级里突然冒出了三个「别叫我敲代码」！老师说真正的「别叫我敲代码」有一个特殊暗号——这个暗号是一个大于等于10且小于等于99的偶数。现在三个"冒牌货"每人报了一个数字，请你帮老师找出真正的「别叫我敲代码」是第几个人。
如果有多个人符合条件，输出最小的那个序号。如果三个人都不符合，输出 0。
输入格式
一行，三个int范围内的整数 a、b、c，分别表示三个人报出的数字。
输出格式
一行，一个整数，表示真正的「别叫我敲代码」是第几个人（1、2或3）。如果都不符合，输出 0。
样例组
输入#1
15 22 37
输出#1
2
输入#2
11 33 55
输出#2
0
输入#3
8 44 66
输出#3
2
提示说明
样例一：22是偶数且在10~99之间，第2个人是真的
样例二：三个数都不是偶数，没有真的
样例三：8小于10不符合，44和66都符合，取最小的序号2
答：
很明显只要满足：
1.等于10且小于等于99的偶数
2.如果有多个人符合条件，输出最小的那个序号。如果三个人都不符合，输出 0。
3.如果都不符合，输出 0。
就可以输出了
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,c;
cin>>a>>b>>c;
if(a%2==0&&a>=10&&a<=99) {
cout<<1;
return 0;
}
else if(b%2==0&&b>=10&&b<=99) {
cout<<2;
return 0;
}
else if(c%2==0&&c>=10&&c<=99) {
cout<<3;
return 0;
}
else cout<<0;
return 0;
}
T3.
丧尸病毒传播（填空）
时间限制：1000ms
内存限制：128MB
这是一道可爱的填空题，你只要在初始代码中进行修改即可。
某编号为 x 的城市中，一个生物实验室爆炸了，里面的特制病毒漏了出来，被病毒感染的人都变成丧尸。丧尸是非常凶恶且异常的，为了寻找食物，会往其它城市进行游走扩散。只有两个城市之间有道路的情况下，丧尸才能够游走到另一个城市。
为了方便问题的描述，所有城市用整数编号来表示。倘若共有 n 座城市，有 m 条单向通行的道路信息，每条道路，丧尸们都需要 1 个单元的时间通过，请问，丧尸到达每座城市的最早时间是多少？
输入格式
第一行两个整数 n，m ，表示有 n 座城市与 m 条道路
从第二行开始的 m 行，每行两个整数 u，v，表示有 (u,v) 这条道路
最后一行一个 x 表示爆发处
输出格式
一行 n 个整数，第 i 个整数表示丧尸到达第 i 座城市的时刻。无法到达，则输出 −1
样例组
输入#1
5 8
2 3
3 4
2 1
3 1
4 1
1 5
4 5
2 5
1
输出#1
0 -1 -1 -1 1
输入#2
5 8
2 3
4 3
1 2
1 3
1 4
1 5
4 5
5 2
5
输出#2
-1 1 2 -1 0
提示说明
1≤n≤1000,1≤m≤10000
答
很明显
这是一道可爱的填空题，你只要在初始代码中进行修改即可。
于是乎
我们只要填：
//起点层为0 ceng[u]= 0
//邻居x未走过 ceng[x]==-1
//x层 是 t的层+1 ceng[x]=ceng[t]+1
//v是u的邻居节点 G[u].push_back(v)
即可
代码
#include<bits/stdc++.h>
using namespace std;
vector<int>G[1010];//G[x] 存x所有的邻居
int n,m,u,v,ceng[1010];//ceng[y] 起点到y的最短距离（最早感染时间），-1表示到不了
void bfs(int u){
memset(ceng,-1,sizeof ceng);
queue<int>q;
q.push(u);
ceng[u]= 0;//起点层为0
while(!q.empty()){
int t=q.front();
q.pop();
for(auto x:G[t]){
if(ceng[x]==-1){//邻居x未走过
q.push(x);
ceng[x]=ceng[t]+1;//x层 是 t的层+1
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v;//v是u的邻居节点
G[u].push_back(v);
}
int x;
cin >> x;
bfs(x);
for(int i = 1;i <= n;i++) cout << ceng[i] << " ";
return 0;
}
T4.
新蚂蚁上岗
时间限制：1000ms
内存限制：128MB
工厂接了一批新的车间杂活，雷震震招了一批新蚂蚁来干。可这些新蚂蚁还在实习期——有的活它们还没学会！雷主任只能在"每只蚂蚁会干的活"里派工，还得照旧算出最省的方案。
工厂新接了 n 项车间任务，正好交给 n 只蚂蚁去做，每只蚂蚁做每项任务所需的报酬各不相同。
不过，有些蚂蚁还不会做某些任务：在输入中，如果某个数是 0，就表示这只蚂蚁不会做这项任务。
雷震震要给每只蚂蚁恰好安排 1 项不同、且它会做的任务，使总报酬最少（保证一定存在合法的安排方案）。请算出这个最小总报酬。
输入格式
第一行 1 个正整数 n (1<n≤15)。
接下来 n 行，每行 n 个数，第 i 行第 j 个数表示第 i 只蚂蚁做第 j 项任务的报酬；若为 0 表示不会做（1≤ 报酬 ≤100）。
输出格式
一个整数，表示最小总报酬。
样例组
输入#1
3
0 2 3
2 4 6
5 0 4
输出#1
8
提示说明
样例说明：
蚂蚁 1 还不会做任务 1
蚂蚁 3 还不会做任务 2。
安排：蚂蚁 1 做任务 2（2）
蚂蚁 2 做任务 1（2）
蚂蚁 3 做任务 3（4）
总报酬 2+2+4=8，最省。
答:
这是一道全排序的变题：
不同点：
在输入中，如果某个数是 0，就表示这只蚂蚁不会做这项任务。
那么我们可以用dfs(深度优先搜索)解决此题
p.s.
这是算最小总和并非下表
代码
#include<bits/stdc++.h>
using namespace std;
int a[20][20];
int n,ans=1e9,vis[20];
void dfs(int dep,int sum){
if(sum>=ans) return;
if(dep>n) {
ans=sum;
return ;
}
for(int i=1;i<=n;i++){
if(vis[i]==1||a[dep][i]==0) continue;
else{
vis[i]=1;
dfs(dep****um+a[dep][i]);
vis[i]=0;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
dfs(1,0);
cout<<ans;
return 0;
}
T5.
比尔吉沃特的潮汐
时间限制：1000ms
内存限制：128MB
古墓线索指向海港之城比尔吉沃特(Bilgewater)。通往灯塔的礁石栈道随潮水起落,潮神俄洛伊(Illaoi)警告:「海水会吞没低地。算准它,否则葬身浪底。」
海域是 n×m 网格,每格高度 h [i][j]
。海平面是一个整数 L;当 海平面 L ≥ 格子高度 时该格被淹没、不可通行。普朗克要从起点 S 走到终点 T(四方移动)。
求海平面最高能涨到多少(整数 L),仍存在一条从 S 到 T 的可通行路径(路径上每个格子都满足 h>L)。
输入格式
第一行 n,m。接下来 n 行每行 m 个整数 h [i][j]
。最后一行四个整数 sr sc tr tc(起点、终点坐标,均从 1 开始)。
输出格式
一个整数:最大可行海平面 L。
样例组
输入#1
3 3
5 5 5
1 1 5
5 5 5
1 1 3 3
输出#1
4
样例说明
沿最上行再向下走右列(全是高度 5)可避开高度 1 的低地,路径最低高度为 5,故海平面最高涨到 4 仍可通行。
数据范围
1≤n,m≤500
1≤h [i][j] ≤。
答：
这是一道典型的bfs(广度优先搜索)
so
我们直接套模板然后用二分进行查找最大可行海平面
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[510][510],vis[510][510];
int dx[10]={0,-1,0,0,1},dy[10]={0,0,-1,1,0};
long long fx,fy,ex,ey;
struct node{
int x,y;
};
void bfs(int mid){
memset(vis,0,sizeof(vis));
queue<node>q;
q.push({fx,fy});
vis[fx][fy]=1;
while(!q.empty()){
node r=q.front();
q.pop();
for(int i=1;i<=4;i++){
int nx=r.x+dx[i];
int ny=r.y+dy[i];
if((nx>=1&&nx<=n)&&ny>=1&&ny<=m&&vis[nx][ny]==0&&a[nx][ny]-mid>0){
q.push({nx,ny});
vis[nx][ny]=1;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
cin>>fx>>fy>>ex>>ey;
int l=0,r=1e6,ans=0;
while(l<=r){
int mid=(l+r)/2;
bfs(mid);
if(vis[ex][ey]==1){
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
cout<<ans;
return 0;
}
T6.
皮尔特沃夫的信号
时间限制：1000ms
内存限制：128MB
最终线索在进步之城皮尔特沃夫(Piltover)。发明家杰斯(Jayce)同时点亮多座海克斯信号塔,信号向全城扩散——唯有全城被照亮,昭阳碎片的封印才会显现。
城市是 n×m 网格:* 信号塔(可能多个),# 障碍(信号无法通过),. 空地。每过一秒,所有已有信号的格子向四方各扩散一格。
求最少多少秒后,全图所有可达的非障碍格都收到信号;若存在永远收不到信号的非障碍格,输出 -1。
输入格式
第一行 n,m。接下来 n 行,每行长度为 m 的字符串。
输出格式
覆盖全图所需的最少秒数;若有不可达的空地,输出 -1。
样例组
输入#1
3 3
*..
.#.
..*
输出#1
2
提示说明
样例说明
两座塔分别在左上、右下角,墙在中心。各格被最近的塔点亮,最晚被点亮的格子用时 2 秒。
数据范围
1≤n,m≤1000。
答：
明显de这道题其实就是水墨扩散+障碍(#)
所以3，2，1上
代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,vis[1010][1010],ans=-1;
long long dx[10]={0,-1,0,0,1},dy[10]={0,0,-1,1,0};
char a[1010][1010];
struct node{
long long dep,x,y;
};
void dfs(){
queue<node>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='*'){
q.push({0,i,j});
vis[i][j]=1;
}if(a[i][j]=='#'){
vis[i][j]=1;
}
}
}
while(q.size()){
node r=q.front();
q.pop();
for(int i=1;i<=4;i++){
long long nx=r.x+dx[i];
long long ny=r.y+dy[i];
long long nd=r.dep+1;
if((nx>=1&&nx<=n)&&ny>=1&&ny<=m&&vis[nx][ny]==0){
q.push({nd,nx,ny});
ans=nd;
vis[nx][ny]=1;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
dfs();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(vis[i][j]==0) {
cout<<-1;
return 0;
}
}
}
cout<<ans;
return 0;
}
T7.
奶酪迷宫
时间限制：1000ms
内存限制：128MB
雪鼠来到了一座奶酪迷宫。迷宫可以看成一个 n×n 的方格，每个方格中都有一定数量的奶酪，第 i 行第 j 列的奶酪数量为 a[i][j]。
雪鼠一开始站在左上角 (1,1)。每次移动时，它可以选择上、下、左、右四个方向之一，并沿这个方向移动 1 到 k 格。
但是雪鼠非常挑剔：它只能移动到奶酪数量严格更多的格子。也就是说，如果当前在 (x,y)，下一步移动到 (nx,ny)，必须满足：
a[nx][ny]>a[x][y]
雪鼠每到达一个格子，就会吃掉该格子里的所有奶酪。同一个格子不会被重复经过，因为每次移动后奶酪数量都必须严格变大。
请你求出雪鼠从 (1,1) 出发，最多可以吃到多少奶酪。
输入格式
第一行输入两个整数 n,k，表示迷宫大小为 n×n，并且雪鼠每次移动时最多可以沿上、下、左、右某一个方向移动 k 格。
接下来 n 行，每行 n 个整数，第 i 行第 j 个整数表示 a[i][j]，即第 i 行第 j 列格子中的奶酪数量。
输出格式
输出一个整数，表示雪鼠最多可以吃到的奶酪总数。
样例组
输入#1
3 1
1 2 3
6 5 4
7 8 9
输出#1
45
提示说明
样例解释
从 (1,1) 出发，可以按照蛇形路线移动：
1−>2−>3−>4−>5−>6−>7−>8−>9
总和为：
1+2+3+4+5+6+7+8+9=45
所以答案为 45。
数据范围与子任务表
对于所有测试点，保证：
1≤n≤300
1≤k≤n
1≤a[i][j]≤
本题共 20 个测试点，每个测试点 5 分。
| 子任务 | 测试点编号 | 分值 | 数据范围 |
|---|---|---|---|
| 1 | 1∼4 | 20 | 1≤n≤5, k=1 |
| 2 | 5∼8 | 20 | 1≤n≤30, k=1 |
| 3 | 9∼12 | 20 | 1≤n≤50, 1≤k≤10 |
| 4 | 13∼16 | 20 | 1≤n≤150, 1≤k≤100 |
| 5 | 17∼20 | 20 | 1≤n≤300, 1≤k≤300 |
答：
滑雪的变题：
1.它只能移动到奶酪数量严格更多的格子
2.雪鼠每次移动时最多可以沿上、下、左、右某一个方向移动 k 格。
代码
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[510][510],vis[510][510],ans[510][510];
long long dx[10]={0,-1,0,0,1},dy[10]={0,0,1,-1,0};
long long dfs(long long x,long long y){
if(ans[x][y]!=0)return ans[x][y];
long long maxn=a[x][y];
for(int i=1;i<=4;i++){
for(int j=1;j<=k;j++){
long long nx=x+j*dx[i];
long long ny=y+j*dy[i];
if(nx>0&&nx<=n&&ny>0&&ny<=n&&a[nx][ny]>a[x][y]){
maxn=max(maxn,dfs(nx,ny)+a[x][y]);
}
}
}
return ans[x][y]=maxn;
}
int main(){
cin>>n>>k;
long long maxans=0;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
cout<<dfs(1,1);
return 0;
}
这里空空如也
有帮助，赞一个