Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js

[研学] 偏序问题的研究

[研学] 偏序问题的研究

时间:2019.04 ~ 2019.09

参加成员:Modem_  Lagoon  _Qijia  mnihyc

备注:第二年就开始混水了啊(笑),只存了自己写的那部分:

  • 高维偏序

至此,k \le 3 的问题已经被我们解决了。

k = 4 呢?CDQ套CDQ?CDQ套树套树?树套树套树?

如果 k 更大,达到 k = 10 呢?十维树状数组?树套树套树套树套………?

很明显 O(n{\log ^{k – 1}}n) 的复杂度是承受不起的,需要从别的方面下手。

注意到在 k 变大的同时,n 也在变小,所以可以考虑复杂度以 n 为主的算法。

首先考虑的,当然是暴力啦)。

可以暴力枚举所有维度,并且按照这个维度(上的数)排序,这些就可以快速找出一个点控制了其它哪一些点。如果把这个信息用一个长度为 n 的二进制数表示,那么对于每个询问,只需要把它在所有维度下的二进制数取“与”运算(即能控制的点取交集),这样答案就是二进制位为 1 的数量了。

维护二进制串?当然是用 std::bitset<>  啦)。

这样复杂度就是 \displaystyle O\left( {\frac{{{n^2}k}}{{32}}} \right) ,足以通过本题了。

 

代码略。

 

这里其实还有一种在时空复杂度上的优化——分块)。

按照分块的那一套理论,把区间分成 \sqrt n 个,每块用一个 std::bitset<>  维护前缀,同时维护一个块最大值。查询的时候在块上二分,找到询问点所在的块,然后暴力加块内的点即可。时间复杂度即可缩小至 \displaystyle O\left( {\frac{{nk\sqrt n }}{{32}}} \right)

 

 …

YZOJ P4444 [APIO2019]路灯

YZOJ P4444 [APIO2019]路灯

时间限制:5000MS      内存限制:524288KB

难度:7.0

  • 题目描述

一辆自动驾驶的士正在 Innopolis 的街道上行驶。该街道上有 n+1 个停车站点,它们将街道划分成了 n 条路段。每一路段都拥有一个路灯。当第 i 个路灯亮起,它将照亮连接第 i 与第 i+1个站点的路段。否则这条路段将是黑暗的。

出于安全性的考虑,自动驾驶的士只能行驶在被照亮的路段上。换言之,的士能从站点 a 出发到达站点 b (a<b) 的条件是:连接站点 aa+1a+1a+2, \cdots ,b-1b 的路段都被照亮。

在经过一些意外故障或修理之后,街道上的路灯可能是亮起的,也可能是熄灭的。

现在给定 0 时刻时,街道上路灯的初始状态。之后 1,2,\cdots,q 时刻,每时刻会发生下列两种事件之一:

toggle i:切换第 i 个路灯的状态。具体地说,若路灯原来亮起,则现在将熄灭;若路灯原来熄灭,则现在将亮起。

query a b:自动驾驶的士部门的负责人想知道,从 0 时刻起到当前时刻,有多少个时刻满足:自动驾驶的士能够从站点 a 出发到达站点 b

请你帮助自动驾驶的士部门的负责人回答他们的问题。

  • 输入格式

第一行包含两个整数 nq (1 \leq n,q \leq 300000) —- 表示路灯的数量与时刻数。

第二行包含一个字符串 s 表示路灯的初始状态 (\left|s\right| = n)s_i1 表示第 i 个路灯初始时亮起; s_i0 表示第 i 个路灯初始时熄灭。

接下来 q 行每行描述一个时刻的事件。第 i 行描述时刻 i 所发生的事件。

toggle i (1 \leq i \leq n):该时刻切换了第 i 个路灯的状态。

query a b (1 \leq a < b \leq n+1):计算从 0 时刻起到该时刻,共有多少个时刻满足的士能从站点 a 出发到达站点 b

至少有一个时刻的事件是 query

  • 输出格式

对于每个 query 的事件,输出一行单个整数,表示该问题的答案。…

YZOJ P2905 [PA2014]Druzyny

YZOJ P2905 [PA2014]Druzyny

时间限制:1000MS      内存限制:131072KB

难度:8.0

  • 题目描述

在之前的某次校内训练中,zzx 出了一道神奇的题目:给出 n 个人,要求将所有人分成若干个组,第 i 个人所在的组的人数必须在 [l_i, r_i] 之间,判断是否存在可行解。

OI组的神犇们决定把这题改造一下:

dick32165401:改成只有编号连续的的一段才可以分一组。

runzhe2000:判定可行解可能会被爆搜水过,最大化分的组数就不那么容易水过了。

E.Space:不仅要最大化组数,还要求出最大化组数的方案数。

ct:数据范围就出100万好了。

于是这题就被这么造好了。

  • 输入格式

第一行 n1 \leq n \leq 1000000

接下来 n 行,每行 l_i,r_i1 \leq l_i \leq r_i \leq 1000000

  • 输出格式

