SDSCDay4
A
考虑我们直径的两个性质
1.一定选择叶子节点
2.两个点集的直径合并性质
所以我们可以用线段树合并维护子树中的直径这一维
然后用一个前缀查询直径处理每个点的询问
B
我们设最大值位置为x,然后建新点y1y2,然后优化建边就好了
对于更大的数据,可以线段树优化建图
然后两个15%的提示需要不同的建图方式
最大值可以用笛卡尔树去建图
两边要去中间最小值?这个直接建两排后缀优化的
->->->->
->->->-
然后会发现最短路径一定会先找中间一个然后再到后面
所以就做完了...
C
对于一个三角形,两侧的图要么是一棵树,要么是两个树,两个情况分别设状态
所以我们要处理[l,r]这条边两侧的点,所以就会发现我们可以按照极角排序然后对于一个三角形就能很快找到了
合法状态数和边数等价所以直接DP即可
网络流
T1
发现答案是合法的就是存在可行循环流
循环流的充要条件是入度等于出度
所以考虑我们手动模拟一下我们走这个的过程,前c次走这个可以节省花费
对于一个初始数字为C的边考虑连(C,-1),(inf,1),后面那个代表我们可以修大这个数
从1到n 求个最小费用流即可
T2
发现白色格子可以二染色不妨设为红蓝
所以每个瓷砖一定会包括红黑蓝三颜色
然后我们就可以建立三排点的图(三列点,然后不同列的点之间有边)跑最大流
其中红色的连黑色的,黑色的连蓝色的
然后黑色的拆下点保证只用一次
然后红连S,蓝连T即可
T3
问题等价于每次选一组不相交线段,选k次问最大收益
所以可以考虑从左到右连边,然后容量为inf然后S到最左端点容量为k
每个线段左端点到右端点连容量为1,费用为价值的边求最大费用最大流
T4
发现一个能量源中决定了所有不合法的就是围绕能量源相邻和相对的两个水晶
然后对于能量源周围的六方格黑白染色,会发现一个能量源使得黑白不能同时出现,所以就可以最小割了
用流量代替权值
S->(权值)->黑->(inf)->能量入点->(权值)->能量出点->(inf)->白->(权值)->T
也就是说我们选择割掉那个都可以
T5
方法一是直接最小割,就是白点向周围灰点连边这样
令白格权值为1,灰格权值为-1,那么选白格就必须选周围灰格,问题就变成了最大权闭合子图,其+一开始灰格数即答案
T6
棋盘黑白染色,对于黑点连S,白点连T
然后非关键点向S/T连容量为2的边,相邻点连容量为1的边,费用为0
而关键点,连容量为2的边,拆成两个点,分辨连横连边和竖连边,然后对每个拆出的点连两个边,一个费用为0一个费用为1
表示如果我们流一个方向两次就要花钱
拆出的点按照自己的方向向上下/左右连边
T7
要想把参与人数搞成第一关键字就可以对于每个人,先用一个1,-inf的边,让权值强行拉大,这样每个人都能流上流量
剩下的连个(k-1,0)
对应的向喜欢的组别连边
然后我们最小费用流一定会流经它
而我们学习小组可以通过拆边形成a^2向T连边,就是考虑与上次的差值...
T8
考虑可以用大权值控制第一关键字
也就是说减肥药的价值为减肥量+inf,而药材的价值为-inf,选一个减肥药必须选对应药材,求最大权闭合子图
然后会发现药材数量一定不会超过减肥药数量就卡上上界了
T9
黑白染色,然后让左边和右边的对接起来,
然后有一个费用啊,接不同的费用不同
首先只有一个接头时就只考虑0,1,2,1
连原先为0,
两个接口,则我们会发现横纵只能连一个,我们可以分叉表示每个方向
我们可以用一个五边形来拆点,就是
然后会发现我们有T型水管,比较复杂,直接拆为4边然后列方程
a+b+c=0
b+c+d=1
c+d+a=2
d+a+b=1
然后我们能解出a,b,c,d,然后这个费用是浮点数*3即可避免误差
T10
枚举一个必须要包含的点作为树根
然后若选择了一个点,那么他到树根所有点都必须选,
最大权闭合子图
T11
我们先枚举一个边断掉
然后设dp状态f[i][j]表示点i的子树和j子树匹配的最大连通答案
然后就可以用网络流来儿子做到最优匹配转移
但这样会T,问题在于同一个可能的状态算了多次
然后考虑树形dp,dp_{i,j,k,l}表示i的父亲是j,k的父亲是l的时候子树的最大匹配程度是多少
然后转移的时候我们可以考虑网络流,最大权的去匹配儿子
这样我们的复杂度是
T12
一个棋子要么被占领要么四周的都被占领
那么这个就很像直线了
S->(代价)->A1->(收益)->A2
A2是四个点
然后就一条线,要保证收益要么全部割掉右边的四个
要么割掉自己的
T13
Ans=需要涂色的格子数-连续涂格子的次数
首先可以发现一个格子要么是横着要么是竖着涂的
然后相邻两个格子是横着还是竖着涂得选择了其中一种方式那么公共格子的另一种方式就不能选
从中选择最多连续染色方式?最小割
S-(1)-横-(inf)-纵-(1)-T
....
T14
如果在原图中两点之间有一条无向边，那么这两点到1的距离之差不大于1。
这个命题的正确性是显然的，我们考虑它的逆命题：
给定每个点到1的距离（不大于n），并给定一些已有的边，满足已有的边的两端到1的距离之差不大于1，那么一定存在一种方案满足该种情况。
那么就做完了,问题变为我们去钦定这个a,然后知道一个a能算出的b,然后已有连边的限制差为1,可以直接做
T15
首先发现横竖会冲突,然后列越长会限制横越短
另一个激光不能超过交点位置
二分图的切糕,我们可以把其中一条链给颠倒过来
然后就会...标准切糕模型
T16
合法的有
所有有三个的
以及一侧有两个的
然后您会发现满足任意2*2子矩阵有且仅有两对颜色不同必然对应一组合法解
然后问题转化之后考虑网络流,那么所有2*2子矩阵建成一个点,相邻点对相等情况可以看成一条边
因为同一个2*2的方阵中,如果我有两个不同的,就是类似于一个水管插头连接
就相当于铁轨铺设问题了,保证有闭合回路