• 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-2780SPOJ-JZPGYZ

  • BZOJ-4001. [TJOI2015]概率论

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

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

  • 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 对

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

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

  • 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
  • 区间 K 小问题

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

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

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