T1 病毒感染

求出一张图，上的能从它出发一直覆盖整张图的所有点

说人话,其实我所给定的图的类型全部是树,所以说这个问题也就相应的转化为求树的重心,而树的重心的求法,我就不过多赘述了,详见代码

T2 切题之路

阅读理解题

T3 神秘钥匙

水题，显然可知答案是

${\sum }_{i=1}^n{C}_n^i\ast i\backslash sum\_\{i=1\}^\{n\}\; C\_\{n\}^\{i\}\; *\; i$

将样子改变一下可以得到

${\sum }_{i=1}^n{C}_n^i={\sum }_{i=1}^n\frac{n!}{i!(n-i)!}\ast i={\sum }_{i=1}^{n-1}{C}_{n-1}^i\ast n=n\ast 2^{n-1}\backslash sum\_\{i=1\}^\{n\}\; C\_\{n\}^\{i\}=\backslash sum\_\{i=1\}^\{n\}\; \backslash frac\{n\; !\}\{i\; !(n-i)\; !\}\; *\; i=\backslash sum\_\{i=1\}^\{n-1\}\; C\_\{n-1\}^\{i\}\; *\; n=n\; *\; 2^\{n-1\}$

所以说最终答案是$n\ast 2^{n-1}n\; *\; 2^\{n-1\}$

T4 迷之盒子

把题目转化为人能理解的样子 有一个方程

$x_1+x_2+x_3+\dots +x_n=mx\_\{1\}+x\_\{2\}+x\_\{3\}+\backslash ldots+x\_\{n\}=m$

保证每个 ,求这个方程有几组解。

T5 诡异数字

数位$DpDp$ 要注意一点,约束取min ,剩下的应该比较简单了。

T6 数列操作

可能有些在同学bzoj或者tyvj上见过类似的题目,简单的说这是一道平衡树的模板题目, (模板题目过多会不会被喷啊QAQ)

所有的操作都可以用splay或者Treap来维护,而出题人不会Treap所以就打了一个Splay的板子QAQ

T7 红包期望

$sqnsqn$发了

T8 机房网络

一个点到另一个点的最大流量就对应着最小割。也就是说必须要在左边割一条边,在右边割一条边假设左边这条边靠近$11$的点是$aa$ ,右边割的边靠近$nn$的点是$bb$那么所有连接$1-a,b-n1-a,b-n$的点都要被割掉

也就是说,左边哪一条边作为割时 ,对应的最小流量是固定的,这样取一个最小值就是最小割。

我们发现这样可以把一种割分为两部分 :

1、左边的一条边的权值

2、选这条边作为割,中间及右边的割产生的最小值

所以我们现在要维护的就是左边每一条边作为割时 ,中间及右边的割产生的最小值。也就是要在右边选一条边作为割,使得中间的对应边和右边的这条边的和最小。

考虑这个如何维护。建一棵线段树 ,首先对其中结点赋值,为右边每条边的边权,表示在右边选这一条边为割所产生的权值,注意因为边有可能直接连到汇点,所以要增加一个权值为$00$的边。

然后我们从$1-n1-n$将左边的边逐一进行考虑,每加入一条边,中间就会多一些边连向右边, 加入左边一条边时,枚举当前点连向右边的所有边, 我们将线段树中$e\mathrm{.}to-ne.to-n$这个区间内加上这个边的值,表示左边当前边再往下的边作为割时都要考虑当前加入的这些边。可以看出每次加入左边一条边并更新完线段树后,线段树中的最小值在加上这条边的权值, 就是这条边所对应的最小割。

用这种方法就可以求出,左边每条边作为割时,所对应的最小割的值。

考虑求答案,我们将求出来的这些值维护成一棵线段树,显然其中的最小值就是最小割,那么对于询问怎样维护。

由于我们求的是左边每-条边作为割所时所对应的最小割,所以这时候修改左边边的值也就可以直接修改 了,这样直接修改线段树,然后输出最小值就可以了。

T9 路灯孤影

设$dp[i][j][k]dp[i][j][k]$表示到第$ii$盏灯(按位置从左到右) , 最左边的需要覆盖到的位置是$jj$($00$代表不存在未覆盖) 最右端位置是$kk$ ,包括了这段实际没有覆盖的最大总长度。

考虑转移:

向右照射,且之前的最左边需要覆盖的位置不变,转移方程:

$dp[i][j][\max (R[i],k)]=\max (dp[i][j][\max (R[i],k)],dp[i-1][j][k]+\max (0,R[i]-k]))d\; p[i][j][\backslash max\; (R[i],\; k)]=\backslash max\; (d\; p[i][j][\backslash max\; (R[i],\; k)],\; d\; p[i-1][j][k]+\backslash max\; (0,\; R[i]-k]))$

向左照射,且覆盖掉了原来实际没有覆盖(或者原来没有未覆盖)的部分,转移方程:

$dp[i][0][\max (p[i],k)]=\max (dp[i][0][\max (p[i],k)],dp[i-1][j][k]+\max (0,p[i]-k]))(L[i]\le j)d\; p[i][0][\backslash max\; (p[i],\; k)]=\backslash max\; (d\; p[i][0][\backslash max\; (p[i],\; k)],\; d\; p[i-1][j][k]+\backslash max\; (0,\; p[i]-k]))(L[i]\; \backslash leq\; j)$

向右照射,且原来没有未覆盖部分,最右边位置在当前灯位置左边,取最右边位置后某一处$jj$到当前位置作为假装覆盖实际没有覆盖部分(或者不选取) , 转移方程:

向左照射,且原来没有未覆盖部分,最右边位置在当前灯照射左边界左边,取最右边位置后某一处$jj$到当前位置作为假装覆盖实际没有覆盖部分(或者不选取) , 转移方程:

总时间复杂度$O\left(n^3\right)O\backslash left(n^\{3\}\backslash right)$。

T10 好的序列

$rqyrqy$咕咕了QWQ

其他疑问可加以下交流群（加入一个即可啦~）

牛客多校算法训练营1：453799454

牛客全国算法训练营2：330766563

牛客多校算法训练营3：934889305