NAIPC 2017补题
D
给定一棵 n ( n ≤ 2 e 5 ) n(n\le 2e5) n(n≤2e5)个点的有根树，每个点有点权，选出一些点，使得这些点的满足大根堆
的性质，求最多可以选多少点。
如果是一条链，就是求LIS，做法是维护一个单调队列。
树的话，其实也可以用单调队列，不过需要对不同儿子节点的队列进行合并。
可以考虑用multiset，进行启发式合并。
E
有 n ( n ≤ 2 e 5 ) n(n\le 2e5) n(n≤2e5)个点，其中 s s s个是特殊点。有 m ( m ≤ 5 e 5 ) m(m\le 5e5) m(m≤5e5)条候选边。需要求一棵最小生成树，使得恰好有 w w w条边是普通点和特殊点之间的。
其实就是边有两类，每一类选的边数固定，求最小生成树。
如果直接Kruskal，遇到一类边选满后跳过的话，是有问题的。
考虑带权二分，即把其中一类边统一加上一个权值，然后跑Kruskal，直到每一类选的边数恰好符合要求。
不需要每次都把边混在一起排序，可以用two-pointers。
G
有一个 n × m ( n , m ≤ 50 ) n\times m(n,m\le 50) n×m(n,m≤50)的矩阵，每个格子里有一定量的苹果（每个苹果1元）。有 k ( k ≤ 1 e 5 ) k(k\le 1e5) k(k≤1e5)个顾客，每个顾客带了一定数量的钱，且只能在一个子矩阵内购买苹果。求最大总消费量。
网络流，但直接建图边数是 O ( n m k ) O(nmk) O(nmk)的，会MLE。
可以考虑二维线段树优化建图，把边数减少到 O ( n m + k log n m ) O(nm+k\log nm) O(nm+klognm)。
H
有一个 n n n个点的完全图，每条边有一个颜色。该图满足：任意一个简单环上必定存在一对相邻边同色。
定义 f ( S ) f(S) f(S)为点集 S S S中最大同色（即图中所有点间的边颜色相同）子图的大小。
求 ∑ S ⊆ [ 1 , n ] f ( S ) \sum_{S\subseteq [1,n]}f(S) ∑S⊆[1,n]f(S)。
可以证明图中必定有一个点的所有出边颜色相同。
去掉这个点后剩下的图依然满足。
因此可以转化成一个长为 n n n的序列。
然后搞dp
查看30道真题和解析