可以发现一个性质：对于图的每个连通分量，一旦在其中任何顶点上的值固定，则所有写入的值都是确定的。我们可以逐个DFS每个连通分量，按照题目的要求给每个点赋值，初始搜索的点值设成\(0\)即可。代码：#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,m;

题目传送门前置知识动态树分治|动态开点线段树|标记永久化解法考虑动态点分治。两种操作本质上是将luoguP6329【模板】点分树|震波的操作互换了下，将原需支持单点修改、区间查询的数据结构换成需支持区间修改、单点查询的数据结构即可。区间修改、单点查询的动态开

数据结构栈栈，一种基本的先进后出的线性数据结构，手写栈一般有一个指针指向栈顶元素。STL中有个容器叫stack,支持一些功能push,将元素放置在栈顶；top(),输出栈顶元素pop()，弹出栈顶元素size(),访问栈中元素clear，清空详细操作可以见栈手写栈可以用数组模拟栈，代码如下。

B算法萌萌题。题解看到完全图求最小生成树，必然是要考虑一下B算法能不能做的。发现这个题的联通块最小值是可以维护的。我们发现。假如我们钦定\(i\)往前面连。那么前面的最小权值必然是一个固定的值。我们一定会连到\(\min(a_j-j\timesD)\)上。由于不能连到自己

MyBlogs[ARC083F]CollectingBalls建图，连边\((x_i,y_i+n)\)，这样会形成一个基环树森林。对于基环树的每条边，需要把他归到他连接的两个点中任意一个，并且每个点只能拥有一条边。对于每个基环树分别计算，树边归属的点一定是它两端深度较大的那个，环边归属点整体只有两种方式：顺时针

