开发笔记:bzoj5017[Snoi2017]炸弹(线段树优化建图+)tarjan缩点+拓扑排序
作者:混事珊远_692 | 来源:互联网 | 2023-06-07 07:07
题目传送门https://lydsy.com/JudgeOnline/problem.php?id=5017题解这个题目方法挺多的。线段树优化建图线段树优化建图的做法应该挺显然的,一个炸弹能够引爆的炸
题目传送门 https://lydsy.com/JudgeOnline/problem.php?id=5017
题解 这个题目方法挺多的。
线段树优化建图 线段树优化建图的做法应该挺显然的,一个炸弹能够引爆的炸弹的显然应该是一个区间里面的,直接对这个区间进行线段树优化建图。
这样可以得到一个带环图,缩点以后这个炸弹能够炸到的炸弹就是从这个点能够走到的点。
但是这个不太好做,不过可以发现最终的炸弹也是一个区间,所以可以通过缩点后的 DAG 来求出左右端点。
时间复杂度 (O(nlog n)) ,空间复杂度 (O(nlog n)) 。
一般的建图 可以发现在一个点可以炸到的炸弹中,真正会对最终答案的左右端点有贡献的只有这些炸弹里面左端点最小的和右端点最大的炸弹。
直接对这两个炸弹建边就可以了,然后和上面一样,先 tarjan 缩点,然后在 DAG 上跑出来左右端点。
但是因为想要确定左右端点对应的位置,所以这个 (log) 还是没有办法去掉。
时间复杂度 (O(nlog n)) ,空间复杂度 (O(n)) 。
神仙的线性递推做法 https://www.cnblogs.com/saigyouji-yuyuko/p/11771364.html
丢个链接跑路。
我不会,好像很神仙的样子。
听说是时空都是线性的哦。
#include #define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to) #define dbg(...) fprintf(stderr, __VA_ARGS__) #define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) #define fi first #define se second #define pb push_back template inline char smax(A &a, const B &b) {return a template inline char smin(A &a, const B &b) {return b typedef long long ll; typedef unsigned long long ull; //typedef std::pair pii; template inline void read(I &x) { int f = 0, c; while (!isdigit(c = getchar())) c == &#39;-&#39; ? f = 1 : 0; x = c & 15; while (isdigit(c = getchar())) x = (x <<1) + (x <<3) + (c & 15); f ? x = -x : 0; } const int N = 500000 + 7; const int M = 500000 * 2 + 7; const int P = 1e9 + 7; const ll INF = 0x3f3f3f3f3f3f3f3f; const int LOG = 19; typedef std::pair pii; int n, m, sccno, dfc, tp; int dfn[N], low[N], scc[N], s[N]; std::vector v[N]; ll a[N], r[N], dpl[N], dpr[N]; pii minl[N][LOG], maxr[N][LOG]; struct Edge { int to, ne; } g[M]; int head[N], tot; inline void addedge(int x, int y) { g[++tot].to = y, g[tot].ne = head[x], head[x] = tot; } inline void adde(int x, int y) { addedge(x, y), addedge(y, x); } inline void dfs(int x) { dfn[x] = low[x] = ++dfc, s[++tp] = x; for fec(i, x, y) if (!dfn[y]) dfs(y), smin(low[x], low[y]); else if (!scc[y]) smin(low[x], dfn[y]); if (low[x] == dfn[x]) { ++sccno; dpl[sccno] = INF, dpr[sccno] = -INF; while (1) { int y = s[tp--]; scc[y] = sccno, smax(dpr[scc[y]], a[y] + r[y]), smin(dpl[scc[y]], a[y] - r[y]); v[scc[y]].pb(y); if (x == y) break; } } } inline void tarjan() { for (int i = 1; i <= n; ++i) if (!dfn[i]) dfs(i); } inline void rmq_init() { for (int i = 1; i <= n; ++i) minl[i][0] = pii(a[i] - r[i], i), maxr[i][0] = pii(a[i] + r[i], i); for (int j = 1; (1 < for (int i = 1; i + (1 < minl[i][j] = std::min(minl[i][j - 1], minl[i + (1 <<(j - 1))][j - 1]), maxr[i][j] = std::max(maxr[i][j - 1], maxr[i + (1 <<(j - 1))][j - 1]); } inline pii qmin(int l, int r) { int k = std::__lg(r - l + 1); return std::min(minl[l][k], minl[r - (1 <} inline pii qmax(int l, int r) { int k = std::__lg(r - l + 1); return std::max(maxr[l][k], maxr[r - (1 <} inline void work() { rmq_init(); for (int i = 1; i <= n; ++i) { int pl = std::lower_bound(a + 1, a + n + 1, a[i] - r[i]) - a, pr = std::upper_bound(a + 1, a + n + 1, a[i] + r[i]) - a - 1; addedge(i, qmin(pl, pr).se); addedge(i, qmax(pl, pr).se); } tarjan(); for (int i = 1; i <= sccno; ++i) { int len = v[i].size(); for (int j = 0; j int x = v[i][j]; for fec(iii, x, y) smin(dpl[i], dpl[scc[y]]), smax(dpr[i], dpr[scc[y]]), assert(scc[y] <= i); } } ll ans = 0; for (int i = 1; i <= n; ++i) { int pl = std::lower_bound(a + 1, a + n + 1, dpl[scc[i]]) - a, pr = std::upper_bound(a + 1, a + n + 1, dpr[scc[i]]) - a - 1; ans += (ll)i * (pr - pl + 1); } printf("%lld ", ans % P); } inline void init() { read(n); for (int i = 1; i <= n; ++i) read(a[i]), read(r[i]); } int main() { #ifdef hzhkk freopen("hkk.in", "r", stdin); #endif init(); work(); fclose(stdin), fclose(stdout); return 0; }
推荐阅读
P2765魔术球问题这道题的思路实在是太罕见了,所以发一篇blog从某一新放入的球开始看起1.放入原来的柱子上2.放入新的柱子并将每个点进行拆点 ...
[详细]
蜡笔小新 2023-10-15 12:54:08
本文介绍了一道经典的状态压缩题目——关灯问题2,并提供了解决该问题的算法思路。通过使用二进制表示灯的状态,并枚举所有可能的状态,可以求解出最少按按钮的次数,从而将所有灯关掉。本文还对状压和位运算进行了解释,并指出了该方法的适用性和局限性。 ...
[详细]
蜡笔小新 2023-12-10 11:23:10
本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度,要求从最低点跳跃到最高点,每次跳跃的距离不超过D,并且不能改变给定的顺序。通过建立差分约束系统,将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法,并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ...
[详细]
蜡笔小新 2023-12-14 11:49:51
本文主要介绍了gym102222KVertex Covers(高维前缀和,meet in the middle)相关的知识,包括题意、思路和解题代码。题目给定一张n点m边的图,点带点权,定义点覆盖的权值为点权之积,要求所有点覆盖的权值之和膜qn小于等于36。文章详细介绍了解题思路,通过将图分成两个点数接近的点集L和R,并分别枚举子集S和T,判断S和T能否覆盖所有内部的边。文章还提到了使用位运算加速判断覆盖和推导T'的方法。最后给出了解题的代码。 ...
[详细]
蜡笔小新 2023-12-09 10:03:53
796.[APIO2012]派遣在一个忍者的帮派里,一些忍者们被选中派遣给顾客,然后依据自己的工作获取报偿。在这个帮派里,有一名忍者被称之为Master。 ...
[详细]
蜡笔小新 2023-10-15 20:32:49
题目描述Takuru是一名情报强者,所以他想利用他强大的情报搜集能力来当中间商赚差价。Takuru的计划是让Hinae帮他去市场上买一个商品,然后再以另一个价格卖掉它。Takur ...
[详细]
蜡笔小新 2023-10-15 11:48:13
DescriptionclickmeSolution套路的状压期望DP题。。。考虑倒退期望:设fi,jrolepresentationstyleposi ...
[详细]
蜡笔小新 2023-10-15 10:43:49
本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法,并给出了问题的解析和解决方法。详细介绍了问题的背景和规则,并给出了相应的算法解析和实现步骤。通过本文的解析,读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ...
[详细]
蜡笔小新 2023-12-14 12:03:27
本文介绍了P1651题目的描述和要求,以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术,将问题转化为求解差值的问题,并定义了相应的状态。最终得出了计算最大高度的解法。 ...
[详细]
蜡笔小新 2023-12-13 19:52:19
本文讲述了少年李逍遥为了救治婶婶的病情,前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵,有些方格内有怪物,有些方格是安全的。李逍遥需要避开有怪物的方格,并经过最少的方格,找到仙药。在寻找的过程中,他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ...
[详细]
蜡笔小新 2023-12-12 13:59:33
本文介绍了Codeforces Round #321 (Div. 2)比赛中的问题Kefa and Dishes,通过状压和spfa算法解决了这个问题。给定一个有向图,求在不超过m步的情况下,能获得的最大权值和。点不能重复走。文章详细介绍了问题的题意、解题思路和代码实现。 ...
[详细]
蜡笔小新 2023-12-11 10:37:34
本文讲述了CodeForces1016C题目的解法。文章首先介绍了一种错误的理解,然后给出了正确的解法。其中,当位于一个角上时,有两种选择,一种是先一直走一行再返回来走,另一种是走到这一列的另一行上然后再往右走一列。作者给出了两种解法,一种是直接计算,一种是动态规划。最后,取两种解法的最优解作为答案。文章附上了源代码。 ...
[详细]
蜡笔小新 2023-12-10 20:45:35
1.概念比较并交换(compareandswap,CAS),是原⼦操作的⼀种,可⽤于在多线程编程中实现不被打断的数据交换操作 ...
[详细]
蜡笔小新 2023-12-09 10:10:40
先看官方文档TheJavaTutorialshavebeenwrittenforJDK8.Examplesandpracticesdescribedinthispagedontta ...
[详细]
蜡笔小新 2023-12-12 13:36:56
本文介绍了标准模板库(STL)定义的五种迭代器的种类和功能。通过图表展示了这几种迭代器之间的关系,并详细描述了各个迭代器的功能和使用方法。其中,输入迭代器用于从容器中读取元素,输出迭代器用于向容器中写入元素,正向迭代器是输入迭代器和输出迭代器的组合。本文的目的是帮助读者更好地理解STL迭代器的使用方法和特点。 ...
[详细]
蜡笔小新 2023-12-10 15:17:25