表面\(O(N^2)\)，随机数据能让\(200000\times 200000\)过的玄学题…… 题目背景 loidc来到了NOI的赛场上，他在那里看到了好多神犇。 题目描述 神犇们现在正排成一排在刷题。每个神犇都有一个能力值\(p[i]...

  题目描述 煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一...

洛谷的这个模板题可以说是相当坑了 【P3388】【模板】割点（割顶）细节处理不到位总是拿不好分。 题目描述 给出一个n个点，m条边的无向图，求图的割点。 输入输出格式 输入格式： 第一行输入n,m 下面...

非常的卡常数？ 拿了好长时间的95分。。 题目描述     公元2044年，人类进入了宇宙纪元。L国有n个星球，还有n−1条双向航道，每条航道建立在两个星球之间，这n−1条航道连通了L国的所有星球。小P掌管一家...

这个题涉及到有向图中的信息传递，需要用到tarjan缩点。 （洛谷数据加强版） 题目背景 浙江省的几所OI强校的神犇发明了一种人工智能，可以AC任何题目，所以他们决定建立一个网络来共享这个软件。但是由于...

   例题是洛谷P3387缩点      顾名思义，缩点就是将等价的几个点转化为一个点，点权可累加。那么我们就要用tarjan来求一下哪些点可以缩在一起。   1.dfn和low的含义    tarjan算法有两个...

例题是洛谷P3379      最近公共祖先可以用倍增做，也可以用tarjan做，不过tarjan是离线的，理论上效率要高一些。      今天学习的是用tarjan算法求LCA。 需要用到的数据结构：并查集。首...

  题目描述 给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一...

   典型的动态规划类题目，不过这次在环上，而且是两端，所以DP方法要有所改进。 题目描述 给出一段环状序列，即认为$ A_1$和$ A_n$是相邻的，选出其中连续不重叠且非空的两段使得这两段和最大。   ...

   题面可见洛谷P1908逆序对      逆序对，最朴素的做法就是$ O(N^2)$的了，枚举每个数对，逆序则sum++。      不过主流做法是归并排序，也可以用树状数组（线段树）来做。   ...