若不存在合法的方案,仅输出一行 -1

否则输出一行两个整数,分别表示组数的最大值和组数取最大值的方案数模 10^9+7

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 3711

膜拜上方所有dalao %%%%%%%%%%%%%%%%%%

像我这种菜鸡看到这种神仙题只会爆零QAQ…

YZOJ P3527 [FJOI2018D1T3]城市路径问题

YZOJ P3527 [FJOI2018D1T3]城市路径问题

时间限制:1000MS      内存限制:131072KB

难度:6.5

  • 题目描述

给出一张 n 个点的有向图 G(V, E) 。对于任意两个点 u, vu 可以等于 v ),uv 的连边数为:\sum\limits_{i=1}^k {out[u, i] \times in[v, i]}

给定 k 和数组 out, in ,现在有 m 个询问,每次询问给出三个参数 u, v, d,你需要回答从节点 u 出发,经过不超过 d边到达节点 v 的路径有多少种。

答案对 10^9+7 取模。

  • 输入格式

第一行两个整数 n, k

接下来 n 行,第 i 行有 2k 个整数,前 k 个整数描述 out[i][],后 k 个数描述 in[i][]

接下来一行一个整数 m

接下来 m 行,每行三个整数 u, v, d,描述一组询问。

  • 输出格式

对于每个询问,输出一个方案数。由于答案可能太大,输出其除以 10^9+7 后的余数。…

YZOJ P3706 [APIO2018]新家

YZOJ P3706 [APIO2018]新家

时间限制:5000MS      内存限制:1048576KB

难度:7.0

  • 题目描述

五福街是一条笔直的道路,这条道路可以看成一个数轴,街上每个建筑物的坐标都可以用一个整数来表示。

小明是一位时光旅行者,他知道在这条街上,在过去现在和未来共有 n 个商店出现。第 i 个商店可 以使用四个整数 x_i , t_i , a_i , b_i 描述,它们分别表示:商店的坐标、商店的类型、商店开业的年份、商店关闭的年份。

小明希望通过时光旅行,选择一个合适的时间,住在五福街上的某个地方。他给出了一份他可能选择的列表,上面包括了 q 个询问,每个询问用二元组 (坐标,时间)表示。第 i 对二元组用两个整数 l_i , y_i 描述,分别表示选择的地点 l_i 和年份 y_i

现在,他想计算出在这些时间和地点居住的生活质量。他定义居住的不方便指数为:在居住的年份,离 居住点最远的商店类型到居住点的距离。类型 t 的商店到居住点的距离定义为:在指定的年份,类型 t 的所有营业的商店中,到居住点距离最近的一家到居住点的距离。我们说编号为 i 的商店在第 y 年在营业当且仅当 a_i \leq y \leq b_i 。注意,在某些年份中,可能在五福街上并非所有 k 种类型的商店都有至少一家在营业。在这种情况下,不方便指数定义为 -1

你的任务是帮助小明求出每对(坐标,时间)二元组居住的不方便指数。

  • 输入格式

