bzoj 1015

这题挺有意思的。大意是在删除点的同时，输出连通块的个数。乍一看挺水的，反向操作就行了，用并查集维护，dfs求连通块，但是第一次全部WA了，还是忍不住看了数据。

自己没有想到的是，每次加入星球后，连通块会变多，想了想，因为有些星球被摧毁了，就不算连通块，所以需要在在恢复星球时，先把当前答案增加1，然后再开始处理减少的情况。

另外要注意的就是不能重复摧毁星球，否则反向操作的时候会导致星球的数量统计出现问题，只有在其第一次摧毁时才操作，针对每个星球记录一下即可。

bzoj 1016

最小生成树计数问题。生成树计数问题理论上都可以用基尔霍夫矩阵-生成树定理来解决。不过构造比较麻烦。

本题给出的特殊条件使得有更简单的做法。因为每条边只有十条权值相同的，所以可以直接枚举然后计算。

这道题DP分两部分，一部分是在树上，但是树上DP时无法计算如何产生最大的收益，于是就要再做一个线性的DP来处理收益，需要两部分DP相结合。

这道题思想比较新颖，用线段树来维护连通性，其实就是维护一下是否有权值。但是要把其放在不同的位置来处理，同时要考虑如何走可以到达，然后维护连通性。听说分治并查集也可以做，但是并没有找到题解，也不会写。。。

这题题目名称叫汉诺塔，但并不是简单的递归。事实上，需要知道一类汉诺塔问题的递推公式，步数总是一个线性的一元一次递推式，即$f[n]=f[n-1]×a+b$。那么只要用三个栈来模拟三个柱子，便可以模拟出前三次操作，计算出$a,b$然后进行递推计算即可。

这道题线段树确实可以直接解决。事实上任何可以快速插入查询的数据结构多可以完成相应的操作。但是另外一种写法是利用单调栈，查找时二分查找，思路还是很值得借鉴。

这道题不是纯的计算几何。最大值最小会想到二分，而且到两边的距离确实具有单调性，但是二分的话先让会浪费很多时间。所以可以根据每次二分的答案计算出哪些地方不可能产生答案而直接剔除，这就用到了迭代的方法。代码实现也比较复杂，需要计算很多量。

DP。设计状态比较重要。数据范围中，债务的最大值只有1000是突破点，可以直接把A、B的债务作为两维，然后进行DP。还是比较好处理的。就是一个01背包，然后直接用滚动数组计算即可。

另外本题需要先推出一些结论，那就是转移是有限的。要推出不同的情况下哪些转移是不同的。然后来进行操作。

数学题。这么裸的莫比乌斯反演不会推，真是problemB白做了，主要不好处理的就是连续的乘法。但是化简一下就成可以直接用的了。看来还是要多做一些题。

这题的模数平方会爆ULL，所以不写个单精取模几乎骗不到暴力分$0.0$。

详细一点的在学校OJ上，截个图吧。。

HAOI2006，话说多年前的题不是都很水么，这道题好难。

第一问利用差分思想，只不过是数组减去下标，然后最长上升子序列即可。

第二问挺难的。下面是网上的题解，事实上我想的也差不多，只不过没有证明下面的结论，所以只想出了$O(n^2logn)$的做法，是过不了这题的。题解中公式比较多，就直接粘图片了。第二问主要是证明结论的，我觉得最值得借鉴的是第一问的思想。

本来看到最小值最大以为是二分，但是并不是，数据范围很小，直接暴力搜索即可，注意每次搜索后选择较好的答案

这题是要求$[1,n]$的正整数组成的数列在不同的置换下，一直循环到恢复初始状态，循环次数有多少种。

这道题可以转换一下。
试想每一个对应关系$a-b$为从$a->b$的一条边，
那么图中一定存在$n$条边且每个点入度出度都为$1$，

易证一定存在一个或几个环。
实际上排数就是这几个环大小的LCM。
即求和为n的数列的最小公倍数种数。
那么可以直接DP。

数位DP，设计状态比较重要，而且不仅要满足题目中所给的条件，也要让这是一个合法的数字。

数位DP的维度设计一般就是数字的长度，而且多是一些数字不同组合方式计数问题。

这道题模型建构很关键啊，想了好久才想出来。不过还是没有自己完全做出来，因为毕竟模型建出来，解决方法也很重要。

每种合金第三个含量可以由前两个计算出来，所以不必考虑。将其看成平面上的点，如果想由几种合金组合成题目要求的合金，可以证明，必须要在几种合金的凸包内部。

之后就是如何处理，事实上还需要建一个图，要求的所有合金如果都在某一条线段的左边，就连一条边。然后floyd求最小环即可。

本题先化成计算几何，再向图论转化是十分巧妙的。思想值得借鉴。

暴力枚举，与入门经典上的暴搜不一样，本题简化了麻将，所以可以很简单的贪心，显然应该优先组成刻子，然后$O(n)$扫描的过程中进行枚举对子进行判断，必须组成三的倍数。最终时间复杂度为$O(n^3)$

又是一道贪心。按T2排序之后扫描，在保证可以修的情况下尽量多修。还是比较好想的。