今天早上。。出于某种不可抗拒的原因，没心情写题，所以正好小记以下（我是按分类记录，不是按日期记录）：

• 动态规划：
  • SCOI2008 着色方案  很好的题，f[c1][c2][c3][c4][c5][k]表示状态进行转移(上网看)
  • HAOI2010 计数  主要是涉及到 具有不可区别物体的集合的排列（比如重新排列SUCCESS能构成多少种不同的串，公式是(n,k1)*(n-k1,k2)*(n-k1-k2,k3)... = n!/(k1!*k2!...*kn!）其中ki表示某种元素的个数
  • SDOI2010 地精部落  这个题网上说的方法看不太懂，神马之云想的方法是 f[i][j]表示长度为i的序列第1个是j且开始下降的序列个数，g[i][j]表示...且开始上升的序列个数，那么f[i][j]=Sigma(g[i-1][k])k<j，g[i][j]=Sigma(f[i-1][k])k>j，dp的时候记录一下Sigma信息就可以省掉转移的那一维。
  • HAOI2010 最长公共子序列  dp时记录方案数，再容斥掉多计算的即可
  • HAOI2010 软件安装  好题 一开始看不就是个简单的树形依赖背包嘛，写出来才发现图里面竟然有环，不过既然是环，选一个就全都得选，所以缩成点，构成新的图，再在新图里面dp就可以了（注意环连接的要么什么都没有要么是外向树，对于外向树，缩点之后都不可能有前驱，所以连接到0，这样就是棵标准的树了，从0开始dp就行了）
  • 越狱第1季第13集 大神的做法不会，不过好像和我的方法有点像（二分答案，然后检查）
  • 瑰丽华尔兹 又是好题 f[k][y][x]表示第k段的结尾在y行x列的最长滑动距离，转移O（n）的，所以优先队列优化就可以Ac
• 图论
  • 公路修建 。。。看出来了很简单，裸的最小生成树，不过由于边数太多Kruskal会跪掉，所以只能用Prim了
  • 卡赞群岛 找到双连通分量，缩点然后dp（由于是无向图，缩点之后必然是个无根树，或者是无根树森林，所以可dp。
  • HAOI 软件安装 见上文
• 贪心
  • SCOI2008 斜堆 很有意思的题，按照斜堆的规则，最后插入的点一定在最左边（也就是便利的时候从不向右转），如果没有根变成左子树的情况，每次找最左边的点，删掉，然后模拟一下就行了（基于字典顺序最小的原则）。考虑上较小元素会替代根的情况，如果我们发现某个极左点没有右子树，那么说明它是叶子结点或者是替代根的元素，此时必须先删它（否则不可能构成目标树），基于最小字典序的原则，这些步骤合在一起就是：每次从根向左找没有右子树的点，一旦发现就把它删掉，并且将它的祖先的左右子树互换，最后倒序输出删点顺序即可（有一个特殊情况，即某点的左子树只有一个叶子结点，而且它没右子树，那么此时删除那个叶子结点（基于字典序最小的原则）），相关拓展见这位大神网志
  • 立春树 树上贪心，比较简单，不说了
• 数论
  • 双亲数 貌似都是利用容斥搞的，用Mobius函数搞会快点，关于Mobius Function见Noi2010 能量项链，HAOI2011问题B，以及网上各种题解。