再整理一遍板子 后缀数组 例题cf432D：问对字符串s，对于所有的前缀，当它等于同长度后缀时，这个子串一共在s中出现多少次。 后缀数组求lcp是logn，显然直接二分即可。复杂度nlogn 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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65...

和自然溢出法不同的是，这种方法需要取模，并且是两套base mod。每次做哈希操作时，需要两套哈希值都一致，这就大大降低了冲突概率。但是据说常数比较大，并且写起来麻烦一些。 CF1320D 对于一个01串（2e5），给出两种操作：110<->011，可以执行任意多次，q（2e5）个提问，问这个串中某两个子串能否通过这两种操作互相转化。 分析可知，这种操作实际上就是把0左移或右移2位，也就是偶数次，那么如果这两个串中0出现的奇偶序列相同（比如第一个0都是奇数位上，第二个0都是偶数位上）那么就一定能互相转化成功，如果奇偶不同例如某两个0相邻，那是无法彼此转化的。所以问题就变...

https://ac.nowcoder.com/acm/contest/4862/E 给n（<=20）头牛，每头牛有自己的身高、重量、承重，要让它们叠罗汉并高度至少是h，并要求剩余的载重量最大（说明最稳），求这个最大剩余载重量。 这题初看直接暴搜剪枝，，仔细一想才发现复杂度不对，是20！的。然后就没辙了，直到看了这篇博客，果然还是有藏着很隐蔽的关系约束的hh，核心思路是想到对于每种方案就是求si-sum{wi+1..wn}的最小值。然后对于所有方案再找最大。 代码就直接按二进制遍历即可。 1 2 3 4 5 6 7 8 9 10 11 12 13 ...

序列自动机其实就是一个数组，记录了每个位置后第一次出现字符c是哪个位置，用于解决一些子序列的问题，它共有n+1个状态，即位置0-n，每个状态都是子序列的接受状态。这个数组在On内完成构建 CF1303E：给字符串s、t问能不能从s中抽取两个不重复的子序列拼接成t。由于长度最大400，考虑枚举两个子序列的分界点，然后两个指针指向两个序列已满足的位置。最初考虑的算法是，直接看这两个指针之后的字符哪个能被较近的字符满足，就先让那个指针增1，这种算法整体是n^2的但有问题就是如果两个指针后需求的字符相同，就没法判断了，所以最后我们还是要用dp。 dp的话依然先枚举分界位置，然后设置dp[i][...

cdq分治，也叫时间分治，核心概念就是对于若干个操作和查询，维护每次操作在哪个时间段中有效。 https://ac.nowcoder.com/acm/contest/888/E?&headNav=acm 这道题中的size就是时间，我们维护某个size区间上点的连通状况（用并查集维护），进行查询时进入某个点则连上这个点上的边，退出它时把并查集再复原。 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 28 29 30 31 32 33 34 35 36 37...

题目 cdq分治，也叫时间分治，核心概念就是对于若干个操作和查询，维护每次操作在哪个时间段中有效。 这道题中的size就是时间，我们维护某个size区间上点的连通状况（用并查集维护），进行查询时进入某个点则连上这个点上的边，退出它时把并查集再复原。 #include<bits/stdc++.h> using namespace std; #define lson rt<<1 #define rson rt<<1|1 const int maxn=1e5+2; int n,m; int fa[maxn],h[maxn]; int fnd(int x){...

写作业代码需要读文件，图方便直接用了freopen重定向输入流，可是后面发现还要切换回控制台输入。于是查资料。 发现大多博客都介绍用freopen("CON", "r", stdin); 这句来改回去，可是实际测试中发现使用了之后scanf是正常读入了，cin却不行。灵光一现想到用cin.clear()清空一下输入流试试，果然可以了

https://codeforces.com/problemset/problem/593/D 看到题目是逐步向下取整我还想了一下……其实对于整型来说和把路径上的值乘在一起统一除效果是一样的。 这题还有一个点就是它的权值是依附于边而非点，对此我们可以把每个点和它连向fa的边绑定，把这个权值重新转换到点上，因为每个点只有一个fa。而对于根我们可以给它一个向上的虚边赋值1，这个过程用一个简单dfs来做 实际写题当中wa了好久……最后才发现是线段树的update参数没用ll #include<bits/stdc++.h> using namespace std; #define...

https://ac.nowcoder.com/acm/contest/881/I 不得不说这题是真的难，看题解都差点没用理解。） 给定平面上若干（1e5）点，每个点ab两个权值，要求将其分为两组，a组的a权值和加b组的b权值和最大，划分条件转化一下就是，不能有a出现在b的右下，也就是要找到一条不降的折线，其上是a，其下是b。我们认为位于折线上的那些点属于b。 暴力dp是可做的，离散化xy并枚举每一列的划分点。考虑优化，认为dp[i]表示，加入i点后，如果折线的最后一个转折点是i，那么总和的最大值。它该怎么更新呢，对于点1~i-1，如果它们比i低，那折线就可以从它们那里拐过来，然后...

https://ac.nowcoder.com/acm/contest/883/A 题目大意，给出一个无向图，设S(x)表示x的临近点集合，临近点即通过一条边直接相连的点。有两种操作，1是把边集合（读入顺序）从l到r的边状态反转（相连变断开，断开变相连），2是询问两个点的临近集是否相等。 这里首先涉及到的一个难点是如何表示临近集，我们采用异或哈希的方式，首先为所有点分配一个随机权值，这里用到了一个新版的随机函数 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); for(int i=1;i&lt...