$Description$

给$n$个数，求数字和前$k$大的区间的和

$Description$

你要从$A$到$B$，需要走$n$步。若你已走了$s$步，那么你再走一步的代价将为$a[s+1]$。

在走完每一步后有$\frac{1}{2}$的概率休息，休息后$s$将变为$0$。

求出你从$A$到$B$的代价的期望$p$乘上$2^{n-1}$对$998244353$取模的结果。

$Description$

把一棵树分成几块，使得每个块中的点数都相同，问有多少种块的大小能满足该条件

$Description$

对一张$n$个点的图做$Q$次加边操作,每次给定$A_i,B_i,C_i,$然后按顺序连边$(A_i,B_i,C_i),(B_i,A_i+1,C_i+1),(A_i+1,B_i+1,C_i+2)$等等，求给定图的最小生成树$.(A_i,B_i,C_i$等点编号均为对$n$取模的意义下$)$给定初始的$n,q,A_i,B_i,C_i;$

$(N,Q\leqslant 200000,0\leqslant A_i,B_i<N,1\leqslant C_i\leqslant 10^9)$

$T1$

对于$20\%$的数据，状压暴力

对于$50\%$的数据，网络流,但是出题人没写过

对于$100\%$的数据

转换成图论问题，对物质和变换规则建点，对于一种变换规则，需要$L$种物质，缺一不可，类似于拓扑排序的感觉，而在一种变换规则成立后，它又会带来$R$种物质，类似于$bfs$的感觉，所以不能只用$bfs$或拓扑排序，所以，只需要两个一起用就行了极其无脑

$T2$

看到二叉搜索树，应该很容易想到对树进行中序遍历。这样问题就变成了对一个序列$A_i,$修改数量最少的元素，使得这个数列严格递增

对于$30\%$的数据$,2^n$枚举那些点改变，然后贪心

对于$50\%$的数据,给求最长不下降子序列只会$O(n^2)$的选手准备的，即正解中的求最长不下降子序列$O(nlogn)$改成$O(n^2)$.

对于$100\%$的数据

一个比较$naive$的想法就是对这个序列求最长上升子序列$x,$然后$n-x$即是答案。

这显然是错误的

然后我们考虑一个奇技淫巧,将每个$A_i-$$=i,$然后求最长不下降子序列

举个栗子$:2\;\; 9\;\;3\;\;9\;\;4\;\;8\;\;5,$按照上面的做法得出的最长上升子序列为$2~3~4~5$或$2~3~4~8$,得出的修改次数为$3,$但是显然答案为$5.$

而我们修改后的序列为$1\;\;7\;\;0\;\;5\;\;-1\;\;2\;\;-2$

这样修改后可以做到第$i$个位置最少要比第$i+1$个位置少$，1，$而$i$最少要比$i+2$的位置少$2$.

$T3$

对于$Subtask~1:$

$1.$枚举两个点，路径中一个个节点统计

$2.n^2$枚举两个点，然后用树剖判断判断是否可行

复杂度$O(n^2log^2n)$

对于$Subtask~2:$

将正解的扫描线改成暴力修改

复杂度$O(n^2)$

对于$Subtask~3:$

尺取法

复杂度$O(n)$

对于$Subtask~4:$

由于每种颜色最多只有$20$个节点。我们枚举一对颜色相同的节点，分别设为$x,y$.

对于$x,y$的情况分成两类$($下面默认$dep_x<dep_y):$

$1.x$不是$y$的祖先

那么所有两端分别位于$x$的子树与$y$的子树中的路径都是不合法的。

$2.x$是$y$的祖先

那么不合法路径的一段位于$y$的子树,另一端位于$y$所在$x$的儿子的子树中。

如果用一个矩阵表示的话，枚举一对颜色相同的节点就相当于对一个矩形染色。

最后没有染色的就是合法路径，再根据题目限制去重一下即是最终答案。

矩阵求并用扫描线即可

总结

出题人估计难度 $\color{limegreen}{绿}$,$\color{limegreen}{绿}$,$\color{blueViolet}{紫}$.

本次比赛难度类似$NOIPday1$,而且暴力分很足

但是由于没有送分题，所以平均分不会很高

对于$T1,$估计有$6 \sim 10$个人$A$掉，平均分大概在$35 \sim 60$之间,因为$20\%$的数据很容易，网络流估计有$6$个左右的人写出来

对于$T2$，估计有$5 \sim 10$个人$A$掉，平均分大概在$30\sim 50 $之间,因为出题人觉得转成中序遍历应该有少部分人想不到，但是想到的话$30$分应该稳拿，即使想不到也还有链的情况可以写。

对于$T3$,估计有$2\sim 5$个人$A$掉,平均分大概在$30\sim 50$之间，因为$25\%$的暴力很无脑，$15\%$的链的情况也不难想，并且原题挺有名的

$1.$赠送分$20+30+25=75$

$2.$普通暴力神仙$50+30+25=105$

$3.$高级暴力神仙$100+50+40=190$

$4.$平均分$70+40+40-10($平均写萎分$)=140.$

$5.AK$神仙$100+100+100=300$

原题$:$

$T1:$https://www.luogu.org/problem/P4957

$T2:$

现在给定一棵二叉树，可以任意修改结点的数值。修改一
个结点的数值算作一次修改，且这个结点不能再被修改。若要将其变成一棵二叉搜索树，且
任意时刻结点的数值必须是整数(可以是负整数或$0$)，所要的最少修改次数。

二叉搜索树首先是一棵二叉树。设$key[p]$表示结点$p$上的数值。
对于其中的每个结点$p$，若其存在左孩子$lch$，则$key[p]>key[lch]$；若其存在右孩子$rch$，则$key[p]<key[rch]$；注意，本题中的二叉搜索树应满足对于所有结点，其左子树中的$key$小于当前结点的$key$，其右子树中的$key$大于当前结点的$key$。

$T3:$https://loj.ac/problem/6276

$Description$

你是一个制作团子的师傅，现在，你正想用竹签把团子串成一串。

团子被放置在长为$N$行，宽为$M$列的隔开的格子里，每个格子里都放着一个团子。每个团子的颜色是红、绿与白中的一种。

你可以选择三个从左到右，或者从上到下的连续的格子，把格子中的团子串成一串，按照这个顺序，一串团子串上正好会有三个团子。

现在，你希望尽可能多做些颜色按照红绿白顺序的团子串，并且团子在串上的顺序必须与从格子中取出的顺序相同。需要注意的是，同一个团子只能被串在一串团子串上。

你最多能制作多少串团子串呢？

给出放置在每个格子上的团子的颜色，你需要计算最多能制作的团子串的数量。团子串的颜色必须按照红、绿、白的顺序。

比赛链接$:$点击进入

$Description$

给出一棵树$($根是$1$$号节点 )$和$q$个询问,对于每个询问$v_i,$要求回答以$v_i$为根的子树的重心

$Desciption$

给一个无向图$,n$个点$m$条边，给定一个$01$序列，如果$a[i]=1,$要求走到这个点奇数次$,$否则，要求走到这个点偶数次$,$请你任选起点$,$输出满足要求的经过点的序列和序列长度$,$序列长度不能超过$4n$

$Description$

给定一棵带点权树，求树上最长上升子序列的长度