几度风雨几度春秋 风霜雪雨博激流
历尽苦难痴心不改 少年壮志不言愁

考虑 Min-Max 容斥,\min(S) 表示至少一个从 s 走到至少一个属于集合 S 的点的期望时间。

f(i, S) 表示集合 Si 到任意 u \in S 的期望时间,则 \min(S) = f(s, S)

f(i, S) = \begin{cases} 0 &(i \in S) \\\\ \frac{\sum_{i \to j} f(j, S)}{d_i} + 1 &(i \notin S) \end{cases}

可通过高斯消元求出,但复杂度过大不能接受。 考虑把原式化为 f(i) = k_i \times f(father_i) + b_i 的形式,推导过程略。 对于每个查询状压处理 \max(S) 不现实,需要处理出每个子集,FWT 一下即可 AC 。

READ MORE

Min-Max 容斥:

\max(S) = \sum\limits_{S' \subseteq S} \min(S') (-1)^{|S'| - 1}

可以用二项式反演证明:构造容斥函数 f(x) 使得

\max(S) = \sum\limits_{S' \subseteq S} \min(S') f(|S'|)

考虑每个 S' \subseteq S\min(S') = a_{x+1} 对答案的贡献为:

g(x) = [x = 0] = \sum\limits_{i=0}^x {x \choose i} f(i+1)

二项式反演得:

所以:

\begin{aligned} \max(S) &= \sum\limits_{S' \subseteq S} \min(S') f(|S'|) \\ &= \sum\limits_{S' \subseteq S} \min(S') (-1)^{|S'| - 1} \end{aligned}

READ MORE

考虑到原问题等价于求第 i 行的 l_ir_i 的值为 1 ,其他为 0 的行列式的值。

我们采用高斯消元,复杂度 O(n ^ 3) ,可以获得 70 pts.

考虑优化,由于 1 的位置是连续的区间,采用左偏树维护每个左端点的右端点最小值即可。

注意行列式中交换两列,行列式的值取相反数;如果不能消成单位矩阵,则行列式的值为 0

READ MORE

之前特别喜欢那种动态博客,因为它能够提供一种更加简洁直观的编辑页面,而不是像 Hexo 一样,要从一堆 .md 文件中找出自己需要编辑的那个。

当然, Hexo 下这个问题也不是无解,所以这篇文章就来简单的介绍下在 Hexo 的文章管理插件。

READ MORE

可能有点假,但没有用线段树......

首先肯定会在 LCA 处集合,通过树剖 + bitset 维护出可选的集合。然后利用 Hall 定理进行完美匹配统计答案。可以发现直接树剖 + 暴力跳是 O(n ^ 2) 的,所以限制树链的长度至多为 S ,则复杂度为:O(n + qcS\times\frac{m}{32} + qc \times \frac{n}{S} + q \times 2^c \times \frac{m}{32}) ,取 S = \sqrt n

试了一下可以被极端数据卡掉,但是 BZOJ 上的数据是随机生成的所以跑的飞快 QAQ ...

READ MORE

首先,我们需要知道如何利用后缀数组对一个指定的字符串计算字典序 Rank 。我们以 abaab 为例:

    a    a    b
   11   10    9
    a    b
    x    8
    a    b    a    a    b
    x    x    7    6    5
    b
    4
    b    a    a    b
    x    3    2    1

按照顺序进行编号,因为本质相同的字符串不重复计算次数,所以每一行的前 height_i 个不计入个数,所以我们也有了一个很自然的 O(n ^ 2) 做法。

接下来我们考虑正解,可以发现,每次可以看做对上面的字典序 Rank 数组进行了依次递减的区间覆盖,可以使用线段树维护。同时我们可以发现,这个 Rank 是递减的,而前缀和是递增的,所以我们可以二分出相等的那个位置。

READ MORE

这个数据范围容易让人想到网络流,问题在于这个网络流怎么流?

首先可以发现,如果我们要放石头,一定只会放在 x + y 为奇数的格子,否则放了不如不放。所以把这些点拆点,连一条费用为 a[x][y] ,流量为 1 的边。

接下来,我们可以构造一种对 x + y 为偶数的格子的黑白染色方案,使得一个 L 型石头的两个 x + y 为偶数的格子异色。容易发现,我们只需要对所有 xy 都是奇数的格子染黑, xy 都是偶数的格子染白。同理,拆成两个点,中间连一条费用为 0 ,流量为 1 的边。

同时,为了使得总放置的石头数为 m ,我们还需要再建一个点 P

于是源点 SP 连边, P 向黑点连边,黑点向 x + y 为奇数的点连边, x + y 为奇数的点向白点连边,白点向汇点 E 连边即可。

需要注意的是,我们跑最大费用最大流,但是我们只需要费用最大,而不是流量。由于我们采用增广路算法,每次新增的流量的花费一定递减,所以当花费是负数时直接跳出即可。

READ MORE

今天模拟赛的第二题,还是大水题,但是由于 SPFA 打错调了好久,还有这个 SB 出题人怎么说都不说一句读入的 L 是 long long 范围的啊,你™咋不上高精

好了,回归正常的题解。本题可以理解为 POI2000 病毒 的加强版(连样例都一样),于是按照惯例,我们只需要建造一棵 AC 自动机。如果能够找到环,那么一定能够产生无限长度的答案串,直接输出 Yes 即可。否则就是一棵 DAG ,跑一下 SPFA (或 BFS)求出最长的答案串,和要求的 L 比较一下就好。

我不会说我写了个 SPFA 还写挂调了两个小时的...

READ MORE