第一行包含三个整数 n,kq ,分别表示商店的数量、商店类型的数量和(坐标,时间)二元组的数量(1 \le n, q \le 3 \times 10^5 , 1 \le k \le n

接下来 n 行,每行包含四个整数 x_i , t_i , a_ib_i 用于描述一家商店,意义如题面所述 (1 \le x_i , a_i , b_i \le 10^8 , 1 \le t_i \le k, a_i \le b_i)。

接下来 q 行,每行包含两个整数 l_iy_i ,表示一组(坐标,时间)查询 (1 \le l_i , y_i \leq 10^8 )。

  • 输出格式

输出一行,包含 q 个整数,依次表示对于 q 组(坐标,时间)询问求出的结果。…

YZOJ P3924 [IOI2011]Race

YZOJ P3924 [IOI2011]Race

时间限制:2000MS      内存限制:131072KB

难度:7.0

  • 题目描述

给一棵树,每条边有权。

求一条简单路径,权值和等于 K ,且经过边的数量最小。

N \leq 200000, K \leq 1000000

  • 输入格式

第一行 两个整数 nk

2~n 行 每行三个整数,表示一条无向边的两端和权值(注意点的编号从 0 开始)。

  • 输出格式

一个整数,表示最小边数量。

如果不存在这样的路径,输出 -1

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 2599…

YZOJ P3361 [校内训练20171117]数点问题

YZOJ P3361 [校内训练20171117]数点问题

时间限制:2000MS      内存限制:262144KB

出题人:zzx      难度:6.0

  • 题目描述

k 维空间内有两个点集 A=\{X_1,X_2,\ldots,X_m\}B=\{Y_1,Y_2,\ldots,Y_n\},每个点的坐标是一个 k 元组 (x_1,x_2,\ldots,x_k)。我们称点 X(x_1,x_2,\ldots,x_k) 控制点 Y(y_1,y_2,\ldots,y_k) 当且仅当 \forall 1\le i\le k,x_i>y_i,记为 X>Y。数点问题是要求计算点 X_i 能控制 B 中的点数 c_i,即 c_i=\left| \{Y \in B\ |\ X_i > Y\} \right|

  • 编程任务

对于给定的点集 AB,求出对于所有 1\le i\le mc_i 的值。

  • 输入格式

第一行有三个正整数mnk,分别表示集合 AB 的基数及维数。接下来的 m+n 行依次给出点 X_1 , X_2 ,\ldots, X_m ,Y_1 ,Y_2 ,\ldots,Y_n,每个点的坐标用一行 k 个整数 x_1 , x_2 ,\ldots, x_k 描述,所有坐标在 int 范围内。

  • 输出格式

将计算出的 c_1 ,c_2 ,\ldots,c_m 依次输出到文件中,每个 c_i 输出 1 行。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于数据点 1n,m\le 200,000k=1

YZOJ P3392 越野赛车问题

YZOJ P3392 越野赛车问题

时间限制:1000MS      内存限制:262144KB

难度: 6.0

  • 问题描述

某山上一共有 n 个广场,编号依次为 1 到 \(n\),这些广场之间通过 n-1 条双向车道直接或间接地连接在一起。对于每条车道 i,可以用四个正整数 u_i, v_i, l_i, r_i 描述,表示车道连接广场 u_iv_i,其速度承受区间为 [l_i, r_i],即汽车必须以不小于 l_i 且不大于 r_i 的速度经过车道 i

现计划进行 m 次训练,每次选择某山上的一条简单路径,然后在这条路径上行驶,且每次训练时的车速都是固定的。现在有在 m 次训练中分别计划使用的车速,要求一条合法的路径(车速在所有车道的速度承受区间的交集内),使得路径上经过的车道数最大

  • 数据输入

输入文件的第一行包含两个正整数 n, m,表示广场数和训练次数。接下来 n-1 行,每行四个正整数 u_i, v_i, l_i, r_i ( \leq n),描述所有车道。最后 m 行,每行一个正整数 v (\leq n) ,表示每次训练是的车速。

  • 结果输出

输出 m 行,输出每次训练时的行驶路径经过的最大车道数。

  • 样例输入

  • 样例输出


YZOJ P3840 [2018省队集训]序列

YZOJ P3840 [2018省队集训]序列

时间限制:2000MS      内存限制:524288KB

难度: 8.0

  • 题目描述

给定一个长度为 n 的序列 x

你需要从序列中选出一些位置。对于i位置,如果它被选中,你会获得 x_i 的收益;否则找到最小的 j 使得第 j 个位置到第 i 个位置都没有被选中,你需要付出 i-j+1 的代价。

此外,你选出的位置必须满足 x_i单调不下降的。

最大化收益减去代价的结果。

  • 输入格式

第一行一个正整数 n,第二行 n 个整数 x_1 ~ x_n

  • 输出格式

输出一行一个整数表示答案。

  • 样例 1 输入

  • 样例 1 输出

  • 样例 1 说明

选择第 1, 3, 5, 7 个位置,获得收益 1+2+3+4=10 ,第 2, 4, 6 个位置的代价分别为 1, 1, 1 ,收益减去代价为 10-3=7

  • 样例 2 输入

  • 样例 2 输出

  • 数据规模与约定

对于 5\% 的数据, 1 \leq n \leq 5 。…

[CEOI2017]Building Bridges

[CEOI2017]Building Bridges

时间限制:1000MS      内存限制:131072KB

难度: 7.2

  • 题目描述

n 根柱子依次排列,每根柱子都有一个高度。第 i 根柱子的高度为 h_i

现在想要建造若干座桥,如果一座桥架在第 i 根柱子和第 j 根柱子之间,那么需要 (h_i-h_j)^2 的代价。
在造桥前,所有用不到的柱子都会被拆除,因为他们会干扰造桥进程。第 i 根柱子被拆除的代价为 w_i​,注意 w_i 不一定非负,因为可能政府希望拆除某些柱子。

现在政府想要知道,通过桥梁把第 1 根柱子和第 n 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

  • 输入格式

第一行一个正整数 n

第二行 n 个空格隔开的整数,依次表示 h_1, h_2, \cdots, h_n

第三行 n 个空格隔开的整数,依次表示 w_1, w_2, \cdots, w_n

  • 输出格式

输出一行一个整数表示最小代价,注意最小代价不一定是正数。

  • 样例输入

  • 样例输出

  • 数据范围与提示

对于 30\% 的数据,有 1 \leq n \leq 1000

对于另外 40\% 的数据,有 \left| w_i \right| \leq 20 ,保证存在一种最优方案,除了头尾两根柱子外,最多只保留两根柱子;

对于 100\% 的数据,有 2 \leq n \leq 10^50 \leq h_i,\left| w_i\right| \leq 10^6

数据来源 LOJ 2483

 

 

已搬至 YZOJ P4254 。…