您现在的位置:主页 > 仙人掌论坛 >

弱逼发福利——BZOJ简易题解

发布日期:2019-10-04 07:58   来源:未知   阅读:

  本弱逼长期做题都是膜题解膜题解,感觉提供一些关键点在进行思考的话能够更快的加强算法能力,所以我就稍微的写一写。

  upd 3.8 : 懒癌晚期不想写东西了,我就记录一些最近做的不想写的傻逼题吧。

  【BZOJ1019】令f(i,j)表示从i柱子移动到另一个柱子盘子为j的操作次数,g(i,j)表示从i移动到另一个柱子盘子为j的移动位置。

  【BZOJ1025】考虑这个由多少个环且每个环大小和为n,对于每种状态的贡献就是lcm(各个环大小),那么就是求lcm值的种类。

  【BZOJ1027】其中有一维是没用的,这样就是一个经典问题:给定平面n个点,求最小凸包包围查询点。这个用最小环就能解决。

  【BZOJ1037】设f(i,j,k)前i个人有j个男的从i开始向前的连续段里最多有k个男与女的差,再设个g(i,j,k)同样地不同的是最多有k个女与男的差。

  【BZOJ1045】经典问题,转化成每个点向正方向扔多少点,转化下就是求一个中位数。

  【BZOJ1049】dp依照前一个dp值可以写一个O(n^3)的dp但是跑的飞快。

  【BZOJ1110】砝码的种类不多不会超过log次,考虑从小到大扔砝码就可以了。

  【BZOJ1237】将a,b都排序,只有连续三个数可以被调整,也就是每个数最多能被调整3次,这样直接dp就可以了。

  【BZOJ1906】显然的我们枚举两个蚂蚁,分类讨论一下就可以了,估计是要用O(1)的LCA。

  【BZOJ1937】树边被非树边覆盖可以列一个不等式发现就是求顶标,KM算法算一下。

  【BZOJ2151】加入每一个点用链表维护一下,每加入一个点将相邻两个点-中间的点扔到队列,并将这三个点合并成一个点。

  【BZOJ2177】转化成切比雪夫距离,那么对于一个点i分成8部分,那么有用的就是跟i最近的点,那么一个点最多8条边。跑一个MST就好了。

  【BZOJ2521】考虑加入的边,那么跟它联通的边比它小的这个图不能联通,那么就是对于每个边加了一些值之后不连通,那么考虑最小割。

  【BZOJ2690】离线算法就是把所有串建一个trie然后dfs序就可以,在线只要把dfs动态维护,用重量平衡树就可以。

  【BZOJ2740】将串reverse下,找到一个最小表达式,找这个位置到底的重复串,将这部分看成s[0..i-1],再对剩下的做一个最小表达式就可以了。

  【BZOJ2750】对每个点dijkstra一遍,然后考察每条边有效贡献就可以了。

  【BZOJ2822】考虑必须选n个,每次必须划分成两队,那么就是catalan数。

  【BZOJ3166】枚举次大值就能得到可行区间用可持久化trie就可以了。

  【BZOJ3251】考虑一组数列不能构成三角形最多不超过46个,那么长度小于46就暴力。

  【BZOJ3252】考虑叶子到根最大的肯定选,那么用线段树维护一下就可以了。

  【BZOJ3276】按照到初始点的距离排序,每次取肯定是在可行范围内取最小重量,然后把取出来的扔到数组里面不停的做,知道不可执行为止。

  【BZOJ3302】取树最中间的边,然后求出两块的重心,那么两个重心一定在这两个求出来的重心的链上,调整下就好了。

  【BZOJ3322】火车的那些点都是一样的就缩点,剩余的求最大生成树树上倍增求求就可以了。

  【BZOJ3323】注意到只有[l,r-1]不会修改,就在l之前加个0,把r加到r+1上。

  【BZOJ3324】可以看出来前面肯定有一坨1,那么剩余移动数不多直接考虑dp。

  【BZOJ3350】manacher求出所有相等不等的关系,相等用并查集维护,不等连边。

  【BZOJ3586】枚举字符串出现的集合和当前匹配到的字符串的位置,这个可以用gauss来消元,状态数大概不会超过500。

  【BZOJ4180】建出T的SAM,f(i,j)表示i开头j结尾的最短长度,二分倍增下。

  【BZOJ4257】二分下最小值,然后转化成圆链,最后肯定要成l1l2l3..lnr1r2..rn这样看下不降序列是否达到k就可以了。

  【BZOJ4304】缩点变成DAG,讨论每个点的进出可行点集用bitset维护。香港现场开奖结果直播论坛

  【BZOJ4305】首先gcd(*)=d可以转化成dgcd(*),这会耗费一个log,之后就是组合数搞一搞就可以了。

  【BZOJ4311】按时间分治[l,r],在这个时间出现的向量找出来,答案肯定在凸包上。

  【BZOJ4379】显然我们枚举每个删边,那么我们可以dp出上面一块的直径和子树的直径,做这个就只用搞出第一长第二长第三长的链就可以了,在记录一个向上延伸。

  【BZOJ4380】可以先dp出一段区间用的价格的代价,然后dp区间的最大花费。

  【BZOJ4386】每个点拆成3个,记录长度为i的方案数,记录下一堆矩阵倍增搞一搞就可以了。

  【BZOJ4402】需要观察出一个性质,本质不同的就两种序列,然后组合数算算就可以了。

  【BZOJ4416】注意到n21时不存在解。用f_{S}表示用了S集合内的元素要到串的第f_{S}位才能表示完全,再用一个转移状态函数表示对于第i位接受了个j要到第几位。