本周无

无

2020.8.22 AtCoder Beginner Contest 176 prob:5/6 rank：889

P3796 【模板】AC自动机（加强版）

题意：对模式串在主串中出现的次数计数，输出出现次数最多的串。

解法：标准的 $ac$ 自动机模板题，但需要建成 $trie$ 图和利用 $next$ 数组来优化满足时限。

本周无

2020.8.22 AtCoder Beginner Contest 176 prob:5/6 rank：585

2020.8.25 Educational Codeforces Round #94 prob:5/5/7 rank:464

2020.8.22 AtCoder Beginner Contest 176 prob:5/6/6 rank：815

2020.8.25 Educational Codeforces Round #94 prob:5/5/7 rank:57

林星涵：AtCoder Beginner Contest 176 - E

题目大意:在一张 $H×W ，H、W \le 3e5$ 的图上，给定一些点 $(n \le min(H×W,3e5))$，问选定一行一列最多能覆盖多少个点。

解题思路:我们显然可以处理出覆盖点最多的行和列，然后依次枚举检查它们交叉的点处有没有点即可，由于点的个数有限，这个检查是符合复杂度的。

推荐理由：这种通过检验点的个数有限来保证暴力正确性的思路较为不错。

陶吟翔：

题目大意：

数据范围：

解题思路：

推荐理由：

郭衍培：

题目大意：给定长度为$2^n$的序列。q次操作，一共四种。一是单点修改，二是给定k，对任意i翻转$[(i-1)\cdot 2^k+1,i\cdot 2^k]$，三是给定k，对任意i交换$[(2i-2)\cdot 2^k+1,(2i-1)\cdot 2^k],[(2i-1)\cdot 2^k+1,2i\cdot 2^k]$，四是区间求和。

数据范围：$n\le 18,q\le 10^5$

解题思路：第二种操作，相当于$a_i$变为$a_{i\wedge (2^k-1)}$，第三种操作相当于$a_i$变为$a_{i\wedge (2^k)}$。因此可以用x表示，当前$a_i$变为$a_{i\wedge x}$。对于区间求和，相当于求$\sum_{i=l}^r a_{i\wedge x}$。不难发现，对[l,r]，若l和r的二进制正好从某一位开始,l都是0，r都是1，这一位前都相等，则[l,r]异或x后仍在连续的一段区间。而任意一段区间，都可以拆成log个满足上述要求的区间。因此可以用一棵支持单点修改，区间求和的线段树来完成这道题。时间复杂度$O(qn^2)$

推荐理由：不是数据结构的数据结构（虽然也用到了数据结构）