Solution 这是一道数组上的异或问题, 这类问题一般要使用前缀异或和作为辅助, 即sum[i] = a[1] ^ a[2] ..... ^ a[i];它具有这样的性质sum[i] ^ sum[j - 1] = a[j] ^ a[j + 1] .... ^ a[i]; (i >= j)其次我们要明白一个问题 两个区间异或为0 等价于 两个区间的异或和相等再看到问题我们考虑枚举一个边界i, 然后看以 i 为右端点的区间和 以 i 为左端点的区间里异或和相等的数量  #pragma GCC optimize(3) #include <bits/stdc++.h> using ...

树学 Solution 题目求最小的, 考虑找树的重心, 其所有的子树中最大的子树节点数最少。能保证每一个子树中的点深度和是最小的, 然后从重心开始给每个点赋深度, 求一下和即可。那么问题就转化为如何求重心, 这是树形dp的一个经典应用, 用cnt[i] 表示 i 点的子树的节点有 dp[u] = max(dp[u], n - cnt[u]) 找一下 dp[u] 的最小值即是重心然后进行 bfs 一遍赋深度即可注意这道题 vector 会超 1s, 比赛的时候时限只给 1s , 后面改成 2s。比赛时卡了vector, 建议使用链式前向星。 #pragma GCC optimize(3) #i...

后缀自动机——一种解决字符串问题的强力数据结构[^5] 后缀自动机的引入  后缀自动机(Suffix automaton, SAM)是IOI国家队成员陈立杰在2012年的冬令营从国外引进的一种数据结构, 它能在线性时间内解决许多字符串问题。 字符串的 SAM 可以理解为给定字符串的所有子串的压缩形式。值得注意的事实是，SAM 将所有的这些信息以高度压缩的形式储存。 SAM的定义  字符串 的 SAM 是一个接受 的所有后缀的最小 (确定性有限自动机或确定性有限状态自动机)。它能且只能接受所有 的后缀, 并且拥有最少的状态与转移。 SAM的用途  考虑一个前置问题, 如果要在一个 (有向无环图)...

A. 打怪 Solution 签到题,我是直接模拟,一开始我的做法是令cnt > 1e4 的输出直接输出 -1, 没想到超时了,出题人没给 t 的大小,上当了..于是考虑下 -1 的情况,显然当我们的攻击大于等于小怪的血量时,我们每次都能先手的情况下,可以秒杀小怪不会掉血所以, 当 h <= a 的时候输出 -1 其他情况模拟即可,时间复杂度PS:其实也可以二分,当数据大的时候直接二分能打的怪数也是可以的,但对于这道签到题,就不画蛇添足了. Code #pragma GCC optimize(3) #include <bits/stdc++.h> using names...

后缀数组 [^3] 一点题外话  好久之前就想学习后缀数组相关算法,但是苦于自己的基础知识不够扎实,而且这个算法对初学者来说难度过高。要大致理解其中的思想其实不难,但是要进行代码实现需要花很大的功夫去理解,静下心来参透每一步的细节。借着这次读书笔记作业的任务，我花了一天的时间对资料进行整理,对代码进行逐行理解和测试,终于对后缀数组的算法有一定的理解了。 后缀数组的实现  首先引入一些定义:  子串: 在字符串 s 中, 任取 i, j(i <= j) 截取字符串 s 从 i 到 j 的一段称为 s 的子串 后缀: 字符串 s 从某个位置 i 开始到末尾的子串, 称为 s 的一个后缀， 定...

另一个问题的提出  我们注意到KMP算法所能优化的是一种单模式串的匹配,那么考虑多模式串的匹配下,KMP算法的复杂度是多少呢？显然，对于每个模式串,我们都要进行一次KMP算法,当有k个模式串时,它们的长度分别是m1,m2....mk,那么我们需要做k次KMP算法,时间复杂度是 此时复杂度不再优秀。基于这个问题,我们来讨论下一种适用于多模式串匹配的算法——AC自动机。 AC自动机——一种多模式串匹配算法[^2] 什么是AC自动机？  Aho-Corasick automaton，简称AC自动机,该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。初次接触AC自动机这个名词,会感觉很陌生和遥...

