update:16.06.30

671 A. Recycling Bottles

枚举两个人分别拿什么瓶子（只需枚举最大和次大）然后取最小值即可（注意：可以只移动一人）

671 B. Robin Hood

给一列数，每次将最大的-1，最小的+1，重复 $K$ 次，求最后的极值

直接模拟比较麻烦，可以考虑二分结束操作时的最小值和最大值从而得到极值

671 C. Robin Hood

给一列数，定义 $F(i,j)$ 表示将 $[i..j]$ 删去后序列两两最大gcd，求 $\sum F(i,j)$

一开始定义 $pr[i]$ 表示当左端点为 $i$ 的时候右端点的最小值

从大到小枚举gcd，将其倍数全部提出来，容易知道有三段 $F$ 区间的值一定是等于d（大于d的已经被计算过了）就可以通过线段树区间修改 $pr[i]$，计算总数减少了多少即是 $F(i,j)=d$ 的个数

这样做有点麻烦，不妨设 $nx[i]$ 表示当左端点为 $i$ 的时候非法右端点的最大值，然后“计算总数减少”改成“计算总数增加”，这样也是一样的

671 D. Roads in Yusland

一棵大小为 $N$ 的树，树上的边全部损坏，$M$ 个工人能修复从 $u_i$ 到 $v_i$ 的路（保证其 $Lca=v_i$）花费为 $c_i$，问把所有边修好的最小费用

dfs一遍，将工人按 $x_i$ 的dfs序排列，子树也记录下dfs序中对应的区间；然后第二次dfs统计答案，用线段树维护轮到哪个工人修路的最小代价，每次dp从里面转移，dp再转移到线段树中，例如将某棵子树除外的其他子树信息加到线段树中

顺便其对偶问题可以贪心解决

660 C. Hard Process

给01序列，最多能将 $K$ 个0修改成1，使得全部都是1的子串尽可能长

双指针大法，0太多了就右移左指针，否则右移右指针

660 D. Number of Parallelograms

给 $N$ 个点，无三点共线，问有多少平行四边形

两两枚举线段然后排序，求得多少对重复的线段，最后除以4即可

660 E. Different Subsets For All Tuples

设 $F(a)$ 表示序列 $a$ 的不同子序列个数，现在给你序列集 $S$，其中包含全部长度为 $N$ 并由 $[1..M]$ 构成的所有可能的序列，求 $\sum F(a \in S)$

首先为了去重，有多个位置匹配则取最前面，那么就可以分成三个阶段（子序列未匹配完且以关键字作为结尾的方案数、子序列未匹配完且以非关键字作为结尾的方案数、子序列匹配完的方案数）分别设为 $A,B,C$，则转移方程为

$$A(i)=m(A(i-1)+B(i-1))$$

$$B(i)=(m-1)(A(i-1)+B(i-1))$$

$$C(i)=mC(i-1)+A(i)$$

685 D. Kay and Eternity

给 n 个点，问端点为整数边长为 K 且包含 $i=1,2,..,n$ 个点的矩形有多少个

转成矩阵求交

离散化 y，然后按 x 排序，维护每列的最后一次变化时刻和当前值，复杂度 $O(nlogn+nk)$

662 C. Binary Table

给 n*m 的 01 矩阵，每次可以取反一列或一行，求最少 1 个数，$n<=20,~m<=100000$

假设行的操作为 mark，预处理出经过操作 mark 后有 k 个 1 的列数（dp[k][mark]）然后就可以 $O(n2^n)$ 求得答案

关键是 dp 怎么求，我们一开始能得到 dp[0]，接下来构造 $F[k][mark]=[count(mark)=k]$，然后我们会发现 $dp[k]=dp[0]*F[k]$，这一步是用 fwt 实现的，总复杂度 $O(n^22^n)$