V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  wnjxyk  ›  全部回复第 1 页 / 共 1 页
回复总数  4
@wnjxyk 是我的错,群晖的 DDNS 域名似乎都没有备案
使用群晖自带 DDNS 与 *.synology.me 可行吗?这个域名应该是群晖自己备案过的。
我在使用 Bow 的三折蓝牙键盘打字,全尺寸而且可以把 iPad 放在桌上、键盘放腿上离老远打字感觉,感觉还是很舒服的。
2018-12-08 09:33:45 +08:00
回复了 hyousan 创建的主题 问与答 问个算法问题。。。。。。。
理解一下 Problem Statements,有 n 个点(x, y)、m 个矩形(x, y, w, h),试问当前图形是否满足 每个点都至少被一个矩形包含 且 每个矩形都包含至少一个点。

假设 n 与 m 都是 1e5 的数量级别的,这个问题可以使用 O(nlogn)的复杂度解决。我们分`每个点至少被一个矩形包含`与`每个矩形都至少包含一个点`这两个部分解决。

首先的首先,如果坐标的数值范围大的可怕,坐标离散化是必须的。

每个点至少被一个矩形包含:
这个问题可以使用扫描线+树状数组(区间修改单点查询)解决。
我们把矩形拆成(x, y)-(x+w, y)的入边与(x, y+h)-(x+w,y+h)的出边两种。然后把入边、出边与点混在一起按照 y 的值排序(如果点和边的 y 值相同,那么要保证入边<点<出边这种顺序)。
按照 y 值从小到大的顺序便利这个对象组,当遇到一个入边(x, y)-(x+w, y)的时候,我们对树状数组的[x, x+w]范围区间+1,遇到一个出边(x, y)-(x+w, y)的时候,我们对树状数组的[x, x+w]范围区间-1。
当遇到点(x, y)的时候,我们查询树状数组位置 x 的值,假设为 p,就表示这个点就被 p 个矩形包含。如果 p=0,那就 GG 啦,直接返回 NO。

每个矩形都至少包含一个点:
这个问题,我们直接使用可持久化线段树来解决。
我们把矩形(x, y, w, h)的排序关键值设为 y+h,点(x, y)的排序关键值设为 y,然后把点和矩形混在一起排序(如果关键值相同,我们保证点<矩形)
接下来,我们建立一颗可持久化线段树 tree_0,然后关键值从小到大的顺序便利这个对象组。每遍历一个新的离散化之后的 y 值 y0,我们就从 tree_{y}创建一个新的可持久化线段树 tree_{y0+1}。如果当前是一个点(x, y),我们对当前可持久化数据结构的 x 位置+1,如果当前是一个矩形(x, y, w, h),我们在 tree_{y+h}-tree_{y-1}这个线段树上查询区间[x, x+w]的和 p,p 表示这个矩形包含点的数量,如果 p=0 就 GG 啦,返回 NO。

如果这两个条件都满足就 YES 了。
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1047 人在线   最高记录 6679   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 13ms · UTC 18:35 · PVG 02:35 · LAX 10:35 · JFK 13:35
Developed with CodeLauncher
♥ Do have faith in what you're doing.