BZOJ5405 - platform

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

1
2
3
4
5
6
7
8
9
10
 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 是递减的,而前缀和是递增的,所以我们可以二分出相等的那个位置。

BZOJ5403 - marshland

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

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

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

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

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

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

首先 $c$ 没什么卵用,我们直接把他乘到属性里。

可以发现这里的 $d$ 是两个属性值减一减的绝对值,所以我们要考虑怎么维护这个绝对值。

我们先考虑 $K = 1$ 的情况,先把这些生物按照 $d$ 的大小排个序,那么后一个减前一个的值一定就是非负的,也就等于绝对值,直接扫一遍就好了。

接下来考虑 $K \not = 1$ 的时候的前 $K - 1$ 位,根据幼儿园学过的知识我们可以知道:

$$a - b \leq |a -b|$$

由于我们要求绝对值的和的最大值,所以我们只要枚举每个属性的正负把他们一起取最大值即可。

那么第 $K $ 位怎么办呢?我们可是要加上绝对值的相反数啊。没关系,采用之前 $K = 1$ 的时候的方法,减一减扫过去,就能保证你去到的值非负啦。

这题需要用到一个惯用的套路。

$$a - b \leq |a - b|$$

显然如果是 $a - b$ 非负的,直接取等号;如果 $ a - b $ 负数,那么绝对值就是正数,负数一定小于正数。

考虑到 $ 2 ^ 5 ​$ 并不是很大,我们可以暴力枚举每个数的符号(用状态压缩的方式)。然后维护一棵线段树进行修改和查询即可。

今天模拟赛的第三题(又达成了原题考试的成就)。考场的时候由于 T2 调太久这题暴力都没写… 现在依然不会正解于是写了个随机化算法 AC 。

每次随机两个点,然后计算出他们的连线的斜率,每次 $O(n)$ 判断一下选取与这条直线平行的两条直接的答案,随机个次几万次w就过了…

这里可能有个细节问题,也就是说我们每次选出的两个点中可能有不合法的点,实际上影响不大,因为我们可以通过略倾斜直线来取到另一个合法的点。

BZOJ4179 - B

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

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

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

BZOJ4178 - A

今天模拟赛的第一题, NTT 作多项式乘法,把后面的转移快速幂一下就过了。需要注意的是 950009857 的原根是 7 而不是 3 。

BZOJ2410 - Nim游戏

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

题解

k > 2

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

k = 1

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

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

1
2
3
4
5
6
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)) $$

写个程序打表:

1
2
3
4
5
6
7
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
2
3
4
5
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$ 了,直接看下面的打表程序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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$

综上所述即可写出程序。

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

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

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

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

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

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

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

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×