Post zxxx

?

[SNOI2017]炸弹

题目描述

在一条直线上有 $ N $ 个炸弹,每个炸弹的坐标是 $ X_i $,爆炸半径是 $ 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$

算了以后我做计数好了。