分类 题解 下的文章

今天模拟赛的第二题,还是大水题,但是由于 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

本题有虚树做法,基本思想差不多,但个人感觉还是换根树剖清真一点 233。

定义一组询问的根节点为这组询问的一号节点。

一个点会对答案产生贡献,当且仅当这个点到这组节点的其他节点的距离大于等于这个节点到这组询问的根节点的距离。

假设当前我们做到根节点为 root ,当前节点为 u 的情况,找出这条路径的中点为 mid ,那么肯定不会对答案产生贡献的点即整颗树 root 为根节点时 mid 这个节点的整颗子树。就是一个简单的换根树剖,乱搞一下即可。

READ MORE

考虑离线做法,每个物品存在的时间一定是一段连续的区间。建一棵线段树按时间分治,乱搞一下。

考虑在线做法:有一个部分分是只会在一端进行插入删除操作,那么我们开个栈,插入元素就加进去,删除就弹出。复杂度 O ( n m ) ;既然我们需要在两端操作,那么我们只要维护两个这样的栈即可,查询时把两边的 dp 数组合并。暴力合并是 O ( m ^ 2 ) 的,会 TLE ,所以我们把一个数组放在线段树上,枚举另一个数组的每一个数,做一下区间查询即可。同时有个问题即有可能在前端删除从后端插入的元素,这种时候我们暴力重构两个栈,各放一半的元素,就能保证复杂度。最后总时间复杂度 O (n \log n \times m \log m) ,可以通过此题。

由于笔者在做题时把合并的 O (m ^ 2) 算成了 O ( m ) 所以去写了在线做法,还好想出了线段树才捡回一条命 233。

READ MORE