[研学] 偏序问题的研究

[研学] 偏序问题的研究

时间: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)\) 的条件是:连接站点 \(a\) 与 \(a+1\),\(a+1\) 与 \(a+2, \cdots ,b-1\) 与 \(b\) 的路段都被照亮。

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

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

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

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

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

  • 输入格式

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

第二行包含一个字符串 \(s\) 表示路灯的初始状态 \((\left|s\right| = n)\), \(s_i\) 为 \(1\) 表示第 \(i\) 个路灯初始时亮起; \(s_i\) 为 \(0\) 表示第 \(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万好了。

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

  • 输入格式

第一行 \(n\),\(1 \leq n \leq 1000000\) 。

接下来 \(n\) 行,每行 \(l_i,r_i\),\(1 \leq l_i \leq r_i \leq 1000000\) 。

  • 输出格式

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

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

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 3711

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

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

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|\)。

  • 编程任务

对于给定的点集 \(A\) 和 \(B\),求出对于所有 \(1\le i\le m\) 的 \(c_i\) 的值。

  • 输入格式

第一行有三个正整数\(m\)、\(n\) 和 \(k\),分别表示集合 \(A\) 和 \(B\) 的基数及维数。接下来的 \(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\) 行。

  • 样例输入

  • 样例输出

  • 数据规模与约定

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

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^5\),\(0 \leq h_i,\left| w_i\right| \leq 10^6\) 。

数据来源 LOJ 2483

 

 

已搬至 YZOJ P4254 。…