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

首先肯定会在 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

@GNAQ 给的博弈劲爆题,让人无言以对 233.

k > 2

对于这种情况,我们可以发现任何时候一定可以给空白格子染色。所以我们只需要判断剩余空白格子的奇偶性即可

k = 1

显然被已经染色的格子分隔出的连续空白格子是不会相互影响的,所以我们可以把他看做一个组合 Nim 游戏,最后判断求一下每个游戏的 SG 函数异或和。

首先你要知道 mex 函数是什么,这里不再赘述,以下的打表程序中用到的实现是:

int mex(const std::set <int> &set) {
    if (!set.size() || *set.begin()) return 0;
    for (auto i = set.begin(), j = ++set.begin(); j != set.end(); i = j, j++)
        if ((*i) + 1 != (*j)) return (*i) + 1;
    return (*--set.end()) + 1;
}

此时题目可以转换为每次染色的格子必须与已经染色的格子不相邻。设 sg1 ( x ) 为有连续 x 个空白格子可以放的 SG 值,则可以推出式子(注意边界情况):

sg1(i) = mex ( sg1 ( j ) \oplus sg1 ( i - j - 3) ( 1 \leq j \leq i - 4), sg1(i - 2), sg(i - 3))

写个程序打表:

sg[0] = 0, sg[1] = 1, sg[2] = 1, sg[3] = 2;
for (int i = 4; i <= n; i++) {
    set.clear(), set.insert(sg[i - 2]), set.insert(sg[i - 3]);
    for (int j = 1; i - j - 3 >= 1; j++)
        set.insert(sg[j] ^ sg[i - j - 3]);
    sg[i] = mex(set);
}

跑出来以后,你可能会大叫这是什么 ** 玩意儿,下面是表:

1 1 2 0 3 1 1 0 3 3 2 2 4 0 5 2 2 3 3 0 1 1 3 0 2 1 1 0 4 5 2 7 4 0
1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 2 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 8
1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 8
1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 8
1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 8

可以发现每 34 位一循环,除了第一行和第二行有些特例(我才不会告诉你我是因为当初没仔细看后几位的差别才找到这个循环节的...)

k = 2

同理,我们可以这样假设 SG 函数(请注意这里的定义与 k = 1 有略微的差别):

  • sg2(x, 0) 表示连续 x 个空白格子且两端格子相同
  • sg2(x, 1) 表示连续 x 个空白格子且两端格子不同
  • sg2(x, 2) 表示连续 x 个空白格子且一端是已经染色的格子,另一端是边缘
  • sg2(x, 3) 表示连续 x 个空白格子且两端都是边缘

虽然最后一种情况,但是数据里并没有,你不判断也没什么关系。

然后推一波式子(懒得写 \LaTeX 了,直接看下面的打表程序)

sg[0][0] = sg[0][1] = sg[0][2] = sg[0][3] = sg[1][1] = 0;
sg[1][0] = sg[1][2] = sg[1][3] = 1;
for (int i = 2; i <= n; i++) {
    set.clear(), set.insert(sg[i - 1][1]);
    for (int j = 1; i - j - 1 >= 1; j++) {
        set.insert(sg[j][0] ^ sg[i - j - 1][0]);
        set.insert(sg[j][1] ^ sg[i - j - 1][1]);
    }
    sg[i][0] = mex(set);

    set.clear(), set.insert(sg[i - 1][0]);
    for (int j = 1; i - j - 1 >= 1; j++)
        set.insert(sg[j][0] ^ sg[i - j - 1][1]);
    sg[i][1] = mex(set);

    set.clear(), set.insert(sg[i - 1][2]), set.insert(sg[i - 1][0]), set.insert(s[i - 1][1]);
    for (int j = 1; i - j - 1 >= 1; j++) {
        set.insert(sg[j][0] ^ sg[i - j - 1][2]);
        set.insert(sg[j][1] ^ sg[i - j - 1][2]);
    }
    sg[i][2] = mex(set);

    set.clear(), set.insert(sg[i - 1][2]);
    for (int j = 1; i - j - 1 >= 1; j++)
        set.insert(sg[j][2] ^ sg[i - j - 1][2]);
    sg[i][3] = mex(set);
}

可以发现:

  • sg2(x, 0) = 1
  • sg2(x, 1) = 0
  • sg2(x, 2) = x
  • sg2(x, 3) = x \mod 2

综上所述即可写出程序。

READ MORE