树状数组(Binary Indexed Tree, BIT)是一种可以实现单点更新,区间查询的数据结构,每次操作复杂度为 $O(logn)$。

它的实现主要包括两个函数:

  • $sum(i)$ 表示 $i$ 所在位置的前缀和(即 $a_1+a_2+…+a_i$,下标从 $1$ 开始)
  • $add(i, x)$ 表示给 $a_i$ 加上 $x$
阅读全文 »

题目大意

给出 $n$ 个点,$m$ 条边的无向带权图(权值都为1),镖车将从起点 $s$ 出发到达终点 $f$,保证走最短路径。强盗在点 $r$ 处,他想通过预先埋伏的方式拦截镖车(甚至可以在 $s$ 或者 $f$ 埋伏)。并且强盗希望在离 $r$ 最近的点埋伏,问最坏情况下需要走的最远距离。
$( 3 \leq n \leq 10^5, 2 \leq m \leq 10^5)$

阅读全文 »

题目大意

国王阅兵式会持续 $n$ 天,每天都有一场飞机表演,第 $i$ 天的飞行表演需要个 $p_i$ 飞行员。飞行员只愿意无偿工作一天。于是这个国家出台了 $m$ 个休假政策,当某个飞行员工作后,如果支付他 $S_j$ 的酬劳,他会在上次工作 $T_j$ 天后重新回来工作。

开始有 $k$ 名飞行员,当然还可以招募新的飞行员,但是,招募需要 $P$ 天的时间,并且招募来的每个飞行员需要支付 $Q$ 作为酬劳。(也就意味着到第 $P$ 天你才可能用到新招募来的飞行员)

现要求通过合理安排,保证每天的飞行员数量足够(若不能,输出“No solution”),并且让总费用最低。输出总费用。
$(m \leq 5, 其他所有数据均在区间[0, 200]内)$

阅读全文 »

题目大意

在2D平面上有 $N$ 个藏宝点,每个点的坐标为 $(x_i, y_i)$ ,价值为 $x_i$ $AND$ $y_i$ 。
现要求选择权值和最大的一些点,且点集 $T$ 满足:
$$ \forall(x_i, y_i)(x_j, y_j)(i \not= j) \in T, gcd(x_i \oplus y_i \oplus x_j \oplus y_j, P) > 1 $$
$P$ 是偶数,且 $\oplus$ 代表异或。
求点集 $T$。
$ (1 \le N \le 500, 2 \le P \le 10^{9}, 0 \le x_i, y_i \le 10^{9})$
$ (\forall i, j, x_i \oplus y_i \oplus x_j \oplus y_j > 0)$

阅读全文 »

题目大意

Cain被困在一座有 $N$ 条路径的洞穴,他本身有战斗力为 $f$ 。
每一天,Cain会被随机传送到某条路径:
若他此时的战斗力大于该路径的困难度 $c_i$ ,那么他可以花费 $t_i$ 时间逃出这个洞穴;
否则,无法逃出洞穴,但其战斗力可以增加 $c_i$ ,并等待第二天的传送。
求Cain逃出洞穴的期望时间。

$( N \leq 100, f \leq 10000, c_i \leq 10000, 1 \leq i \leq N )$
$( t_i = \lfloor \frac{1 + \sqrt{5}}{2} \rfloor \times c_i^{2} )$

阅读全文 »