Solution 太菜了,看了雨巨的题解才发自己读错题了 自闭了一天题目提到如果我们选择i点i点到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑那么我们就可以考虑从叶子开始取,因为取非叶子节点永远无法将叶子节点染黑这样显然就可以用dfs递归从叶子往根染黑其次,我们发现从叶子节点往上的点可能会因为选取叶子节点而被染黑但是被染黑不代表就不取,我们可以简单的运用一个等价替换的思想: 考虑图上这种情况,显然权值为3这个点我们一定要取,而它的父亲节点是B权值为1,显然不用取但是呢,我们可以转换思路,把权值3 - 1赋予给它的父亲节点,取个max即可 a[fa] = max(a[fa]...

Solution 分析题意,要求我们求出每一个奇数长度前缀的中位数对于每一个奇数长度前缀,设长度为len,求中位值其实就是求区间第(len + 1) / 2大那么显然这就是一道求区间第k大的模板题了我们直接上主席树,秒掉这个问题这里简单介绍下主席树主席树又叫可持久化线段树，它是基于线段树发展而来的一种数据结构。给线段树增加一些历史点来维护历史数据，使得我们能在较短时间内查询历史数据。主席树思想是每个位置都维护一个线段树，线段树的节点是值的范围。然后第i个线段树中某个区间[x, y]维护的是，1-i中数字在[x, y]范围内的个数。因此我们运用前缀和的思想,在主席树上二分递归求解即可求出区间第k...

A. Maximize The Beautiful Value Solution 看了半天才看懂,forward向前是从右往左挪动,我们知道一个数字往前挪动k个位后,位置为i - k。注意到i - k 到 i - 1 这个范围的数字他们都会相应往后挪,即我们的答案会加上sum[i - 1] - sum[i - k - 1]因此,只需要从k + 1位开始枚举每一位,求最大值就行了 #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef lon...

A 环球旅行 Solution B 恢复数列 Solution 由于解一定存在,我们考虑构造 a[1] 为 n , 用一个 vector 存取后面的构造值首先将 m 个 n - 1 放入 vector 里,如果此时 vector.size() == n - 1 则构造结束否则我们删去 vector 的第一个元素v[0], 在后面补上 m 个 v[0] - 1，重复上述过程直到出现 vector.size() == n - 1但是正确性我不会证明orz Code #pragma GCC optimize(3) #include <bits/stdc++.h> using namesp...

Solution  Code #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long long LL; const int N = 1e6 + 5; const ll mod = 1e9 + 7; const int DEG = 20; const double PI = acos(-1.0); const double eps = 1e-10; const ll inf = 1e18; static auto faster_io...

Solution  Code #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long long LL; const int N = 1e6 + 5; const ll mod = 998244355; const int DEG = 20; const double PI = acos(-1.0); const double eps = 1e-10; const ll inf = 1e18; static auto faster_...

前言   众所周知,串与序列的算法是计算机科学领域的经典研究课题,尤其是在告诉互联网、大数据与云计算及人工智能已经上升为国家战略性新兴产业的新时代，它的发展与应用更显示出勃勃生机。在生物信息学、信息检索、语言翻译、数据压缩、网络入侵检测、序列模式挖掘等诸多具有挑战性的前沿科学领域中，串与序列的算法都扮演着关键的角色。应用高效的串与序列的算法将是推进和提高这类先进系统总体性能的重要手段。 在大学这三年我学习了许多关于字符串的算法，下面我将以读书笔记的形式复习并归纳总结一些自己的心得体会。  正文 KMP——我学习的第一个字符串算法  我第一个学习的字符串算法是KMP算法，他由Knuth、Prat...

A 咪咪游戏 Solution  Code #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long long LL; const int N = 4e5 + 5; const ll mod = 19961993; const int DEG = 20; const double PI = acos(-1.0); const double eps = 1e-10; const ll inf = 1e18; static auto f...