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

点击查看代码#include<bits/stdc++.h>usingnamespacestd;intsa[500005];intrk[20][500005],w,p[25],r[500005],h[500005];stack<int>s1;stack<int>s2;longlongn;structt1{ charc; intid;}t[500005];boolcmp1(t1a,t1b){ returna.c&l

https://www.luogu.com.cn/problem/B3691?contestId=154692`include<bits/stdc++.h>usingnamespacestd;intn,m;inta[500005],b[500005],c[5000005],d[5000005];intmain(){cin>>n>>m;for(inti=1;i<=n;++i){scanf("%d&q

P9868[NOIP2023]词典（民间）直接把每个串\(w_i\)都从大到小/从小到大排一下，记作\(a_i,b_i\)。如果\(b_i\)小于除了\(i\)之外的所有\(a_i\)，说明可以，否则不行。求一个前后缀最大值即可。复杂度\(\mathcal{O}(26n+nm)\)。点击查看代码#include<bits/stdc++.h>usingname

「KDOI-06-S」A.「KDOI-06-S」消除序列赛时写了一个\(O(nq)\)的线性DP，喜提60分。注意到如果操作1被使用，则一定只会使用一次，而且在最优策略中一定是第一次使用操作1。则我们可以通过以下方式进行操作，使序列满足条件：首先执行\(a_i\)和\(\sum^{j\lei,i\inP}_{j=

归并排序的模板。能求逆序。。。。#include<stdio.h>#include<string.h>intn;longlonga[500005],b[500005];longlongsum;voidmerge(intl,intm,intr){ inti=l,j=m+1,k=0; while(i<=m&&j<=r) { if(a[i]<=a[j]) b[k++]=a[i++]; else

思路发现此题除了模拟没有好的方法，所以考虑如何模拟。先考虑删除操作，如果在删除的时候再去找要删除那些的话，就会使时间复杂度变高，所以考虑先预处理出每个括号对应的位置。如果按照操作删除括号，那么时间复杂度也是非常吓人的。所以我们考虑标记被删除的括号。再考虑移动操作，如果

Non-Puzzle:SegmentPair时间限制(普通/Java):2000MS/4000MS内存限制:262144KByte描述输入输出样例输入3146725351357样例输出2思路枚举区间左端点x，则要满足区间的交包含x，并且不包含x−1。考虑计算包含x的方案数，则每对区间的贡献

题目链接题意是输出所有区间满足其内部每个数要么出现$3$次要么不出现的个数。因为是区间，数量很多，发现贡献是可以抵消的，直接无脑预处理前缀的桶。然后枚举左端点，统计答案，怎么处理呢？疯狂地向右扩展，直到区间内有数字出现了$3$次以上（这样是对的，待会儿证明，另外扩展到前一个就

T1：金盏花传送门直接暴力枚举前6位的值即可，记得开longlong#include<bits/stdc++.h>usingnamespacestd;#defineintlonglonginty,z,ans=1e18;signedmain(){ scanf("%lld%lld",&y,&z); for(inti=100000;i<=999999;i++){ intx=i*1000000+y; ans=min

P1020[NOIP1999普及组]导弹拦截思考这题很显然是一道DP题，第一问就是求该序列的最长不下降子序列.先说最长不下降子序列的\(O(n^2)\)的做法.用\(dp_k\)表示第\(k\)

#include<iostream>#include<algorithm>#include<cstdio>usingnamespacestd;inta[500005],b[500005],n;intmain(){scanf("%d",&n);for(inti=1;i

所以说，我又来贴标程了。这题有很多做法，线段树，优先队列$and$删除等等，这里分享一种码量极少的二分做法，主要思路：二分+动归#include<bits/stdc++.h>usingnamespacestd;

求\(n\)个点的树上对于每个点距离小于\(k\)的点的数量（边权均为\(1\)）。\(n\leq5\times10^5，k\leq10\)。设\(f[u][i]\)表示距离\(u\)点\(i\)距离以内并且