题目链接 \(Description\) 给定\(n\times m\)的带边权网格图.\(Q\)次询问从点\((x_i,y_i)\)到点\((x_j,y_j)\)的最短路. \(n\times m\leq 2\times 10^4,Q\leq 10^5\). \(Solution\) 对分治线上的每个点进行一次Dijkstra.若该区域点数(面积)为S,则分治线如果选择较短的一边,其上点的个数\(\leq\sqrt S\).每次选较短的分治复杂度\(O(S\sqrt S\log S)\),若不

题目描述 小Y来到了一个新的城市旅行.她发现了这个城市的布局是网格状的,也就是有n条从东到西的道路和m条从南到北的道路,这些道路两两相交形成n*m个路口 (i,j)(1<=i<=n,1<=j<=m). 她发现不同的道路路况不同,所以通过不同的路口需要不同的时间.通过调查发现,从路口(i,j)到路口(i,j+1)需要时间 r(i,j),从路口(i,j)到路口(i+1,j)需要时间c(i,j).注意这里的道路是双向的.小Y有q个询问,她想知道从路口(x1,y1)到路口(x2,y2)最少

链接 P3350 [ZJOI2016]旅行者 题目大意:给出网格图,求两点之间最短路,多组询问. \(n*m\leq10^5\ \ q\leq 10^5\) 考虑\(CDQ\)分治. 首先把询问离线,对于一个矩阵中的最短路,如果\(u,v\)不在统一侧,那么一定会经过平分线. 所以对矩阵分治理,只考虑最短路经过矩阵中线的情况,枚举中线上的任意一点做最短路,用\(Dis_u+Dis_v\)更新这次询问的答案即可. 然后把询问划分到左右两边的矩阵中去,分别递归处理即可. 类似于整体二分的思想? 代码

题目链接 bzoj4456: [Zjoi2016]旅行者 题解 网格图,对于图分治,每次从中间切垂直于长的那一边, 对于切边上的点做最短路,合并在图两边的答案. 有点卡常 代码 #include<queue> #include<cctype> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> inline int read() { int x

4456: [Zjoi2016]旅行者 https://www.lydsy.com/JudgeOnline/problem.php?id=4456 分析: 每次对当前矩阵按长边化一条分治线,然后在对分治线上的点跑最短路,然后可以处理处过分治线的询问.对于不过分治线的,递归处理. 先写的dijkstra+堆优化,在开O2的情况下可以过,不开O2过不了,卡常~,还是过不了.然后在UOJ的排行榜里(而且UOJ是有大样例的!),看到了两个优化,加上就可以了. 优化:1.代码41行,用上次的遍历结果初始化

4456: [Zjoi2016]旅行者 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 777  Solved: 439[Submit][Status][Discuss] Description 小Y来到了一个新的城市旅行.她发现了这个城市的布局是网格状的,也就是有n条从东到西的道路和m条从南到北 的道路,这些道路两两相交形成n×m个路口 (i,j)(1≤i≤n,1≤j≤m).她发现不同的道路路况不同,所以通过不 同的路口需要不同的时间.通过调查发

[BZOJ4456][Zjoi2016]旅行者 Description 小Y来到了一个新的城市旅行.她发现了这个城市的布局是网格状的,也就是有n条从东到西的道路和m条从南到北的道路,这些道路两两相交形成n×m个路口 (i,j)(1≤i≤n,1≤j≤m).她发现不同的道路路况不同,所以通过不同的路口需要不同的时间.通过调查发现,从路口(i,j)到路口(i,j+1)需要时间 r(i,j),从路口(i,j)到路口(i+1,j)需要时间c(i,j).注意这里的道路是双向的.小Y有q个询问,她想知道从路口

传送门 题意:给出一个$N \times M$的网格图,边有边权,$Q$组询问,每组询问$(x_1,y_1)$到$(x_2,y_2)$的最短路.$N \times M \leq 2 \times 10^4 , Q \leq 10^5$ BZOJ原题竟然没有数据范围 矩形的多组询问问题考虑分治.考虑计算矩形$(x_1,y_1,x_2,y_2)$的询问,我们将较长边沿着中线劈成两半,在这些询问里面就只可能存在两种情况:①询问的两个端点在中线两边,那么路径就一定会经过中线上一点:②询问的两个端点在中线

题面 https://www.lydsy.com/JudgeOnline/problem.php?id=4456 题解 分治 设当前work的区间为(x1,y1,x2,y2) 我们将长边分成两半 不妨设长边是(x1,x2) 那么令mid=(x1+x2)/2 对于分界线(mid,y1)~(mid,y2)的所有点 我们做最短路 得到分界线上所有点到区间里任意点的最短路 那么对于询问(sx,sy,tx,ty) 我们可以枚举分界线上某一点(mid,y) 并且用dist((mid,y),(sx,sy))+

题链: http://www.lydsy.com/JudgeOnline/problem.php?id=4456 题解: 分治好题.大致做法如下:对于一开始的矩形区域,过较长边的中点把矩形区域分为两个块.然后依次以划分线上的点为起点跑最短路(Dijkstra),尝试以该点为中转点去更新起点和终点都在这个矩形区域内的询问.显然,如果某个询问的起点和终点在划分线的两侧,那么此时一定可以求出该询问的答案,(因为其最短路一定会经过划分线上的点).那么至于起点和终点都在同侧的询问,那么就递归到更小的区域去

