专栏文章

8.24测试总结

LLuck_Deepsea
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio5s9mu
此快照首次捕获于
2025/12/02 13:49
3 个月前
此快照最后确认于
2025/12/02 13:49
3 个月前
查看原文

8.218.21测试总结

P2895[USACO08FEB]MeteorShowerSP2895 [USACO08FEB] Meteor Shower S

得分:2121

应得:100100

考点:bfsbfs(广度优先搜索)

错误思路:使用多个数组存储信息,进行bfsbfs(广度优先搜索)，十分暴力,最终TLETLE

CPP
1.
    struct node{
	int x,y,step;
    }a[50005];//存储输入的信息

2.
    bool vis[355][355];//是否到达过

3.
    bool mp[355][355]；//实时地图(某个时刻mp[x][y]是否能走)

4.
    bool mb[355][355];//mb[x][y]是否永远安全

5.
    int dx[]={0,0,-1,1};
    int dy[]={1,-1,0,0};//方向数组

6.
    queue<node>q;//队列

正确思路:使用一个数组记录最早破坏时间,初始化为−1-1,再进行bfsbfs(广度优先搜索)，不过多了一个条件-现在的时间这里没有被破坏

数组的记录:

CPP
    memset(a,-1,sizeof a);
	int n;
	cin>>n;
	while(n--)
	{
		int x, y, t;
		cin>>x>>y>>t;
		if(a[x][y]==-1)
		{
			a[x][y]=t;
		}
		else
		{
			a[x][y]=min(a[x][y],t);
		}
		for(int i=0;i<4;i++)
		{
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(xx>-1&&yy>-1)
			{
				if(a[xx][yy]==-1)
				{
					a[xx][yy]=t;
				}
				else
				{
					a[xx][yy]=min(a[xx][yy],t);
				}
			}
		}
	}

bfsbfs(广度优先搜索)代码

CPP
void bfs(int x,int y){
	q.push({x,y});
	vis[x][y]=1;
	while(q.size()){
		node f=q.front();
		q.pop();
		if(a[f.x][f.y]==-1){
			cout<<f.t;
			return;
		}
		for(int i=0;i<4;i++){
			int tx=f.x+dx[i];
			int ty=f.y+dy[i];
			if(tx>-1&&ty>-1&&(a[tx][ty]==-1||a[tx][ty]!=-1&&a[tx][ty]>f.t+1)&&!vis[tx][ty]){
				q.push({tx,ty,f.t+1});
				vis[tx][ty]=1;
			}
		}
	}
	cout<<-1;
}

完整代码:

CPP
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,t;
};
int a[505][505];
bool vis[505][505];
queue<node>q;
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
void bfs(int x,int y){
	q.push({x,y});
	vis[x][y]=1;
	while(q.size()){
		node f=q.front();
		q.pop();
		if(a[f.x][f.y]==-1){
			cout<<f.t;
			return;
		}
		for(int i=0;i<4;i++){
			int tx=f.x+dx[i];
			int ty=f.y+dy[i];
			if(tx>-1&&ty>-1&&(a[tx][ty]==-1||a[tx][ty]!=-1&&a[tx][ty]>f.t+1)&&!vis[tx][ty]){
				q.push({tx,ty,f.t+1});
				vis[tx][ty]=1;
			}
		}
	}
	cout<<-1;
}
int main()
{
	memset(a,-1,sizeof a);
	int n;
	cin>>n;
	while(n--)
	{
		int x, y, t;
		cin>>x>>y>>t;
		if(a[x][y]==-1)
		{
			a[x][y]=t;
		}
		else
		{
			a[x][y]=min(a[x][y],t);
		}
		for(int i=0;i<4;i++)
		{
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(xx>-1&&yy>-1)
			{
				if(a[xx][yy]==-1)
				{
					a[xx][yy]=t;
				}
				else
				{
					a[xx][yy]=min(a[xx][yy],t);
				}
			}
		}
	}
	bfs(0,0);
	return 0;
}

T644252篝火问题T644252 篝火问题

得分:00

应得:100100

考点:map+pairmap + pair

错误思路:输出nn个00

正确思路:由于模拟烟雾会TLETLE(超时),因此想到烟雾不变,去偏移原点(篝火)和目标(人),就可以避免超时,得到正解

完整代码:

CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int>pii;
string s;
int n,r,c,nx,ny;
map<pii,bool>mp;
signed main()
{
	cin>>n>>r>>c;
	cin>>s;
	mp[{0,0}]=1;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='N')
        {
            nx--;
        }
		else if(s[i]=='S')
        {
            nx++;
        }
		else if(s[i]=='E')
        {
            ny++;
        }
		else //偏移原点和人
        {
            ny--;
        }
		mp[{-nx,-ny}]=1;
		if(mp[{r-nx,c-ny}]==1)//人被烟覆盖
		{
			cout<<1;
		}
		else//人m没有被烟覆盖
		{
			cout<<0;
		}
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...