[考试练习题]4.20
三道降智好题
A. 商店
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。![[考试练习题]4.20 随笔 第1张](https://img.liuyixiang.com/image/2019/4/eMRFF3.png "[考试练习题]4.20 随笔 第1张")
包含关系，一定先让子树选择，自己选择剩下的最大的。
线段树O(nlogn)
反过来，一个值如果是子树最大的，一定会被到根第一个有顾客的祖先选择到
倒序枚举每个商品
并查集找到到根第一个父亲。
O(n+m)
B. 构图
![[考试练习题]4.20 随笔 第2张](https://img.liuyixiang.com/image/2019/4/fMJzM3.png "[考试练习题]4.20 随笔 第2张")
n<=3e4
大力讨论贪心
正负分左右
1.每个左都连接一个右
2.剩下都是右右之间连接。
一定涨这样：
![[考试练习题]4.20 随笔 第3张](https://img.liuyixiang.com/image/2019/4/yUbqMj.png "[考试练习题]4.20 随笔 第3张")
右面可以DP出f[]，表示前i个，前缀回文选择后缀都选择b[1]，最小值。
如果i是偶数，特殊考虑全部都是回文选择
（可以FFT优化）
然后枚举和左部点连的后缀。
全部暴力O(n^2)可过。
层层论证大力贪心
C. 朋友
![[考试练习题]4.20 随笔 第4张](https://img.liuyixiang.com/image/2019/4/YVNbiu.png "[考试练习题]4.20 随笔 第4张")
![[考试练习题]4.20 随笔 第5张](https://img.liuyixiang.com/image/2019/4/FJR7B3.png "[考试练习题]4.20 随笔 第5张")
每个鱼区间[l,r]
直接离散化
![[考试练习题]4.20 随笔 第6张](https://img.liuyixiang.com/image/2019/4/yM77ny.png "[考试练习题]4.20 随笔 第6张")
最大值的位置一定是经过的区间都到这里。否则不优。
T2,T3,想得太复杂。
更多精彩
