?
[SNOI2017]炸弹
题目描述
在一条直线上有 $ N $ 个炸弹，每个炸弹的坐标是 $ Xi $，爆炸半径是 $ R_i $，当一个炸弹爆炸时，如果另一个炸弹所在位置 $ X_j $ 满足：
$ X_i-R_i≤Xj≤X_i+R_i $ ，那么，该炸弹也会被引爆。
现在，请你帮忙计算一下，先把第 $i$ 个炸弹引爆，将引爆多少个炸弹呢？
答案对$1000000007$取模
输入输出格式
输入格式：
第一行，一个数字 $N$ ，表示炸弹个数。
第 $2$ ∼ $N+1$ 行，每行 $2$ 个数字，表示 $X_i$，$R_i$，保证 $X_i$ 严格递增。
输出格式：
一个数字，表示 $\sum \limits{i=1}^n i\times$ 炸弹 $i$ 能引爆的炸弹个数。
输入输出样例
输入样例#1：
4
1 1
5 1
6 5
15 15
输出样例#1：
32
说明
$N≤500000$，
$-10^{18}≤X_i≤10^{18}$，
$0≤R_i≤2 \times 10^{18}$。
题解
这题我一开始以为我轻松切了，就没写代码，结果写的时候就切爆了，不小心最优解了…
后来发现直接叶子节点连了然后Tarjan+DAG DP就OK了。
但是代码还是没有写，颓啊。。。
CF1155F Delivery Oligopoly
给定一张nn个点mm条边无向图 保证它是一个边双连通分量
你需要求出它的一个包含nn个点的子图 满足两个条件：
- 这个子图必须也是边双连通分量
- 这个子图的边数最少
数据保证有解
你需要输出这个子图的所有边
边双连通分量是指一个去掉任何一条边都依然联通的图
$( 3 \le n \le 14, n \le m \le \frac{n(n - 1)}{2} ) $
题解
复习下图论基础知识。
点连通度与边连通度：for undirected graph $G$ , if $\exists \{V_i\}$ , delete $\{V_i\}$ and the edges which have at least one point in $\{V_i\}$ , we called the $card({V_i})$ is the Point connectivity , the number of the edges is the Edge connectivity
英语是好东西。
边双连通分量意味着至少要割掉两条边，也就意味着每个点都有至少两条路径到达其他点。
这道题复杂度最高$O(n3^n)$
挖掘图$G$与子图$G’$的是否双连通关系，发现了一个有趣的性质:
the $G$ is 2EC is quivilant to the $V \in \{V_i | V_i \in G \and V_i \notin G’\}$ , that V have at least edges connecting the two different $V’\in G’$ and $G’$ is 2EC.
proof: Assume the to different vertexes are P1 , P2 , we prove P1 -> V have two different ways.
$\because$ G’ is 2EC $\and P1 -> V \and P2 -> V $
$\therefore$ G’ + V is 2EC
So we could inductively prove that.
这样我们就枚举状态的一个点，然后看去掉这个点的点集是不是2EC，以及这个点有没有两条边相连。
这样时间复杂度是$O(n^22^n)$，感觉不大可能吧….时间太少抄题解？
发现比我想象的复杂，果然我只会做水题。
let $f_S$ means the least number of edges to form 2EC. $Lk1_S$
算了以后我做计数好了。