CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
[[http://wiki.buaaacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95|back]]

====== 2020/08/29--2020/09/04 周报 ======

===== 团队训练 =====

===== 姜一凡 =====

[[..:qgjyf2001:异或方程组]]

==== 专题 ====

==== 比赛 ====

==== 题目 ====

===== 蒋贤蒙 =====

==== 专题 ====

[[..:jxm2001:字符串_2|字符串 2]]

[[..:jxm2001:字符串_3|字符串 3]]

[[..:jxm2001:字符串_4|字符串 4]]

==== 比赛 ====

==== 题目 ====

===== 王赵安 =====

==== 专题 ====

[[..:lgwza:可持久化数组|可持久化数组]]

[[..:lgwza:主席树|主席树]]

[[..:lgwza:拆点|拆点]]
==== 比赛 ====

==== 题目 ====

===== 本周推荐 =====

==== 姜一凡 ====

[[https://www.luogu.com.cn/problem/P2447|洛谷p2447]]

=== 标签 ===

异或方程组

=== 解析 ===

异或方程组的模板题

==== 蒋贤蒙 ====

[[https://www.luogu.com.cn/problem/SP1812|SP1812]]

=== 标签 ===

后缀数组，后缀自动机

=== 题意 ===

给定 $n$ 个串，求 $n$ 个串的 $\text{LCS}$。

=== 题解 ===

先考虑两个串匹配的情况。考虑将一个串压入 $\text{SAM}$，另一个串在 $\text{SAM}$ 上匹配。

如果存在 $ch[pos][c]$，则直接匹配，且匹配长度 $+1$。否则考虑尽可能地保留后缀，于是不断跳 $\text{parent}$ 树。

由于当前串的后缀与当前等价类地某个串匹配，而该等价类的最短串长度大于父节点等价类中最长串，于是当前串一定能与父节点最长串匹配。

于是跳 $\text{parent}$ 树过程中如果遇到 $ch[pos][c]$ 存在的情况，则跳到 $ch[pos][c]$ 结点，匹配长度变为 $len_\text{pos}+1$。

每次失配向上跳使得匹配长度变短，而匹配长度最多增加 $|T|$ 次，于是失配的均摊复杂度为 $O(1)$。时间复杂度 $O(|S|)$。

接下来考虑 $n$ 个串匹配的情况。先将一个串压入 $\text{SAM}$，其他所有串在 $\text{SAM}$ 上匹配。

对每个串，记录每个结点匹配的答案，然后每个结点取该结点所有匹配答案的最小值，然后所有结点的最大值即为所求答案。

注意 $\text{parent}$ 树的子节点可以将答案贡献给父节点，可以每次匹配后根据拓扑序转移答案。时间复杂度 $O(\sum |S|)$。

=== 评价 ===

后缀自动机基础题。

==== 王赵安 ====

[[https://codeforces.com/contest/12/problem/D|CodeForces 12D Ball]]

**标签**

线段树

**题意**

有 $n$ 个人，每个人有三个属性($a_i,b_i,c_i$)。如果一个人的三个属性均小于另一个人的，那么他将告辞。问最后有多少人告辞。$1\le n\le 5\times 10^5$

**题解**

首先将第一维离散化，第二维从大到小排序，以第一维为坐标在线段树中插入第三维的值。由于逐个插入，第二维一定递减；对于每个新插入的数只要保证它插入位置后面的区间最大值比这个数小就不会告辞。时间复杂度 $O(n\log n)$

**评价**

三维偏序用线段树解，感觉非常妙，线段树的应用十分灵活。
CVBB ACM Team

用户工具

站点工具

页面工具