暑假集训CSP提高模拟25组题人：@KafuuChinocpp|@H_Kaguya\(T1\)P235.可持久化线段树\(0pts\)弱化版：SP11470TTM-Tothemoon标记永久化主席树板子。点击查看代码constllp=998244353;lla[100010];structPDS_SMT{ llroot[100010],rt_sum; structSegme

[SNCPC2024]换座位题目描述树王国在筹备着举办一次盛大的庆典！Shirost作为树王国的庆典设计师，准备邀请\(n\)个嘉宾来参加本次庆典。庆典上一共准备了\(2n\)个座位，一个座位最多只能坐一个人且一个人恰好坐一个座位。Shirost初步计划将第\(i\)个嘉宾安排在第\(i\)个座

题目传送门前置知识树的直径|最近公共祖先|并查集解法一个显而易见的结论：设点集\(A\)的直径的两个端点为\(u_{1},v_{1}\)，另一个点集\(B\)的直径的两个端点为\(u_{2},v_{2}\)，则\(A\bigcupB\)的直径端点一定是\(\{u_{1},v_{1},u_{2},v_{2}\}\)中的两个。还有

题目传送门前置知识树链剖分|树的直径|最近公共祖先|并查集解法正着删边不太可做，考虑离线下来反着加边。一个显而易见的结论：设点集\(A\)的直径的两个端点为\(u_{1},v_{1}\)，另一个点集\(B\)的直径的两个端点为\(u_{2},v_{2}\)，则\(A\bigcupB\)的直径端点一定是

暑假集训CSP提高模拟20组题人：@KafuuChinocpp\(T1\)191.Kanon\(0pts\)原题：luoguP7405[JOI2021Final]雪玉|雪玉(Snowball)\(T2\)P154.SummerPockets\(0pts\)原题：[ARC157D]YYGarden\(T3\)199.空之境界\(60pts\)原题：QOJ1833.Deleting部分分

题目传送门前置知识线段树|树链剖分解法观察到要维护树上信息，且更改的呈链状，考虑进行树链剖分。将边权转化成点权，钦定边权给了深度更深的那个点，注意更新时不能更新\(\operatorname{LCA}\)。区间赋值和单点查询用线段树维护即可。代码#include<bits/stdc++.h>usingnam

暑假集训CSP提高模拟16组题人：@Muel_imj\(T1\)P216.九次九日九重色\(100pts\)部分分\(30pts\)：设\(f_{i,j}\)表示当前处理到\(P\)的第\(i\)位，\(Q\)的第\(j\)位时最大的\(k\)，状态转移方程为\(f_{i,j}=\begin{cases}\max(f_{i,j-1},f_{i-1,j})&p_{i}\nmid

暑假集训CSP提高模拟15组题人：@LYinMX\(T1\)P213.串串\(15pts\)原题：luoguP5446[THUPC2018]绿绿和串串部分分\(15pts\)：当\(|S|=1\)时输出\(1\)，否则顺序输出\([2,|S|]\)。正解由题，有\(R\)一定是\(S\)的前缀。赛时在这里被绕进去，一直在想怎么证

前言题目链接：Hydro&bzoj。题意简述无向联通图给出起点终点，多次询问删边后最短路，或报告不连通。\(n,m,q\leq2\times10^5\)。题目分析首先想到，如果删掉的边不是原来最短路的边，那么最短路不会发生变化。因此我们只需考虑删除了原来在最短路上的边。不妨把原先最短路任

算法竞赛（差分）（上午）初始化#include<algorithm>intarr[100];std::fill(arr,arr+100,0);//比memset更高效intarr[100]={};//所有元素都初始化为0栈溢出为局部变量每次运行时都在运行栈中分配，如果数组很大，结果会造成运行栈溢出，自然就运行不了另外，使用全局变

暑假集训加赛1P145修仙（restart）题目中的可以指恰好。考虑计算双休带来的差值。令\(b_{i}=a_{i}+a_{i+1}-\max(a_{i}+a_{i+1},0)\)，则需要计算从\([1,n)\)中选出\(k\)个不相邻的\(b_{i}\)的最大价值，同luoguP1484种树|luoguP1792[国家集训队]种树|

暑假集训CSP提高模拟2\(T1\)T2745.活动投票\(30pts\)原题：luoguP2397yyylovesMathsVI(mode)懒得再复制一遍了，直接挂当时的题解得了。点击查看代码intmain(){lln,a,sum=0,ans=-0x7f7f7f7f,i;scanf("%lld",&n);for(i=1;i<=n;i++){

思路通过读题发现，每个数变化当且仅当这个数在集合内。所以不妨设它被添加进来的时间点为\(L_i\)，它被删除的时间点为\(R_i\)，所以它被增加的数量就是这段时间内集合数量之和。所以用一个变量\(cnt\)模拟当前集合内有多少个数，前缀和维护即可。具体实现参见代码。代码#include<

题意在长为\(n\)的序列\(a\)中找出\(k\)个数，设它们的下表为$p_1\(，\)p_2$到\(p_k\)，满足这\(k\)个数从小到大排列过后是一个公差为\(1\)的等差数列。求满足条件的\(k\)个数的最大的\(p\)减去最小的\(p\)最小。输出这个值。思路把数组\(a\)排一遍序，滑动窗

题目链接CF1454FArrayPartition解题思路我们发现显然第一个和第三个区间的值区间随着长度的增大而增大。于是我们就可以枚举第一个区间的右端点位置，然后现在问题就转化成了找到一个断点来确定第二，三个区间的长度，由于前文提到的第三个区间的值区间随着长度的增大而增大，于是我

哎哎哎，原来的题解没怎么写证明被叉了/yun所以我来补下证明。题目链接P10678『STA-R6』月解题思路时间复杂度优于官解的做法。首先我们观察到一个性质就是\(\suma_i=2\times(n-1)\)，因为一个树有\(n-1\)条边。注意到一棵树必定有叶子结点。于是我们每次给树

MyBlogsP10542[THUPC2024]RPG一个有配合的“状态加攻击”一定是一个连续段，段内都在摸鱼。所以设\(f_i\)表示考虑了前\(i\)个人的最大收益：\[f_i=\begin{cases}f_{i-1}+d_{b_i}\\\max_{(x,y,z)\in\mathbb{E},y=b_i}g_x+z+d_{b_i}\end{cases}\]其中\(g_i\)表示满足

题目传送门前置知识树链剖分|线段树解法树剖换根，子树查询板子。类似换根DP的思路，我们发现换根后仅有祖先、子树、深度等会随祖先的变化而变化。设\(rt_{i}\)表示第\(i\)次操作的树根，\(x_{i}\)表示第\(i\)次操作的节点。接着进行大力分讨。当\(rt_{i}=x_{i}\)

链接很一眼。容易发现除非操作时影响\(1\)这个数字，否则答案一定改变，直接特判影响到\(1\)这个数字的两种情况即可。代码：点击查看代码/*Tips:你数组开小了吗？你MLE了吗？你觉得是贪心，是不是该想想dp？一个小时没调出来，是不是该考虑换题？*/#include<bits/stdc++.h>using

想起上次的ABC346没打，刚才虚拟参赛打了A~D，E题思路有，但是实现方式没选好导致WA了，没能在赛时做出来。写下题解记录一下~C-Σ用求和公式先把\(1\simk\)的和求出来：\(\frac{k(k+1)}{2}\)，然后对于\(A\)数组中的元素依次减去就行（注意相同元素不能减\(2\)次）点击查看代码#include<b