最近做的BZOJ题 III

VictorWonder posted @ 2015年3月07日 19:18 in BZOJ with tags 刷题记录 , 1131 阅读
按照原本的想法,应该要在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。

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter