2 RHJoi

尚未进行身份认证

穷且益坚,不坠青云之志。

等级
TA的排名 7w+

从 线段树维护区间最大子段和 浅谈 DDP 【程序设计竞赛】

题意:n≤1e5,m≤1e5n\le 1e5,m\le 1e5n≤1e5,m≤1e5,每次支持单点修改,求区间内的最大子段和(不能为空)引言相信用线段树维护左边最大,右边最大的分治做法大家都会,我们来思考一下DDP怎么做这个题。先列出dp方程,f[i][1]表示从1选到i,i必须选的产生的最大子段和,f[i][0]:i可以不选。f[i][1]表示从1选到i,i必须选的产生的最大子段和,f[...

2019-11-15 12:10:39

OI考试中及平常练习里的一些低级错误总结

long long相关1,没开long long /long long开少了。具体地,可能是未对题目可能产生的数值预估,可能是只写了int的读优,忽略long long。2.#define int long long出锅。-1,比如在遍历图的时候,vector的返回值会出现问题,要强行转换(ll)。-2,main函数类型设置成signed ,避免出现long long main。3.爆...

2019-11-12 23:10:12

[NOI2009]二叉查找树【区间dp+treap理解】

洛谷P1864SOL题目构造了一个权值不随机的非旋treap,我们可以思考替罪羊树的重构方式。(好像同时出现了三种平衡树。。。)我们模拟一下递归建树的过程。假如最后已经修改好了权值,我们按照数据值总小到大排序,得到一个序列。对于当前 区间 [l,r][l,r][l,r],在其中找到一个权值最小的点(设为第kkk个)作为根, 再对区间[l,k−1][l,k-1][l,k−1]和区间[k+1...

2019-11-07 11:33:09

[SCOI2008]天平【差分约束+Floyd】

洛谷P2474SOL发现一道不板子的差分约束看到这个数据范围,我们可以想到一个暴力:枚举另外两个(记为C,DC,DC,D),判断是否满足A+B<C+DA+B\lt C+DA+B<C+D,A+B>C+DA+B\gt C+DA+B>C+D,A+B=C+DA+B =C+DA+B=C+D.转换一下,A−C>D−C ∣∣ A−D>C−BA-C...

2019-11-07 10:07:45

[PKUWC 2018]Minimax 【线段树合并优化dp】

LOJ2537SOLdp式子:f[U][rank−j−inU]=f[V][rank−k−inV]∗(P∗∑i=1k−1f[V][i]+(1−P)∗∑i=k+1totVf[V][i])f[U][rank-j-inU]=f[V][rank-k-inV]*(P*\sum_{i=1}^{k-1} f[V][i]+(1-P)*\sum_{i=k+1}^{tot_V}f[V][i])f[U][rank...

2019-11-04 20:14:09

[YNOI2019]游戏【概率dp+高斯消元】

P5415SOL对于我这样的“wen” “mang”,这题意可能有点太简略了。。参照了 @ i_m_a_大佬的题解才理解题意。。简述一下题意:每次选出序列的前4个,从中等概率产生一个赢家,留在原地,剩下三个按照原来的相对位置挪到序列末尾。依次循环,知道有一个人连续赢了m场,游戏结束。问初始序列中第k位置的人(我们称作目标点)连续赢m次的概率。用高斯消元求出概率dp方程式不难发现,我...

2019-11-04 18:53:16

[SDOI2008]山贼集团【树上背包+状压】

洛谷P2465SOL比较经典的一类树上背包问题套一个子集状压枚举。注意到代价的计算与所选的点的集合有关,如果我们要统计代价需要状压记录点集,而数据范围非常配合的给了P≤12P\le12P≤12,直接状压当前子树包含的点集。从叶子向根dp,对于TTT个限制,预处理出每一个点集SSS所产生的收益,并把路径拆成一个一个点,在向根转移的时候分开算贡献,及将子树的贡献算出,只考虑当前这个点对应的点...

2019-11-04 08:57:10

[ZJOI2019]语言 【线段树合并】

LOJ3046SOL转换一下题意,对于每一个点我们维护可以到达的集合SSS,ans=∑∣Si∣ans=\sum{|S_i|}ans=∑∣Si​∣。然后每次区间覆盖相当于向一条链上的每个点的集合,集体覆盖上一些点。有一个比较暴力的做法。对于每一个点,我们用一颗动态开点的线段树维护可以到达的点集,当前点的贡献就线段树的总长。对于每次操作,覆盖的点在一条链上,所以用树剖变成lognlogn...

2019-10-31 22:04:37

[SDOI2019]热闹又尴尬的聚会

LOJ3113SOL对于题目的p,qp,qp,q的限制,我们可以转化成(p+1)(q+1)>n(p+1)(q+1)\gt n(p+1)(q+1)>n,q是求最大独立集,但是此题不是二分图,无法用网络流等方式。我们需要最大化地求p,qp,qp,q。构造方法先贪心地求出最大的ppp。不妨把“加点”的思路转化为“删点“,即已经有一个合法的图,我们考虑让它更大。删除度数最小的...

2019-10-31 18:59:35

LOJ3057[HNOI2019]校园旅行【dp+优化建图】

LOJ3057SOL30pts从构造路径的角度思考,难以入手。总点数能实现O(n2)O(n^2)O(n2)算法,转换思路,从中间向两边接点,构造回文串。设f[i][j]f[i][j]f[i][j]表示i,ji,ji,j点对能否作为回文路径的两端。故枚举i,ji,ji,j的边尝试转移。不难发现这样做总复杂度是O(m2)O(m^2)O(m2)(每一对"边"最多被拿出两次)100pt...

2019-10-31 11:04:24

NOIP2017 列队【动态开点线段树/平衡树】

洛谷P3960SOL据说正解离线+树状数组一眼思路就是模拟题目的过程。我们发现每次出队为:第xxx行向左挪,最后一列向前挪。所以开n+1n+1n+1个平衡树维护队列就好了。nnn个记录xxx行1−m−11-m-11−m−1列的信息,剩下一个记录最后一列的信息。每次修改取出P(x,y)P(x,y)P(x,y),取出P(x,m)P(x,m)P(x,m),把P(x,m)P(x,m)P(...

2019-10-27 21:33:06

NOIP2017 宝藏 【状压dp】

P3959SOL不错的一道简单树论状压dp一句话题解:状压枚举每一层节点计算贡献,dp出答案。(或者深搜)说具体一点,发现贡献和深度有关,加上巨小无比的数据范围,我们可以记录前一颗树的节点和深度,枚举下一层地节点,把树一层一层地填出来。只需要预处理出 :把点集S1和S2连边的边权和最小值即可,顺便判一下合法性\text{把点集S1和S2连边的边权和最小值即可,顺便判一下合法...

2019-10-25 10:16:32

P4426 [HNOI2018] 毒瘤 【虚树+dp / DDP】

P4426SOL敲了3小时虚树,突然发现这是一道ddp板题。。。看来最近和板子挺有缘的。。transfer the probelem:\text{transfer\ the\ probelem}:transfer the probelem:在有10条多余边的树上求点独立集个数。基于原树思考。先求出n−1n-1n−1条边的fff值。剩下的边最...

2019-10-24 22:00:35

P4103 [HEOI2014]大工程【虚树】

洛谷SOL虚树板题一道。。。个人觉得这题比 “消耗战”更适合练板子(树形dp更为简单)说正解。注意到∑∣p∣≤2e6\sum |p|\le2e6∑∣p∣≤2e6,这提示我们建一颗虚树。建好后,2和3问就是求一个树上最短路,最长路,不再赘述。简单说一下1,我们对于每一条边统计有多少点对经过它。具体的,树形dp的时候算出,即为siz[son]∗(tot−siz[son)siz[son...

2019-10-23 21:58:18

BZOJ1226 学校食堂 【状压dp】

WOJ2171SOL就当是复习一下状压dp吧理清楚过程。 相当于有一个最前面的没拿饭的人卡在那里,由于∀ bi≤7\forall \ b_i\le7∀ bi​≤7,我们可以状压最前面的人和他的后面777个人(一共8个人)吃饭没有。由于算代价需要前一个吃饭的人,我们再用题目性质,记录前一个吃饭的人和当前人的相对位置即可。(注意有负数,要整体位移)f[i][...

2019-10-23 20:25:09

BZOJ2037 Sue的小球 【区间dp】

WOJ2039SOL区间dp得好好理解一下了。。我们注意到yyy坐标的限制是不存在的。minimize:Delta=∑t[i]∗v[i]minimize:Delta=\sum t[i]*v[i]minimize:Delta=∑t[i]∗v[i]考虑子问题,按xxx坐标排序后,一段点被走完后只会停在最左端或者最右端,再“扩展段长”不放设:f[0/1][i][j],表示i到j走...

2019-10-21 20:13:02

P2114 [NOI2014]起床困难综合症 【dp】

P2114SOL休闲娱乐玩dp。关于解法,读完题目后写代码就行了。一道有质量的洛谷蓝题CODE#include<bits/stdc++.h>using namespace std;#define sf scanf#define pf printf#define ll long long#define cs const#define db double#de...

2019-10-21 15:15:34

P2150 [NOI2015]寿司晚宴【状压dp】

洛谷P2150SOL两两互质:对于同一个质因数的倍数不能选在同一集合内。状压A,BA,BA,B所选的集合的质因数情况。即为f[S1][S2]f[S_1][S_2]f[S1​][S2​]。预处理出每一个数包含的质因数,也是状压。枚举当前数选在 A或B或不选。{f[i][S1∣k][S2]+=f[i−1][S1][S2]f[i][S1∣k][S2]+=f[i−1][S1][S2]...

2019-10-21 15:04:52

图的存储

1.邻接表: (前向星) 不开O2O_2O2​快一点。可以实现正反边(cntcntcnt从1开始)2.vectorvectorvector,有边权我用结构体 ~~~,开O2O_2O2​快一些。

2019-10-20 20:44:23

2-SAT

Definationk-SAT问题 :通俗的可以理解为, 对于nnn个集合,每个集合有kkk个元素,集合内元素只能有一个为111,集合的元素间有限制。-类型: NP2-SAT:[k==2][k==2][k==2],类型:PAlgorithm1.对每个iii,有i0,i1i_0,i_1i0​,i1​,表示iii选0或1。2.题目的限制(i,ji,ji,j至少一个为1,i,ji,ji...

2019-10-20 19:57:27

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。