String题面：给定两个字符串\(a\),\(b\),我们称这两个字符串的所有子序列为坏字符串。求最短的非坏字符串。做法：首先要解决一个问题，假设你有一个字符串你需要判断这个字符串是否是坏的，怎么快速判断？我们预处理出nxta[i][j]表示\(a\)字符串中第\(i\)个位置之后第一个\(

Portal：https://www.luogu.com.cn/contest/179008\(\bf{100+50+50+25+5=\color{indianred}225\color{black}\,\rk.\184}\)A-StrangeCakeGame显然对于小W，向下移动蛋糕刀是最有利的；对于小M，向右移动是最有利的。所以双方以最佳状态移动，最终\(x\ley\)的巧克力是小W的。直接

题目链接点击打开链接题目解法我真菜啊，感觉每一步都不难，但一步都没想到/yun考虑两行\(x,y\)什么时候可以构造出合法的矩形？即\(x\)中需要有\(y\)对应位置为\(0\)的\(1\)，\(y\)中需要有\(x\)对应位置为\(0\)的\(1\)归纳一下，\(x\)不是\(y\)的子集且\(y\)不

字符串KMPconstintN=1e6+5;intn,m;intnxt[N];//t串前缀的border长度chars[N],t[N];intmain(){scanf("%s%s",s+1,t+1);n=strlen(s+1);m=strlen(t+1);for(inti=2;i<=m;i++){intj=nxt[i-

得用kunkka号看。题解A.网瘾少年很好很好的贪心题。弱化版是[CSP-J2023]公路，这题没有油箱限制。首先判掉无解：存在\(d_i>T\)。用单调栈求\(nxt_i\)表示\(i\)之后第一个油价比\(i\)低的位置，没有为\(n+1\)（终点）。因为\(nxt_i\)的油价比\(i\)低，所以你肯定

A结论题，行着取intn,m;signedmain(void){#ifdefONLINE_JUDGEfreopen("alter.in","r",stdin);freopen("alter.out","w",stdout);#endif read(n),read(m); writeln(n/2+m/2); for(inti=2;i<=n;i

T1一般图最小匹配点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=5000+107;intn,m,a[N];intread(){ intf=1,s=0;charch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=ge

关于这道题目卡\(O(n\logn)\)但是放\(O(n^2)\)我也是很疑惑。我们发现，题目要求的是字典序最小的序列。但凡涉及了字典序最小，答案或多或少的都会带点贪心思想。那我们也来贪一贪。考虑当前枚举到第\(i\)个点，如果后面有比它更小的数，那显然把它们交换过来是更优的。如果有多

机器人搬重物题目描述机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径\(1.6\)米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个\(N\timesM\)的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时

[NOIP2017普及组]棋盘题目背景NOIP2017普及组T3题目描述有一个\(m\timesm\)的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的），你只能向上、下、左、右

Statement维护一棵树，边权\(\in\{\texttta,\textttb,\textttc\}\)，根为\(1\)，定义这棵树的子串为从\(1\)走到所有点构成的字符串的所有后缀，需要支持以下操作：问当前树的本质不同子串数给一个点添加一棵子树问一个串在当前树中作为子串的出现次数Solution直接广义SAM+

前置知识在了解图论之前，还需要知道怎么存图。vector用vector<int>G[MAXN]来存图。$G_i$表示从$i$出发，能够到达的点的数组。空间开销相较于链式前向星较大。也可以将vector替换为其他STL容器，如list、unordered_set、deque等。list的写法空间更优，常数较小，但是vecto

先开个坑，不一定填。主要记录一些口胡了但是没写的题。String题面：给定两个字符串\(a\),\(b\),我们称这两个字符串的所有子序列为坏字符串。求最短的非坏字符串。做法：首先要解决一个问题，假设你有一个字符串你需要判断这个字符串是否是坏的，怎么快速判断？我们预处理出nxta[i

链表可以\(O(1)\)插入/删除单向链表顾名思义只有后继指针邻接表我习惯叫做链式前向星,一般用来存储图,挺好理解的,这里直接给出存图的应用structedge{intto,nxt;}eg[M];inthead[N],egtot;voidadd(intu,intv){eg[++egtot].to=v;eg[eg

Asignedmain(){intl,r;cin>>l>>r;if(!(l==1&&r==1||l!=1&&r!=1)){if(l==1)cout<<"Yes\n";elsecout<<"No\n";}elsecout<<"Invalid\n";}Bsig

T1文本编辑器说实话，看到题目的第一瞬间，我还以为gm第一道就放了平衡树。一道链表的模板题，当然愿意也可以用平衡树写，不多说了，直接放代码(100pts)：#defineN1000005chars[N],t[N];intnow,pre[N],nxt[N];intmain(){scanf("%s%s",s+1,t+1);intn=strlen(s+1);

学习笔记我认为我这个算法可能无法讲明白，而且工作量巨大，所以为了让你快速学会我推荐学习下列笔记。学习笔记1学习笔记2学习笔记3例题感觉经过上述的学习，你一定有所收获吧（如果没有的话还是菜就多练吧），所以接下来我会举出一些题目，应该会对你的学习有些帮助。1.【模板】KMP（洛谷

0828-T3天气预报题意有\(4\times4\)的村庄，有一朵\(2\times2\)的云，需要控制云上下左右移动，保证每个村庄都不会连续\(7\)天以上不下雨，也不会在不能下雨的时间下雨。问是否可以做到。思路搜索。需要注意的是打标记时只用记录时间，云的位置，四个角落的村庄连续未下雨的天

主要思路：网络流。思路先考虑最小生成树，如果一条边边权大于等于选中的边，那么这条边是否删去没有任何影响。按边权排序，对于边\((u,v,L)\)，若要加上当且仅当\(u\)和\(v\)并不联通。把所有边权比选定的边的边权小的边拿出来连上，流量均为\(1\)，最小割。最大树同理，连上边权比选

简单版题目描述给定\(n\)个模式串\(s_i\)和一个文本串\(t\)，求有多少个不同的模式串在文本串里出现过。两个模式串不同当且仅当他们编号不同。思路我们可以将所有模式串存进\(trie\)树中，像这样：此时如果我们朴素地查找，那显然会超时，因此我们可以使用类似\(KMP\)算法

1.前言链表：不仅存储 当前元素的数据，还存储着 元素排列顺序2. 正题2.1如何存储节点？我们可以使用结构体 数组来存储 链表节点structNode{intval;//可以是string或其它复杂的类型intnxt;}node[N];Tip:下标顺序不是单链表顺序 val代表 元

逆天贪心设对于一个点\(x\)花费\(d\)步能走到的最左边为\(L_{x,d}\)，最右边为\(R_{x,d}\)。主要证明一个东西：若\((a,b)\)这个询问中区间\([L_{a,x},R_{a,x}]\)与\([L_{b,y},R_{b,y}]\)有交，那么必然存在一条步数为\(x+y\)的路径。证明：分类讨论当\(val_{R_{a,x

思路：双向链表+组合数学（不过你要用单调栈也没人拦着你）我们现在先抛开题面，先换个思路。我们现在求：这个数能做多少个区间的次大值。我们现在设\(l1,l2,r1,r2\)分别为左边第一个比这个数大的id，第二个比这个数大的id，右边第一个比这个数大的id，第二个比这个数大的id。竟然是

树论LCTclassC_LinkCutTree{public: intrev[N],fa[N],ch[N][2]; /*====================*/ boolWhich(intx) { returnch[fa[x]][1]==x; } boolIsRoot(intx) { returnch[fa[x]][Which(x)]!=x; } /*====================*/ voidPushUp(intx) {

KMP(Knuth-Morris-Pratt)用途：用于一个文本串S内查找一个模式串P的出现位置，以及求一个字符串的最小循环元长度和最大循环次数。思路：\(kmp\)是对原始的在文本串S内查找一个模式串P的出现位置的一种优化。原始做法将\(s\)的每一位都与\(p\)的第一位开始匹配。(匹配到\(s\)的