本周无

本周无

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

• Codeforces Round 665 C - Mere Array
  • 分类：思维
  • 题目大意：有$n$个数，问能否从小到大排序，两个数能进行交换的条件是:这两个数的最大公约数是这个数组中最小纸
  • 数据范围：多组数据，$T \le 10^4$，$1 \le n \le 10^5$，$\sum n 10^5$
  • 解题思路：如果两个数能换那么它们都能和最小值换，所以只要所有位置不对的数都能和最小值换即可
  • Comment：较为简单的思维题
• Codeforces Round 665 D - Maximum Distributed Tree
  • 分类：dfs，贪心
  • 题目大意：有一棵树$n$个点，给定一个$k$，要求给每个边赋值，使得所有边的乘积是$k$且任意两点间距离和最大
  • 数据范围：多组数据，$T \le 100$，$2 \le n \le 10^5$，$\sum n 10^5$
  • 解题思路：由于题目给出的$k$是按照质因子给出，我们直接把质因子排序，然后对答案贡献大的边放大的质因子贪心即可
  • Comment：非常显然的贪心题

本周无

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))$，问选定一行一列最多能覆盖多少个点。

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

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

陶吟翔：

题目大意：给定$n$个数$a_1,a_2 \ldots a_n$，问有几个四元组$(i,j,k,l)$满足$i < j < k < l$且$a_i = a_k,a_j = a_l$

数据范围：多组数据，$1 \le T \le 100$，$4 \le a_i,n \le 3000$

解题思路：先$O(n^2)$预处理出每个位置往后某个数有多少，然后枚举$i$和$k$，每次$k$移动的时候会变两个数，直接计算合法的对数，如果此时$a_i=a_k$就把数加进答案

推荐理由：题目本身简洁明了，有多种解法，考察了做题者优化算法的能力以及通过合适的方式处理数据的能力

郭衍培：

题目大意：给定长度为$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)$

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