题目描述 小Y来到了一个新的城市旅行.她发现了这个城市的布局是网格状的,也就是有n条从东到西的道路和m条从南到北的道路,这些道路两两相交形成n*m个路口 (i,j)(1<=i<=n,1<=j<=m). 她发现不同的道路路况不同,所以通过不同的路口需要不同的时间.通过调查发现,从路口(i,j)到路口(i,j+1)需要时间 r(i,j),从路口(i,j)到路口(i+1,j)需要时间c(i,j).注意这里的道路是双向的.小Y有q个询问,她想知道从路口(x1,y1)到路口(x2,y2)最少

原文链接http://www.cnblogs.com/zhouzhendong/p/8682133.html 题目传送门 - BZOJ4456 题目传送门 - UOJ#184 题意 $n\times m$的网格图$q$次询问两个格子之间的最短路. $n\times m\leq 2\times 10^4,q\leq 10^5$且任何两个相邻格子之间的路径长度$\leq 10^4$. 题解 考虑分治. 对于当前网格图以及起点和终点都在当前网格图内的询问进行处理. 考虑把当前网格图的长边作为分治对象.

本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作. 本文作者:ljh2000 作者博客:http://www.cnblogs.com/ljh2000-jump/转载请注明出处,侵权必究,保留最终解释权! 题目链接:BZOJ4456   UOJ184 正解:分治+dijkstra 解题报告: 这道题的思想挺神的… 考虑我如果每次都处理的是一个矩阵中的询问,我选取“长”,将其分割为两半,显然中轴线的长度$<=$ $\sqrt{n*m}$. 我对于中轴线上的所有

BZOJ 4456 听若干个大佬讲过$n$遍终于写掉了. 我把时限基本上跑满了2333…… 分治 + 最短路. 首先我们去分治这个矩形格子,找到一条长边把它对半切,对切开的边上的每一个点跑一遍最短路然后更新所有答案,接下来把询问分成两类,一类是两个端点都在切开的中间线一侧的,另一类是在两侧的.对于在中轴线一侧的点,我们把它加到一侧去继续分治,而在中轴线两侧的点就不用继续分治了,因为接下来的中轴线一定不会对它造成影响. 分治边界是没有对应询问的情况和只剩下一个点但是仍然有询问的情况,这时候可以直接

感觉比较套路,每次在长边中轴线处切一刀,求出切割线上的点对矩形内所有点的单源最短路径,以此更新每个询问,递归处理更小的矩形.因为若起点终点跨过中轴线是肯定要经过的,而不跨过中轴线的则可以选择是否经过中轴线,若不经过一定就在矩形的某一半了.复杂度O((nm)1.5log(nm)),不太会证. #include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cst

Description 小Y来到了一个新的城市旅行.她发现了这个城市的布局是网格状的,也就是有n条从东到西的道路和m条从南到北 的道路,这些道路两两相交形成n×m个路口 (i,j)(1≤i≤n,1≤j≤m).她发现不同的道路路况不同,所以通过不 同的路口需要不同的时间.通过调查发现,从路口(i,j)到路口(i,j+1)需要时间 r(i,j),从路口(i,j)到路口(i+1 ,j)需要时间c(i,j).注意这里的道路是双向的.小Y有q个询问,她想知道从路口(x1,y1)到路口(x2,y2)最少需要

分析 类似于点分治的思想,只统计经过分割线的最短路,然后把地图一分为二. 代码 #include <bits/stdc++.h> #define rin(i,a,b) for(register int i=(a);i<=(b);++i) #define irin(i,a,b) for(register int i=(a);i>=(b);--i) #define trav(i,a) for(register int i=head[a];i;i=e[i].nxt) typedef lo

4456: [Zjoi2016]旅行者 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 254  Solved: 162[Submit][Status][Discuss] Description 小Y来到了一个新的城市旅行.她发现了这个城市的布局是网格状的,也就是有n条从东到西的道路和m条从南到北的道路,这些道路两两相交形成n×m个路口 (i,j)(1≤i≤n,1≤j≤m).她发现不同的道路路况不同,所以通过不同的路口需要不同的时间.通过调查发现,

Search GO 说明:输入题号直接进入相应题目,如需搜索含数字的题目,请在关键词前加单引号 Problem ID Title Source AC Submit Y 1000 A+B Problem 10983 18765 Y 1036 [ZJOI2008]树的统计Count 5293 13132 Y 1588 [HNOI2002]营业额统计 5056 13607 1001 [BeiJing2006]狼抓兔子 4526 18386 Y 2002 [Hnoi2010]Bounce 弹飞绵羊 43

广告 ZJOI2018Round2游记 All Falls Down 非常感谢学弟学妹们捧场游记虽然这是一篇假游记 ZJOI Round1今天正式落下帷幕.在这过去的三天里遇到了很多朋友,见识了很多有趣的人和事.或许这只是我整个OI生涯中的卷首一场,但是允许我谨此游记献给所有的一切.所有的你们. ZJOIday1游记 8:30:然而报告厅里选手们陆陆续续地并没有到齐-- 第一场主讲人是绍一的任轩笛,讲课pdf的标题一如既往地是「杂题选讲」听主讲人说都是一些套路题 Binary Cards 不上升