songhn's blog
P1073 最优贸易 P1073 最优贸易
似乎题解里都是两遍spfa,加堆优化的dijkstra也能过,这道题其实求出两个点a b要b-a最大,而且b的遍历顺序要在a后面,可以考虑两次dijkstra来维护d与v两数组处理,d表示走到这个节点前面能买到的最便宜的货,f表示这个节点往
2019-07-06
P1438 无聊的数列 P1438 无聊的数列
区间加等差数列模板,维护a的差分数组c,对于$l-r$的首项为k公差为d的等差数列,只要对c进行3个操作$c[l]+k$ , $c[l+1-r]+d$ , $c[r+1]-(k+(r-l)*d)$,直接线段树维护c的区间加 区间查询即可,注
2019-07-06
P2024 食物链 P2024 食物链
带权并查集题解PS:题解参考了许多dalao的文章所以难免有既视感,请见谅 一般普通的并查集只能确定节点与父节点的关系,但比如像是食物链这种类型的题目,给定了ABC的关系,这个时候就需要给并查集加权,这个权一般用来表示两个节点之间的关系,由
2019-07-06
对拍 对拍
在对拍时我们需要四个文件1. zj.cpp这是复杂度较有优但正确性未知的代码 2. baoli.cpp这是暴力但正确的代码 3. random.cpp这是随机生成数据的代码 4. duipai.cpp这是用于对拍的代码,在对拍时执行它的ex
2019-07-06
P2014 选课 P2014 选课
这是树上背包型问题 $f[i][j]$表示对于以$i$为根的子树中选$j$个获得的学分 则有$f[i][j]=min(f[i][j-k-1]+f[v][k]+w[v])$ 之所以$j-k-1$是因为子树中肯定要取$v$,对于每一个子树,都进
2019-07-06
P1880 NOI1995石子合并 P1880 NOI1995石子合并
继续重新学dp,当年写的代码真是丑,一点缩进都没有… 基本区间dp,由于是环形,先复制一份然后继续求解,可以发现区间长度可以递增,把它作为状态,之后枚举左端点,求出右端点,然后在这中间枚举端点,进行更新。之后在扫一遍去最优就好了 #inc
2019-07-06
tyvj1061 Mobile Service tyvj1061 Mobile Service
线性dp,注意初始化以及三个点不能相同,还有不要弱智爆内存 #include<bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; int l,n,c[50
2019-07-06
P2678跳石头 P2678跳石头
二分经典题,不过n=0的边界情况要特判一下 #include<bits/stdc++.h> using namespace std; const int maxn=100050; inline int read() { in
2019-07-06
P2055 ZJOI2009假期的宿舍 P2055 ZJOI2009假期的宿舍
这道题难在建模,首先复制n个节点以及一个超级源点 汇点,对于非在校生或是要住在学校的在校生都由源点连一条边,住在学校的在校生向自己连边,认识在校生的外校向在校连边,有床的向汇点连边,最后最大流应等于需要床的人数,判断即可 #include
2019-07-06
POJ1741 Tree POJ1741 Tree
初学点分治,挂一个博客 需要注意的地方在于找树的重心的过程,因为我们对一个树进行分治,所以容斥的时候的n不能是总点数,而应该分成两个函数,一个dfssize和disroot,统计出每个点儿子最多的节点,然后找根的过程中这样更新$maxv[u
2019-07-06
1 / 7