单链表与双链表的用处单链表单链表的存储：单链表的几种操作在表头插入一个数：先将这个数指向head指向的数，再将head指向这个数在表中的第k位后面插入一个数：先将这个数指向第k位指向的数，再将第k位指向这个数在表中删除一个数：让这个数直接指向下一个数的下一个数代码实现：/

二分图的判别：首先二分图是指一个图如果没有奇数环，则该图是二分图。其实这两种算法都是基于dfs来做的，要深刻理解每个算法的dfs指代的是什么。1、染色法：所谓的染色是指所有边的每一条边的两个端点颜色不同，算法思路就是让每个顶点都做一次dfs，判断其中有无同一条边的端点颜色相同。

伯恩斯坦引理：若\({\rmcard}X\le{\rmcard}Y\)且\({\rmcard}Y\le{\rmcard}X\)，则\({\rmcard}X={\rmcard}Y.\)证明：由条件得存在单射\(f\colonX\longrightarrowY\)和\(g\colonY\longrightarrowX.\)，取\(g\)的一个左逆\(h\colonX\longrightarrow

题目传送门luogu观看简要题意给两个序列\(S\)和\(T\)，输出的第一个数是它能改变的总个数，后面跟着的第\(i\)个是改变\(i\)个数之后，字典序最小的结果。思路当\(S\)与\(T\)相等的话，那就无法改变了，直接输出\(0\)。对于总数只要\(T_i\neS_i\)那它就可以改，所以只

/*325.计算机https://www.acwing.com/problem/content/description/327/一所学校前一段时间买了第一台计算机（所以这台计算机的ID是1）。近年来，学校又购买了N−1台新计算机。每台新计算机都与之前买进的计算机中的一台建立连接。现在请你求出第i台计算机到距离其最远

//503最长路径.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。///*http://oj.daimayuan.top/course/5/problem/226有一棵n个节点的树，节点编号从1到n。对于每个节点，请求出经过它的长度最长的简单路径有多长。定义一条路径的长度为这条路径上经过了多

树形dp一般的状态定义方式：f[u][j]：所有只在以u为根的子树中选，且总体积不超过j的选法的集合题目1：树的最长路径最长路径也就相当于树的最大直径给定一棵树，树中包含n个结点（编号1~n）和n−1条无向边，每条边都有一个权值。现在请你找到树中的一条最长路径。换句话说，要找到一

算法导论这个文档是学习“算法设计与分析”课程时做的笔记，文档中包含的内容包括课堂上的一些比较重要的知识、例题以及课后作业的题解。主要的参考资料是Introductiontoalgorithms-3rd(ThomasH.)（对应的中文版《算法导论第三版》），除了这本书，还有的参考资料就是Algorithmsdesi

 链接cf_Sakurako‘sHobby大意：给一堆点和边，并给出点的颜色，输出每个点能遍历到几个黑点思路：1、这些点边里面有拓扑结构，也有环2、先处理拓扑排序的一些点，依次遍历无父节点的即可，之后就会剩下环3、有环的说明每个点都能去到环内任意一点，那么直接就记录一个sum，然后递归

题意给定一张无向图，选取四个点\(a\neb\nec\ned\)，求\(f(a,b)+f(b,c)+f(c,d)\)的最大值，其中\(f(u,v)\)表示点\(u\)到点\(v\)的最短路长度。题解如果顺着枚举四个点\(a\)、\(b\)、\(c\)、\(d\)，是一个\(n^4\)的复杂度，显然过不了。但是我们发现如果确定

一、并查集学习一：1、寻找根节点（两种）intfind(intx){if(x!=city[x]) city[x]=find(city[x]);returncity[x];}intfind(intx){ returnfa[x]==x?x:fa[x]=find(fa[x]);}2、合并不同集合voidmerge(intx,inty){inta=find(x);intb

原题链接：https://www.luogu.com.cn/problem/P3509题意解读：n个点，每个点上有一只青蛙每次跳到距离自己第k近的点，m次之后跳到哪个点。解题思路：1、计算距离每个点第k近的点，存入ne[N]给定一个点i，距离i第k近的点一定在长度为k+1个点的窗口内，窗口包括i并且，第k近的点只能是左端点或者

题意第一行输入三个整数\(n,m,d(1\leqn\leq2*10^5,n\leqm\leq10^9,1\leqd\leqn)\)，第二行输入\(n\)个整数，保证每个数均不大于\(m\)。在每一天你都可以任意选择一个未选过的数\(a_i\)，随后可以继续选任意一个大于\(a_i+d\)的数\(a_j\)；接下来可以再选任意

目录题目描述输入格式输出格式数据范围输入样例输出样例思路解析 纯享版代码题目描述给定一个字符串S，以及一个模式串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串P在字符串S中多次作为子串出现。求出模式串P在字符串S中所有出现的位置的起

视频链接： P3629[APIO2010]巡逻-洛谷|计算机科学教育新生态(luogu.com.cn)//两次DFS+树形DPO(n)#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintN=100005;intidx=1,head[N],to[N<<1],ne[N<<1],w[N<

二分图二分图当且仅当图中没有奇数环.染色法//染色法模板intn;//n表示点数inth[N],e[M],ne[M],idx;//邻接表存储图intcolor[N];//表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色//参数：u表示当前节点，c表示当前点的颜色booldfs(intu

#include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefunsignedintuint;typedefvector<string>VS;typedefvector<int>

#include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefunsignedintuint;typedefvector<string>VS;typedefvector<int>

题目一 ​​​​Problem-2196大致意思就是求每个点为根的最大深度；对于这个问题，很快速的我们可以想到跑两次dfs，第一次预处理出以u为根的子树的第一，二深的深度，第二次dfs进行树形dp，从u->v时推出v的最大深度，用up[v]来存储；代码如下：注意分走到第一大和第二大的路径上的决策，以

AcWing826.单链表模板题：实现一个单链表，链表初始为空，支持三种操作：向链表头插入一个数；删除第k个插入的数后面的一个数；在第k个插入的数后插入一个数。现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。注意:题目中第k个插入的数并不是指当前链表

\(Question：\)给定一个模式串P和一个主串S,求模式串P在主串S中出现的位置(字符串下标均从1开始)\(Solution：\)模式串中next函数next[i]表示模式串P[1,i]中相等前后缀的最长长度运用双指针：i扫描模式串，j扫描前缀初始化ne[1]=0,i=2,j=0;ne[1]=0;

题目描述王老师脑袋一拍，定义了乘加运算！他定义 a∗bc=(a+b)×c 。而且他觉得用括号来规定运算的先后顺序太麻烦了，他给乘加运算定义了一个权值的系数（为乘加运算的下标），权值大的乘加运算先进行。例如下面的表达式：=====​9 ∗34​ 9 ∗12​ 1 ∗23​ 6 ∗41​ 29 ∗34

在此记录若干Trie好题。1.洛谷P3732[HAOI2017]供给侧改革点击查看题面给定一个长度为\(n\)的\(\texttt{01}\)字符串\(S\)。令\(\operatorname{data}(L,R)\)表示：在字符串\(S\)中，起始位置在\([L,R]\)之间的这些后缀之中，具有最长公共前缀的两个后缀的最长公

//164.可达性统计.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。///*https://www.acwing.com/problem/content/166/给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。输入格式第一行两个整数N,M，接下来M行每行两个整数x,

题目描述给定\(n\timesm\)的方格\(a[1..n][1..m]\)，每个格子有一个数。从\((1,1)\)出发走到\((n,m)\)一共不超过\(K\)次，只能往右往下走，走过的位置的数会变成\(0\)。问经过的位置的数字之和的最大值是多少。输入第一行包含一个正整数\(T(1\leqT\leq10)\)，表示测试数据的组数