首页 > 其他分享 >[刷题笔记] LuoguP2658 汽车拉力比赛

[刷题笔记] LuoguP2658 汽车拉力比赛

时间:2023-06-04 09:57:35浏览次数:52  
标签:二分 拉力 int mark bfs LuoguP2658 PAIR include 刷题

Problem

Solution

需要找到最小满足题意的\(d\),显然\(d\)满足单调性,考虑二分

二分\(d\),然后直接bfs,每次bfs判断能不能走的时候还需要加上高度差不超过二分的\(d\)(即满足),bfs跑完后看看所有的路标都被访问了没。(可以记录个数,因为不可能重复走)

二分的时候注意\(l\)从0开始,不然会WA on test 5(答案可以为0)

还是一道很有意思的bfs呢

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> PAIR;
int m,n;
int mapp[N][N];
int mark[N][N];
int sx,sy;
int vis[N][N];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int std_mark = 0;
bool check(int d)
{
    queue <PAIR> q;
    q.push(PAIR(sx,sy));
    vis[sx][sy] = 0;
    int cnt = 1;
    while(!q.empty())
    {
        if(cnt == std_mark) return true;
        PAIR p = q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int ax = p.first + dx[i];
            int ay = p.second + dy[i];
            if(ax>=1&&ax<=m&&ay>=1&&ay<=n&&vis[ax][ay] == INF&&abs(mapp[p.first][p.second] - mapp[ax][ay])<=d)
            {
                if(mark[ax][ay]) 
                {
                //    cout<<"ok"<<endl;
                    cnt ++;
                }
                q.push(PAIR(ax,ay));
                vis[ax][ay] = 1;
            }
        }
    }
    if(cnt == std_mark) return true;
    else return false;
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++) scanf("%d",&mapp[i][j]);
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++) 
        {
            scanf("%d",&mark[i][j]);
            if(mark[i][j]) sx=i,sy=j,std_mark ++;
        }
    }
    int l = 0,r = INF;
    while(l <= r)
    {
     //   cout<<l<<" "<<r<<endl;
        memset(vis,INF,sizeof(vis));
        int mid = (l+r)/2;
        if(check(mid)) r = mid -1;
        else l = mid + 1;
    }
    cout<<l<<endl;
    return 0;
}   

标签:二分,拉力,int,mark,bfs,LuoguP2658,PAIR,include,刷题
From: https://www.cnblogs.com/SXqwq/p/17455232.html

相关文章

  • [刷题笔记] ybt1250:The Castle
    ProblemSolution显然bfs,只不过扩散的时候需要判断墙那么如何判断墙呢?题目只给出了每个方块墙方向的和原来的思路是可以暴力,很复杂但是可做,代码就不给了。后来教练讲到了可以用位运算巧妙实现,这里重点介绍一下:首先,我们观察一下每面墙代号的二进制:十进制二进制100......
  • [刷题笔记] ybt1255:迷宫问题
    题目传送门Solution数据范围很小,一共才\(5\times5\),所以乱搞做法很多比如我一开始就先bfs单纯跑最短路,然后dfs找路径但是忘回溯被嘲讽其实可以边bfs边记录路径,因为bfs是按层数搜的,所以第一次到达终点的路径一定是最优的。那么如何记录路径呢?我原来用pair,经教练指导发现可以......
  • 算法刷题记录:素数中的等差数列
    题目链接https://ac.nowcoder.com/acm/contest/19859/I题目分析模拟!模拟!模拟!下标要计算好。自己的思路是放发现两个相等的差时,说明至少可以输出了,也就是合法情况,然后用指针R往后扩展。我选择的R是闭区间的,即[L,R]的区间已经看过了,所以i可以直接从i+1开始看。所以R赋值给i后......
  • 算法刷题记录:[NOIP1999]回文数
    题目链接https://ac.nowcoder.com/acm/contest/19859/G题目分析高精度相加+进制转换+判断回文的模拟题。AC代码//Problem:[NOIP1999]回文数//Contest:NowCoder//URL:https://ac.nowcoder.com/acm/contest/19859/G//MemoryLimit:262144MB//TimeLimit:20......
  • 算法刷题记录:素数五五
    题目链接https://ac.nowcoder.com/acm/contest/19859/E题目分析一道找规律的题,我们注意33,当33的长度一样,我们只要无脑添加4和8即可。4和8的关系与33的关系:有n个33,就有n-1个4或8。在此基础之上,因为会出现a和b的33长度不相同的情况,这时候我们只要统计a和b的33个数的差就行了......
  • 2023-06-03 刷题
    练习英文描述算法56.合并区间-力扣(LeetCode)[mid,非常好展示思路]分析:Firstsorttheintervalsbystarttime,sothatwecaneasilyfindwhichintervalscanbemergedbycheckingintervalsfromlefttoright.Useoneexampletodemotheprocess.(e.g.use......
  • 2023年5月刷题记录
    2023年5月1日leetcode1376.通知所有员工所需的时间链接地址:https://leetcode.cn/problems/time-needed-to-inform-all-employees/题意:公司里有n名员工,每个员工的ID都是独一无二的,编号从0到n-1。公司的总负责人通过headID进行标识。在manager数组中,每个员工都......
  • 算法刷题记录:日历中的数字
    题目链接https://ac.nowcoder.com/acm/contest/19859/B题目分析很简单的一道数位统计的题目其中年和月是乘法原理。(固定住年和月,枚举该月有几天,所以是乘法原理)当x=0并且month<10时,月需要特判一位数的情况,是加法原理日是加法原理AC代码//Problem:日历中的数字//Cont......
  • 刷题建议
    课程安排知识点题目+1题目+2日期线性数据结构-数组15.三数之和560.和为K的子数组 11.盛最多水的容器 排序算法179.最大数75.颜色分类 1054.距离相等的条形码 扩展线性数据结构-多维数组986.区间列表的交集56.合并区间 74.搜索二维矩阵 扩展线性数据结构-特殊矩......
  • 23-05-31 刷题,两道Mid题目
    Mid-1020.飞地的数量-力扣(LeetCode)-BFS-grid分析:飞地,就是被敌人(水)包围的陆地。本题中是指不与任何border相联的1组成,只考虑四个方向。思路:换种角度,从border的1出发,总共有4个border,利用BFS遍历,初始队列中包含四个border中1的位置,然后将他们标记成其他值(例如2),这样省掉......