题意给定一颗树，每个点有权值\(1\)和\(-1\)，称一条路径是好的当且仅当路径上所有点的权值和为\(0\)。求连续编号区间\([l,r]\)使得两个点都在\([l,r]\)的好路径比两个点都不在\([l,r]\)的好路径数严格多的方案数。\(n\le10^5\)。Sol两个端点都在区间内不好做，

T1题目描述今天的酒席有\(n\)个人，他们要同时举杯，成对碰杯。碰杯的时候，不能有人不参与碰杯，也不希望有手臂交叉这种别扭的情况出现。如下图，左图的情况是好的，右图的情况是不希望出现的。每个人都有一个喜爱的酒种类，每个人想要与和自己喝一样酒的人碰杯，请你设计一个方法，在保证每

为了使得整篇文章显得更加人性化，咱们首先说一下最短路。声明：不是讲解知识点不是讲解知识点不是讲解知识点不是讲解知识点不是讲解知识点，整篇文章建立在默认已经会的基础之上，然后提出一些个人见解。最短路此时的SPFA显得不再重要了（，咱们进入正题，说一下dijkstra。（堆优化的）迪杰

传送门题意时限6s,给你一颗\(n\leq1e6\)的树，输出所有的\(i\)，使得该树可以删除某\(i\)条边,使得删除后所有的连通块大小相等题解虽然有结论,但还是讲讲我的做法把,或许有所启发考虑将枚举删除边数转换为枚举连通块大小,不妨设每个连通块大小为\(k\)每次从树上删除一个

题意给定一个\(0/1\)字符串，你需要从中选出尽可能多的不相交的子串使得按顺序字典序单调递增。\(n\le25000\)。Sol先考虑能最多选出多少个不相交的子串，这个是\(\frac{n}{\logn}\)，但是这个没用。考察一下子串的长度，由于字典序的限制，最劣的情况下就是一个子串比上一个子串

题意你需要维护一个可重集\(S\)，支持插入删除以及查询最大的方案使得给定正整数\(k\)，划分为\(k\)个非空子集的按位与结果之和最大。\(n\le10^5\)Sol先上个trie。然后考虑一次查询怎么搞。先转化一下，如果需要划分为\(k\)个子集，显然需要合并\(n-k\)次。我们只

之前就是史，重新来写，字符串还是有必要学的。KMP用于文本串匹配。其和暴力的区别在于失配后会从一个特定位置重新开始匹配而不是从头开始，从而节约时间。这个失配数组也就是\(nex_i\)表示\(S[\mathbf{1}\dotsi]\)的最长\(\mathtt{border}\)长度，建出来之后相当于一个自动机

题目链接：没有上司的舞会思路题解#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintN=1e5+10;intdp[N][2],happy[N],subordinate[N],cnt,head[N],nex[N],edge[N];//链式向前星存储边voidadd(intx,inty){nex[++cnt]=

