Mambacrose

ride or die

水题大战

| Comments

好久没刷bzoj了,感觉整个人都逗逼了不少。。。

【bzoj 4144】用spfa求出离每个点最近的加油站的距离,设为d[x],然后对于一条边(u,v,c),将边权改为d[u]+d[v]+c。然后对于一组询问(a,b,c),将边权小于c的边全部加进来,判断a,b是否联通。
【bzoj 4152】在横坐标相邻或纵坐标相邻的点之间连边,求最短路。
【bzoj 4018】推公式,记录前缀和分块即可。
【bzoj 4151】1号点到答案点的距离至少为,找到距离限制最大的一条,然后再符合条件的点里面找到一个离1号点最近的点。
【bzoj 4145】状压dp,枚举子集,复杂度
【bzoj 4146】傻逼题。
【bzoj 4082】转化为树结构,枚举起点倍增。
【bzoj 3482】f[i][j]代表经过i条x边到达j号点的最短路,求一个凸壳即可。
【bzoj 4149】求出以i为最小值最大值向两边所能延伸的区间,线段树求最值。
【bzoj 1086】傻逼树分块。
【bzoj 4129】树上带修改mex,树分块套权值分块。
【bzoj 4029】傻逼贪心。
【bzoj 3881】神题。将s建立ac自动机,求出fail树,每次插入一个t串,记录下它在fail树种经过的节点,将这些节点到根的路径上的所有点权值都+1,但这样会算重。所以把这些点按dfs序排序后假设为a1,a2,....,ak。将a1,a2,...,ak到根的路径上所有点权值+1,再将lca(a1,a2),lca(a2,a3),...,lca(ak-1,ak)到根路径上所有点权值-1。可以直接在树上放标记,询问求子树上得标记和即可。
【bzoj 4034】傻逼数据结构。
【bzoj 4059】求出i向两边所能延伸的区间,线段树维护即可。
【bzoj 4028】分块hash,卡常真是一颗塞梯。
【bzoj 4001】令表示有x个节点的不同的二叉树的个数,令表示有x个节点的不同的二叉树的叶子数量,那么答案即为。推公式得。推出前几项找找规律就好了。
【bzoj 3874】三分送货次数,贪心。
【bzoj 4123】alice选择的为环上一段区间,bob可以控制alice的选择区域。令表示包含i的所有区间和的最小值,答案就
【bzoj 4080】不会做呀。。看官方做法发现巨复杂,然后去看了下网上的做法,随机化就可以过?
【bzoj 2433】dp,从前往后转移的时候维护可以转移的角度区间。
【bzoj 2878】树的话可以直接向上向下dp,环的话向上暴力转移向下一样的dp。
【bzoj 2436】第一问直接dp,第二问爆枚它所在的区间dp。
【bzoj 2437】二分图博弈,同bzoj1443
【bzoj 2432】找循环节,细节好多。。
【bzoj 4033】傻逼树形dp
【bzoj 1563】打下表就知道决策单调了,维护一个存决策的栈。
【bzoj 1491】傻逼题。
【bzoj 3489】kd-tree强上。
【bzoj 3211】傻逼线段树。
【bzoj 3171】每个点入度出度都为1,直接费用流。
【bzoj 3629】爆搜。
【bzoj 3237】同dzy love chinese。
【bzoj 3158】不能满足条件的两个数必定是一奇一偶,然后连边求最小割。
【bzoj 2429】傻逼题。
【bzoj 2229】全局最小割,每次把点集划分成两个部分,分治进行。
【bzoj 4025】lct维护已删除时间为权值的最大生成树。
【bzoj 3810】无脑dp。
【bzoj 4163】回文树。
【bzoj 4165】set强上。

Comments

comments powered by Disqus