字符串构造机100pts原题，见[赛记]多校A层冲刺NOIP2024模拟赛01【衡中】T1；忍者小队60pts赛时最后想出来个$\Theta(n^2\logn)$的DP，所以60pts；对于这个DP，直接用map维护一下所有lcm的状态转移即可；点击查看代码#include<iostream>#include<cstdio>#include<vect

图论【LuoguP8428】Pastiri题目描述给定一棵\(N\)点的树，点编号为\(1\)到\(N\)，现在在\(K\)个点上有羊，你的任务是在树上分配一些牧羊人。这些牧羊人很懒，只会看管离他最近的羊。当然如果有多个离他最近的羊，那么他会都看管。当然，牧羊人可以和羊在同一个点上，但这样牧羊

排列最小生成树(pmst)50pts又是诈骗题，然后又不会。。。暴力很暴力，直接建个完全图跑Kruskal即可；正解考虑如果我们连接编号相邻的点，那么每个边的边权都小于$n$真能考虑到吗？；所以我们最终的最小生成树中的边边权都小于$n$；那么对于$|p_i-p_j|\times|i-j|<n$

椒过#include<bits/stdc++.h>usingnamespacestd;intn,m,tot,lnk[505],ter[500005],nxt[500005],st[500005],ed[500005],deg[505];doublea[505][505],b[505],x[505],f[500005];voidadd(intu,intv){ ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot;}voidGauss(

median50pts错解50pts（有重复的数就不行）；赛时想容斥了，其实不用容斥（好像也不能容斥）；题解做法：将每个数存一个二元组，按大小排序，枚举每一个数作为中位数，再枚举每个位置的种类，看它前面和后面有多少这些种类的数，乘起来即可；这样就巧妙地避免了重复的情况，如果直接枚举，则有相同的数会被重

高效高效，坚持高效，耶(•̀ω•́)y首先，我们考虑引爆每个炸弹，它能引爆的区间是多少（即：它能对答案做出什么贡献）易得炸一个=炸这个区间为什么？你只要引爆了一个大炸弹（例如沙皇）它就会把它的左边和右边一起抬走所以考虑线性维护每个炸弹向左/向右能炸到哪里代码十分精华：#inclu

     ~~~~~     P8436【模板】边双连通分量     ~~~~~

Kanon40pts签到题，但是不会，所以打了暴力；正解时考虑相邻两个雪球，只有两种情况：它们的覆盖区间有交集或无交集，那么如果我们找出了无交集的最后一天，我们就很容易判断剩下的一堆雪该被谁拿走，于是我们二分找出这一天即可；赛时确实想不到二分时间复杂度：$\Theta(n\logn)$；点击查看

$Peppa\Pig$都有时间写赛记了，看来现在这题是真不好改了今天又是一题没切；九次九日九重色0pts原题：现找的赛时理解错了子序列，给理解成了字串（$HDK$给我说的，要不我可能还不知道），导致大样例咋手模都出不来，干了45min，整了个不像暴力的暴力然后走了；赛后证明，我的乱胡搞到了$

普通分治其实没啥，每次只计算跨越分治中心的区间的贡献，剩下的递归到左右两边进行分治；时间复杂度：分治树高度为$\Theta(\logn)$，乘上其他操作的复杂度即可；例题一：现在有一个$n$阶排列$a$，计算：\[\sum^{n}_{i=1}\sum^{n}_{j=i}\min(a_i,a_{i+1},...,a_j)\]

二维数点问题我们通过扫描线可以将静态的二维问题转换为动态的一维问题维护动态的一维问题就使用数据结构维护序列点击查看代码#include<bits/stdc++.h>usingnamespacestd;structt1{ intx,y;}t[500005];structq1{ intx1,y1,x2,y2;}q[500005];structl1{

花30分钟发现lg翻译出错了又花30分钟学习欧拉回路怎么求再花30分钟等待codeforces的queue#include<bits/stdc++.h>usingnamespacestd;intt,n,m;vector<int>res;structedge{ intv,w,nx;}e[1000005];intcnt,hd[500005],deg[500005],sum[500005];voidadd(intu,in

子树余树的信息可以通过全局信息减去子树信息来统计在最后一刻，其实你已经意识到，问题大概出在((g[fa][0]-f[n1][0])+n-sum-cnt[n1][0])这个式子上但你最终没能找出错误，因为你只关注到式子的逻辑有没有问题，而没有意识到变量对式子的诠释是否恰当——你需要的其实是O节点的个数，但

