首页 > 代码库 > 屁股痛#4

屁股痛#4

A http://codeforces.com/problemset/problem/527/C

对一个矩形进行横和纵两种方向的分割 求每次分割后最大碎片的面积

用一个set记录分割线的位置 
用一个可重复set记录线段的长度 
用容器自带的二分找到位置并更新新的位置和长度 
容器内部是有序的 取最后一个元素相乘即为最大

http://paste.ubuntu.com/25124870/

需要学习的地方:STL是很强大的工具 在需要做一些复杂工作的时候记得考虑是否能用STL来简化操作

B http://acm.hdu.edu.cn/showproblem.php?pid=1561

树形dp dpij表示以i为根选j个点的最大价值 
以0为虚根选m+1个点

http://paste.ubuntu.com/25125210/

比赛的时候感觉想出了差不多的结构 
然而自己就是写不出 还是学太少了

C http://codeforces.com/problemset/problem/527/E

要求添加最少的边使得所有点的出度入度为偶数

最后得到的图是一个欧拉回路 
把已有的图中度数为奇数的点连起来 
如果要满足条件则需要有偶数条边 
如果连完后为奇数条就对任意一点添加一个自环 
做一个无向图的欧拉回路 然后把它变成有向图的欧拉回路 
把a-b-c-d-e形式的变成 a->b<-c->d<-e 
(感觉很神奇 以后有空再好好体会一下)

http://paste.ubuntu.com/25126008/

D http://acm.hdu.edu.cn/showproblem.php?pid=5739

对每个割点删除后形成的联通分量建立一个新点 
给新点和联通分量的每个点连边 
再对新生成的森林进行树dp

还看不太懂代码实现 以后补

E http://codeforces.com/problemset/problem/527/B

水题 
分别检测ans-1和ans-2的情况

F http://acm.hdu.edu.cn/showproblem.php?pid=2586

水题 
倍增LCA

G http://acm.hdu.edu.cn/showproblem.php?pid=4479

求一个严格递增路径的最短路

把边按权值排序 
每一次更新相同权值的边

把这些边全部存起来再进行更新 
就可以把保证更新到的是之前已经走过的点 即 严格递增

http://paste.ubuntu.com/25126658/

H https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1208

用一个线段树表示一维的区间上的最值 
对每个星星 以它为左下角在可以框到星星的范围内加上一个权值 
在每个点的值就是能选到的各个星星的权值之和(重叠) 
对y轴使用一个扫描线 遍历到位置yi时更新一位线段树上的星星

因为数据很大 所以需要离散化

(这道题可能刚接触有点难懂 以后要记得来再理解一下)

http://paste.ubuntu.com/25127223/

屁股痛#4