最近做的BZOJ题 III
按照原本的想法，应该要在WC前刷到250题的，结果现在WC都已经过去一个月了，我才拖拖拉拉的刷完。算了，不说了，都是泪啊。下面是一句话题解。（作为一名轻度强迫症患者，偶尔格式不正常真是不爽啊）
48
BZOJ 1180 双倍经验，和2843一模一样……
BZOJ 2330 差分约束系统
BZOJ 3668 按位贪心乱搞
BZOJ 3669 动态MST，出现了莫名其妙的错误，改了一下连边和拆边的顺序结果就对了……
BZOJ 3039 悬线法求最大子矩形，具体请看2003年王知昆的论文
BZOJ 1057 悬线法求最大子01矩形和O(nm)的DP求最大子01正方形
BZOJ 1927 最小费用最大流
BZOJ 1934 最小割建模
BZOJ 3578 线段树，重点在于判重，所以当然要用hash。首先给每个数赋一个不同的hash值，我是直接lim+i，接着就是hash了。大多数人用的应该是xor，估计就我一个奇葩用的是*吧？还用快速幂求了乘法逆元，还进行了双关键字的hash……结果最后还是WA了，然后把lim从100000扩大到了500000，于是AC了。
BZOJ 2809 贪心+可持久化线段树，结果查询的地方出了点问题，我的查询程序是不查询最右端的那个结点的，然后第五个数据狂WA，最后把线段树的范围扩大为0~n+1，然后就水过去了。
BZOJ 2006 堆+主席树，第2个数据点神坑，其他数据都很水，在判定范围的时候出了点问题，坑我半个多小时。
BZOJ 2819 链剖水题
BZOJ 1042 DP+容斥原理
BZOJ 2816 首先，请忽视“数据有误”这句话，然后，按照不同的颜色建树用LCT维护（颜色数最多只有10），要注意的是，有可能会出现一条边修改后的颜色和修改前的颜色是一样的。
BZOJ 2815 求LCA用倍增就行了，没有必要打LCT。出详细题解请下转出题人的blog：
BZOJ 1876 更相减损法，不过有一个小优化，二的倍数需要除以2，不然会超时。另外，python如果直接调用函数递归求gcd的话会WA，必须要递推，汗……还有，我的c++跑得比python还慢这是怎么回事……
BZOJ 1150 贪心+链表乱搞，具体请右转：http://hzwer.com/2934.html
BZOJ 2151 和上面那题差不多，就不详细解释了。
BZOJ 2127 最小割。
BZOJ 3438 同上，忽然发现原来我用的模板是错的……虽然Claris给我的时候是对的，结果我把它乱七八糟地改出问题来了……TAT
BZOJ 3834 根号枚举就行了。
BZOJ 2131 线段树优化DP，先将坐标系旋转45度再直接转移，具体地可以去寻找一下2011年的集训队作业-李其乐。
BZOJ 2132 最小割，和上题同样的来源。
BZOJ 2186 乘法逆元+欧拉函数
BZOJ 2594 卡了我一个上午TAT……一眼秒的LCT求动态MST水题，但是加强后的数据特别大，所以开始的时候我们不能够动态求MST，要将所有边排序之后，再对以后不会被删掉的边直接MST，这样的话，就可以将LCT的一百万次操作减少为十万次操作……之后再倒着做就行了。
BZOJ 2286 虚树的模板题。
BZOJ 3835 斜率优化，关于结论的证明请看我写的详细题解。
BZOJ 1305 网络流，从小到大枚举答案再用最小割判断。
BZOJ 1079 DP，以颜色剩余次数的数目为状态进行转移。
BZOJ 1019 递推，f[i][j]表示第i根柱子将上面的j个盘子搬运到第g[i][j]根柱子上的步数。
BZOJ 1064 具体请看lyd的博客（网址忘了，请百度搜索），我莫名其妙的有个点比答案小1，然后悄悄打了个表（嘘——）
BZOJ 2743 开始的时候以为根号大军可过，后来看到数据范围是一百万，换了一种做法，离线+树状数组，类似于GSS2的做法。
BZOJ 1565 经典最小割例题，建图有点麻烦。
BZOJ 3892 最开始以为是分层最短路，虽然感觉复杂度很大，但还是义无反顾地打了，打到一半的时候才发现建图好像就会超时，然后去网上搜了一下，看到大家都打了DP，就把程序删了重打了。
BZOJ 3894 最小割，具体建图就不说了，类似的题目已经做过两三道了。
BZOJ 1306 看到数据范围就知道搜索，因为是个搜索弱渣，所以是去网上找了个短程序，按照程序打的，最后卡过去了。据说可用记忆化搜索做，但我不会，暂时就这样吧。
BZOJ 2440 二分+容斥原理，听说直接容斥也是能过的，不过加上莫比乌斯反演的话速度更快，计算的时候要注意，可能会爆了int，就会死循环了。
BZOJ 3091 LCT，主要在于updata，合并的公式推对了就行了。
BZOJ 1833 脑子一片糊涂，照着以前的数位DP程序打了一遍，最后还是有点问题，好像两个数位数不同时我的程序有点问题，然后随便加了个特判（不知道是不是因为这个原因）终于过了。
BZOJ 1044 二分+DP，j写成了i，怎么都搞不对。
BZOJ 3504 网络流。多组测试数据神马的最讨厌了！
BZOJ 1066 hzwer大神的题解：http://hzwer.com/1903.html
BZOJ 2656 递推，本来懒得打高精，想要打python，然后发现这道题我不会用python（不知道怎么打全局变量），然后就只能打了C++的高精度了。
BZOJ 1084 DP，m=2的情况坑了我好久，一直有一种情况没有考虑，最后只过了一半数据点，没办法，只能照着网上的程序改了。
BZOJ 2301 莫比乌斯反演，一分钟内就推出了公式，然后不幸被卡。我自己电脑上都在50s内过去了，结果在BZ上被卡了，最后只能照着Claris的程序改，用容斥原理做，总算是AC了。
BZOJ 3676 回文树裸题，具体可以看我的论文：http://victorwonder.blog.uoj.ac/blog/146
BZOJ 2624 据说只有打表才能过，唯一让我郁闷的是，为什么我和Claris明明都是去OEIS找的表，我的就是错的，而且，偏偏我错了的还是数据恰好要询问的那个地方TAT。
评论 (0)
