BZOJ-3509. [CodeChef] COUNTARI

给定一个长度为 n ~(1 \leq n \leq 10^5) 的数组 a_i~(0 \leq a_i \leq 3\cdot 10^4),问有多少对 (i, j, k) 满足 i < j < ka_i - a_j = a_j - a_k

也就是统计有多少对长度为 3 的等差子序列(题目连接 BZOJ-3509, CodeChef COUNTARI

例如 3 5 3 6 3 4 10 4 5 2,就有 (1, 3, 5), (1, 6, 9), (1, 8, 9), (3, 6, 9), (3, 8, 9), (5, 6, 9), (5, 8, 9), (4, 6, 10), (4, 8, 10) 一共 9 对

(more…)

Read More

BZOJ-3771. Triple

这题挺有意思的,来源是 SPOJ-TSUM,题意大概是,给出 n 个物品,第 i 个物品的价值为 x_i(0 < x_i \leq 4\cdot10^4),问在这 n 个物品中选出 1 个或 2 个或 3 个价值和是多少,对于每个价值求出方案个数,在这题中 (a, b)(b, a) 算作一种方案

例如有三个物品

x_1 x_2 x_3
1 2 3

选一个就可以得到 1, 2, 3 三种价值

选两个就可以得到 1+2, 1+3, 2+3 三种价值

选三个就可以得到 1+2+3 一种价值

所以最后答案就是

价值 1 2 3 4 5 6
方案数 1 1 2 1 1 1

(more…)

Read More

BZOJ-2001. [HNOI2010]City城市建设

题目给定一个有 n 个节点,m 条边的有向图,以及 q 个修改,每个修改更改一条边的权值,并且询问修改后的图的最小生成树,n\leq 20000, m \leq 50000, q \leq 50000

看了这篇题解才会做的QAQ

题目核心思想是分治以及缩小图的规模,有两个操作

Contraction:删除必须边

把待修改的边标记成 -\infty,然后跑一次最小生成树,显然这时候出现在生成树中非 -\infty 的边肯定会在之后的生成树中,所以我们记录下它们的权值和,然后在下一层分治的时候删除这些边

Reduction:删除无用边

把待修改的边标记成 \infty,然后跑一次最小生成树,没出现在生成树中的非 \infty 边在之后的生成树中肯定也不会出现(因为在当前图构造出的MST中,加入这条边会生成一个环,而且它是这个环中权值最大的边,然而在之后的图中,\infty 边只会变小,它还是权值最大的边,所以肯定不会出现在MST中),于是将它们删除,继续分治

然后每层分治过程中都进行 Contraction-Reduction 来缩小图的规模,在最后一层分治的时候使修改生效,做一遍MST就可以了(这时候图已经很小了所以会很快)

(more…)

Read More

BZOJ-3695. 滑行

这是 2014 年福建省省队训练的时候首长出的一道题,然后听完讲评后整个人就不好了,题目大概是这样的

首长NOI惨跪,于是去念文化课了。现在,他面对一道物理题

现在有一个小滑块可以在地面上滑行,地面上被划分成不同的区域,使得小滑块在不同的区域内部有一个不同的速度上限

小滑块在(0,0)点,我们现在要推动小滑块到目标点(x,y)

地面上有 N 层区域,每层区域都是矩形,现在给你一个序列 \{H_i\} 表示每层区域的高度,覆盖的地面横坐标范围是 0~X,第i个区域的限速是 v_i

注: Y=\sum_{i=1}^nH_i,其它的地方小滑块不允许进入

现在我们要设计一个路线使得小滑块滑到目标点的用时最小

如果你知道两个物理学的定理(光的最速原理、折射定律),那么这题就可以很快解出来了

(more…)

Read More

NOI2012. 迷失游乐园

放假了,小Z觉得呆在家里特别无聊,于是决定一个人去游乐园玩

进入游乐园后,小Z看了看游乐园的地图,发现可以将游乐园抽象成有n个景点、m条道路的无向连通图,且该图中至多有一个环(即 m 只可能等于 n 或者 n-1,并且环上节点个数不超过 25 个)。小Z现在所在的大门也正好是一个景点

小Z不知道什么好玩,于是他决定,从当前位置出发,每次随机去一个和当前景点有道路相连的景点,并且同一个景点不去两次(包括起始景点)。贪玩的小Z会一直游玩,直到当前景点的相邻景点都已经访问过为止。小Z所有经过的景点按顺序构成一条非重复路径,他想知道这条路径的期望长度是多少?

小Z把游乐园的抽象地图画下来带回了家,可是忘了标哪个点是大门,他只好假设每个景点都可能是大门(即每个景点作为起始点的概率是一样的)

同时,他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点

(more…)

Read More

BZOJ-3157. 国王奇遇记

题目大意是要求下面这个式子

 \begin{eqnarray*} \sum_{i=1}^n m^i \cdot i^m \end{eqnarray*}

这个题目有三个版本:

BZOJ-3157 m \leq 200

BZOJ-3516 m \leq 1000

BZOJ-4126 m \leq 500000

这篇文章介绍 \mathcal O(m^2)\mathcal O(m) 两种做法

为了方便,定义一个函数 f(i)

 \begin{eqnarray*} f(i) = \sum_{k=1}^n k^i \cdot m^k \end{eqnarray*}

然后使用“扰动法“

 \begin{eqnarray*} (m - 1) \cdot f(i) & = & \sum_{k=1}^n k^i \cdot m^{k + 1} - \sum_{k=1}^n k^i \cdot m^k \\ & = & \sum_{k=1}^{n + 1} (k - 1)^i \cdot m^k - \sum_{k=1}^n k^i \cdot m^k \\ & = & n^i \cdot m^{n + 1} + \sum_{k=1}^n m^k \sum_{j = 0}^{i - 1} {i \choose j} \cdot (-1)^{i - j} \cdot k^j \\ & = & n^i \cdot m^{n + 1} + \sum_{j = 0}^{i - 1} {i \choose j} \cdot (-1)^{i - j} \sum_{k = 1}^n k^j \cdot m^k \\ & = & n^i \cdot m^{n + 1} + \sum_{j = 0}^{i - 1} {i \choose j} \cdot (-1)^{i - j} \cdot f(j) \\ \end{eqnarray*}

然后这个算法的复杂度是 \mathcal O(m^2) 的,但是这题最快可以做到 \mathcal O(m) 的!

(more…)

Read More