https://www.luogu.com.cn/problem/U285997#submit题目描述星斗大森林里有一棵参天巨树，树上有 nn 个结点，我们给它们编号 11~nn。松鼠每天从树的这头窜到那头，因为它不认真写信息学作业只想划树叶子（树上没办法划水啊），被妈妈给批评了，于是回不了家。现在松鼠想要知道，它从

原题链接题解注意数据范围1.我们不知道要在哪些地方建站，所以考虑都遍历一遍2.如果一个地方\(i\)要建站，那么在它前面且离它最近的一个站，一定建在所有右端点大于\(i\)的区间中，左端点最大区间里所以我们令\(dp[i]\)表示为在\(i\)建立一个站，且和\([1,i]\)有交集的区间

没有push_down调了15分钟，然后在赛后7分钟过的，中间看到E是期望题就去打舟了，哎，再也不摆了（期望能不能别再出现了）翻转?这我熟，fhq啊!然后大写变小写?简单，再lazytag搞一下就好了。时间复杂度\(O(n\logn)\)，带一个大常数，但是绰绰有余。#include<bits/stdc++.h>#definefor1

刚学字符串，随便打打Hash基础题就打到了这道，然后阴差阳错入坑Manacher算法，再也回不过头了。这道题让你求反对称子串个数，就是在亦或意义下的回文子串，于是毅然决然选择了放弃在\(O(n)\)的马拉车（最后补回来了），所以两个做法都写写吧。Hash这道题让你求回文串的数量，考虑如何判定

原题链接题解本质：求一个数前面有几个数大于它，我们把序列分成几段，然后对每段分别进行排序，然后找出这个数在前面已经排好序中的序列里有几个大于它code#include<bits/stdc++.h>usingnamespacestd;#definelllonglonglla[500005],b[500005],c[500005];//a-original

原题链接题解1.设\(f(i)\)为\([0,i]\)区间内该有多少个数属于整数集\(Z\)则对于每一对输入的\(x,y,c\)都有\(f[y]-f[x-1]>=c\)而且\(0<=f[i]-f[i-1]<=1\)差分约束由此得来又因为下标从零开始，而且我们需要建立超级源点，所以我们把\(f\)内的下标整体往右移两位co

原题链接题解拓扑排序，层级标记，如果层级等于n，代表层次分明code#include<bits/stdc++.h>usingnamespacestd;vector<int>G[500005];intin[500005]={0};structnode{intid,layer;};intmain(){intn,m;cin>>n>>m;for(inti=1;i<=m;i++)

维护子树的全部子树的权值和时，需要用到树的DFS序列，树的每个子树都对应DFS序列中的连续一段黄金树影题意：给定一棵树及每个节点的权值，给定一组操作，输入1ax，表示节点a权值加上x；输入2a，表示询问节点a的子树权值和（包含a）。考虑到树的DFS序列，则问题转变为对某个序列维护区间和以

原题链接题解和点双连通分量不同在于点双联通分量：分量内任意两点之间至少有两条独立路径可走，两条路径所经过的点除了起点和终点都不同边双连通分量：分量内任意两点之间至少有两条独立路径可走，两条路径所经过的边都不同（包括重边）用这个图依然可以解释code#include<bits/stdc++

单向边森林不能通过dfs找环抽象的题目需要通过模拟样例理解题意列表模拟样例链式前向星双倍空间（边&边的访问函数）*点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintmod=1000000007;longlonga[500005],b[500005],w[500005],c[500005],p[500005],cn

点击查看代码#include<bits/stdc++.h>usingnamespacestd;intha[50005],res[100005],ans[100005];ints[500005],id[500005],tot,f[100005],l[100005],u[500005],o[100005];intrk[20][500005],r[500005],sa[500005],h[500005],w,p[25];intL[100005],R[100005];int

容斥原理将两个字符串拼接起来（中间用‘#’分隔开），再减去它们内部的贡献height数组支持的最长公共前缀：不仅是长度，也是子串的个数返回值开longlong核心代码与[AHOI2013]差异一致点击查看代码#include<bits/stdc++.h>usingnamespacestd;intsa[500005];intrk[20][5