• May 1, 2015

    BZOJ-2780. Sevenk Love Oimaster

    题目给出 $n$ 个字符串 $s_1, s_2, \cdots, s_n$，以及 $m$ 个询问 $q_1, q_2, \cdots, q_m$，每个询问是一个字符串，要求计算 $q_i$ 在多少个 $s_1, s_2, \cdots, s_n$ 中出现过

    例如 $s_1=abcabc, s_2=ca, s_3=a$，那么 $abc$ 在 $s_1$ 中出现过，$a$ 在 $s_1, s_2, s_3$ 中出现过

    数据范围：$1 \leq n \leq 10^4, 1\leq q \leq 6\cdot 10^4, \sum_{i=0}^n |s_i| \leq 10^5, \sum_{i=0}^m |q_i| \leq 3.6 \cdot 10^5$

    题目连接：BZOJ-2780、SPOJ-JZPGYZ

  • Apr 29, 2015

    BZOJ-4001. [TJOI2015]概率论

    题目要求出一个含有 $n$ 个节点的有序二叉树的叶子节点的期望个数，$n \leq 10^9$，要求精确到 $1.0 \times 10^{-9}$

    例如一个含有 3 个节点的二叉树，一共有 5 种情况，期望的叶子节点个数是 $\frac{6}{5}$

  • Apr 27, 2015

    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 < k$ 且 $a_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 对

  • Apr 25, 2015

    从多项式乘法到快速傅里叶变换

    计算多项式的乘法，或者计算两个大整数的乘法是在计算机中很常见的运算，如果用普通的方法进行，复杂度将会是 $\mathcal O(n^2)$ 的，还有一种分治乘法可以做到 $\mathcal O(n^{\log_23})$ 时间计算（可以看这里）。下面从计算多项式的乘法出发，介绍快速傅里叶变换（Fast Fourier Transform, FFT）如何在 $\mathcal O(n\log n)$ 的时间内计算出两个多项式的乘积。

  • Apr 23, 2015

    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
  • Apr 5, 2015

    区间 K 小问题

    这篇文章将会介绍如何求解区间 K 小问题。

  • Apr 5, 2015

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

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

  • Dec 10, 2014

    BZOJ-3267. KC采花

    这题是 bzoj-3267 上的题目，原题大概是给一列数，要求支持操作：

    • 修改某个数的值
    • 读入 l、r、k，询问在 [l,r] 内选不相交的不超过 k 个子段，最大的和是多少

    然后序列的长度和操作的次数大约都在 $10^5$ 级别的

  • Dec 6, 2014

    BZOJ-3695. 滑行

    这是 2014 年福建省省队训练的时候首长出的一道题，题目大概是这样的

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

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

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

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

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

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

  • Oct 19, 2014

    NOI2012. 迷失游乐园

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

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

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

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

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

    这题是 NOI2012 的一道题目，前几天突然想找一题环套树的来做一做于是就找到了这题