emerald's blog

想要得到拓扑序的图一定是有向图. 拓扑序列虽然不止1个,但都满足,每个点的前驱后继点的顺序，某点的后继点在拓扑序中不可能出现在该点的前面, 基本思想： 拓扑序列满足，入度为0的点进入序列，且该点的出边点的入度-1, 如果该点出边的入度为0,则重复第1步 邻接表+bfs 开一个数组记录所有点的入度,将入度为0的点加入到队列 取出队头,加入到拓扑序. 更新出边的点的入度,判断是否为0，为0加入队

timu题目：给定一个非空字符串 s 和一个包含非空单词列表的字典 ，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明：拆分时可以重复使用字典中的单词。字典中没有重复的单词。样例：示例 1： 输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可

邻接表存图 1234567891011121314151617181920212223242526#include <iostream>using namespace std;const int maxn = 1e6;int ver[maxn],next[maxn],head[maxn],edge[maxn];int tot = 0;// 存图void add(int u,int v

1.合并2个点时，可以判断2个点是否属于一个联通分量，如果不属于，那么加入该连通分量，2. 最后判断该图 有几个单独的联通分量，3. 或者将图压缩成 最小生成树时，判断每个点是否属于最小生成树中，不是就加入树中， 用一个pre[i]表示点i在图中的顶点，初始化时每个点i（都是一个单独的联通分量）所以顶点就是，判断联通分量的数量也是判断pre[i] == i， 合并两个u,v，一开始标记pre[u

欧拉函数例题 除了(1,0)(1,1)(0,1)三个点的，发现其余可视点gcd(x,y)=1 发现关于(1,1)这条线所有点都是对称的，不妨取下半部分，x<y,此时1<=x<y<=n,这就转化到求与y互质数x的个数, y有多个选择,且y>=2,最后答案从2~N累加起来 求欧拉函数值，就是分解质因数的过程，1.试除法分解质因数累加和，但是只能求出 $\upsilon

互质 gcd(a,b) = 1 则a,b互质, gcd(a,b,c) = 1 则两两互质gcd(a,b) = gcd(a,c) = gcd(b,c) = 1 欧拉函数定义:[1,N)中与N互质数的个数被称为欧拉函数,记作 $\upsilon(N)$由算数基本定理知：$N = p_1^{c_1} * p_2^{c_2}*p_3^{c_3}*……*p_i^{c_i}$ 先推倒i=2

回文字符串分为奇回文和偶回文，在字符串中间插入任意字符使得串变成奇回文串 暴力思想：肯定是找一个点往两边任意扩展,遍历一次,Manacher时间为O(n) 开一个数组p[]记录 以点i为中点 的最长回文串的半径, 假设前i-1个点的p[]都已经求出来来，现在考虑p[i]如何推导 重点：3. R是p[1]~p[i-1]中推出来的右端最远最长回文子串的右端点,且用pos记录下来，每一步更新po

这么简单的我都想不出来思路： 开一个vis[]标记在区间[l,r]中已经出现的画的数量,当每个画vis[i]==1那么看到的画的数量++,左端如果画的数量>1那么向左移动, 右端不断标记然后加入队列中，当 画的数量=画家的数量 记录区间端点值 1234567891011121314151617181920212223242526272829303132#include <iostr

poj1961思路： 满足 $i % (i-prefix[i]) == 0$ 且i != i-prefix[i] ,说明当前子串S[1~i]的长度是（最长公共前后缀）的前缀长度的倍数，那么 i/(i-prefix[i])就是循环节的个数 123456789101112131415161718192021222324252627282930313233343536373839

kmp 匹配的目的是 询问一个字符串s1 len(s1)<=len(s2) 是否是 字符串s2 的子串 s1 叫做 pattern模式串 暴力匹配都知道 abcde 前缀：a ab abc abcd abcde 真前缀不包括abced 后缀同理 所以我们求出s1的prefix[]要后移一位，才是最长公共(真)前后缀 为什么prefix[]要右移？？？ 当不断比较s2[i] 与 prefi