Day1:

　　程序自动分析:

　　　　并查集裸题，离散化一下就好。

　　软件包管理器：

　　　　树链剖分入门题。

　　寿司晚宴：

　　　　2到n共n-1个数，两个人各选一个数集（可以为空集），设为A，B，要满足∀x∈A,y∈B,gcd(x,y)=1，问选择方案数。

　　　　我们发现，要满足这样的条件，选了一个数就相当于选择了它所有的质因子，而两个集合不能拥有相同的质因子。

　　　　注意到两个性质：

　　　　　　对于一个正整数x，大于等于√x的质因子只有一个，暂且叫做大质因子。

　　　　　　数据范围中n≤500，小于等于√500的质数只有{2，3，5，7，11，13，17，19}共8个。

　　　　先不考虑大质因子，因为小质因子只有八种，所以我们可以预处理每个数x的质因子集合prime[x]，进行经典的状态压缩动态规划：

　　　　　　设f[state_a][state_b]代表A集合选择质因子的情况是state_a,B集合选择质因子的情况是state_b的方案数。

　　　　　　初始化f[0][0]=1。

　　　　　　枚举每个数x，枚举state_a,state_b,满足state_a&state_b=0,

　　　　　　　　如果prime[x]&state_b=0,f[state_a|prime[x]][state_b]+=f[state_a][state_b]。

　　　　　　　　如果prime[x]&state_a=0,f[state_a][state_b|prime[x]]+=f[state_a][state_b]。

　　　　　　最后答案就是∑f[state_a][state_b]，满足state_a&state_b=0。

　　　　可是要考虑大质因子怎么办呢？我们将拥有相同大质因子的数放在一起考虑，因为他们只能出现在同一个集合里（或者不出现）。

　　　　　　g[0（或1）][state_a][state_b]代表将这些数放进集合A（或B），A,B质因子状态分别为state_a,state_b的方案数。

　　　　　　在处理当前大质因子之前，初始化g[0][state_a][state_b]=g[1][state_a][state_b]=f[state_a][state_b]。

　　　　　　枚举所有拥有当前处理大质因子的数x，枚举state_a,state_b,满足state_a&state_b=0,

　　　　　　　　如果prime[x]&state_b=0,g[0][state_a|prime[x]][state_b]+=g[0][state_a][state_b]。

　　　　　　　　如果prime[x]&state_a=0,g[1][state_a][state_b|prime[x]]+=g[1][state_a][state_b]。

　　　　　　将这些数处理完以后，令f[state_a][state_b]=g[0][state_a][state_b]+g[1][state_a][state_b]-f[state_a][state_b]。

　　　　　　为什么要减去呢？因为不放入任何一个数的情况在g[0]和g[1]都考虑了。

Day2:

　　荷马史诗：k叉哈夫曼树裸题。

　　品酒大会：后缀数组。用到了将height数组从大到小合并的方法。详见我之前的博客：http://www.cnblogs.com/iamCYY/p/4727309.html

　　小园丁和老司机：DP+上下界网络流。还没有改过就不说了...