首页 > 代码库 > 屁股痛#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