8.24测试总结

· · 算法·理论

8.21测试总结

P2895 [USACO08FEB] Meteor Shower S

得分:21

应得:100

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

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

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,再进行bfs(广度优先搜索)，不过多了一个条件-现在的时间这里没有被破坏

数组的记录:

    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(广度优先搜索)代码

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;
}

完整代码:

#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 篝火问题

得分:0

应得:100

考点:map + pair

错误思路:输出n个0

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

完整代码:

#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;
}