`moduletop_module(inputclk,inputx,outputz);reg[2:0]s_cur;reg[2:0]s_nex;//传递状态always@(posedgeclk)begins_cur<=s_nex;end//确定下一状态always@()begincase(s_cur)3'b000:case(x)0:s_nex=3'b100;1:s_nex=3'b111;endcase3�

本质最多有二十六个节点的树（假设只看小写英文字母）。空间换时间nex[p]是一个节点，根据c的取值最多有26个分支，nex[p][c]存的是下一个节点有意思的情况：为什么Trie的树用数组实现，二叉树用指针实现：当创建和使用Trie树时，以下是一般的步骤和操作：创建Trie树的节点结构：通常使用一个

先放着点击查看代码 nxt[0]=-1; intj=0; for(inti=2;i<=len2;i++) { while(j&&s2[j+1]!=s2[i])j=nxt[j]; if(s2[j+1]==s2[i])j=j+1; nxt[i]=j; }//自己匹配 j=0; for(inti=1;i<=len1;i++) { stk[++top]=i; while(j&&s2[j+1]!=s1[i])j=nx

题目：链接：https://www.luogu.com.cn/problem/P8625基本思路：1.使用dp[N]记录i节点的当前最大值2.使用vectornex[N]记录图3.使用vis[N]防回退如果该节点没有子节点，那么这个点的最大值就记录为当前的值：val如果该节点有子节点，那么先遍历子节点，然后+res并记录由于使用了vis，那么

一、题目描述P8715[蓝桥杯2020省AB2]子串分值二、问题简析记录字符串\(s\)的第\(i\)个字符\(s_i\)（\(0\leqi<s.size\)）上一次出现的位置\(pre_i\)、下一次出现的位置\(nex_i\)，仅包含\(s_i\)的字串个数为\((i-(pre_i+1)+1)*(nex_i-1-i+1)\)，即\((i

写点简单的思维题https://codeforces.com/problemset/problem/1927/D思路：用两个数组，一个存储原始数据，一个用nex存该位置第一次不一样的下标#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<sstream>#include<string>#include<str

题意给定一棵树，以及\(m\)条路径。让你选出最少的点，使得对于每一条路径，都有一个点距离链上的点离端点更近。Sol考虑将每一条路径分为直链和曲链考虑。注意到所有的曲链最多对答案有\(1\)的贡献。考虑直链的情况。注意到一个很显然的东西。对于一个选择的点，如果她的上方

那个求p串的next数组这个版本是下标从1开始的字符串，如果从0开始的话，可以在前面加空字符，然后p.size或者s.size的地方-1即可。nex[1]=0    for(inti=2,j=0;i<=p.size();i++){if(j&&p[i]!=p[j+1])j=nex[j];if(p[i]==p[j+1])j++;nex[i]=j;} kmp函数

#include<bits/stdc++.h>usingnamespacestd;structtrie{intn;vector<array<int,26>>trans;vector<int>cnt;trie():n(0){new_node();}intnew_node(){trans.push_back({});trans.back()

这道题只要求输入最小步数即可，而且数据的个数较大，所以优先采用BFS（广度优先搜索）：广度优先搜索，即以数据搜索的广度优先，换句话说就是每一次操作都将所有可能的结果存储下来，随后对数据进行下一步处理，注意是对每组数据都只进行一次处理，如果是一条路走到头，这就变成了深度优先搜索（DFS）。而基

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e3+10,inf=0x3f3f3f3f;intnex[N];//nex[j]的意思是当子串的第j个字符和主串的第i个字符不匹配时，我们应该从子串的nex[j]字符开始重新匹配stringa,b;/*kmp指针回退j=nex[j-1]

数据结构——字典树学习笔记字典树，也叫trie树。检索字符串本质是记录字符串前缀的一棵查找树，形态类似于：字典树使用边表示字母，节点表示一个前缀，同时也可以在节点上记录状态\(\mathit{tag}\)。基本实现形如：var: nex[0..siz][0..rng],idx est[0..siz],pre[0..siz]fun

最短路专题由于最短路的内容有点多，所以从代码模板中提取出来单独做一个专题，后期有需要把字符串也单独整理一下。Dijkstra(迪杰斯特拉)每次选取一个据起点最近的点，尝试更新与它相连的所有点。在补充一下Dijkstra不能求负权边的原因，因为其根本逻辑是确定当前点已经是离原点最

题意给定一棵树，每次操作将一个点染成黑色。求询问的点到所有黑点的路径编号最小值。**数据保证第一次为染色操作**Sol注意到保证第一次为染色。考虑钦定根节点为染色的点。那么对于所有染色操作，暴力记录染色的点到根节点的路径上所有点的贡献。每个点只会贡献一次，这部分

忘了具体什么时候写的，应该是2023.8初这算是个算法复习，因为我太菜了以前学的都不会了。KMP字符匹配有一说一这个我讲不来，大概意思就列这好了：Knuth(D.E.Knuth)&Morris(J.H.Morris)&Pratt(V.R.Pratt)提出的字符串匹配算法，简称KMP。KMP算法应该是最基础的字符串匹配算法了，

创建节点类publicclassNode{intn;Nodenext;}第1次推导publicclasstest{publicstaticvoidmain(String[]args){//新建节点Nodenode1=newNode();node1.n=2;Nodenode2=newNode();node

创建节点类publicclassNode{intn;Nodenext;}第1次推导publicclasstest{publicstaticvoidmain(String[]args){//新建节点Nodenode1=newNode();node1.n=9;Nodenode2=newNode();no