1 RHJoi

尚未进行身份认证

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

等级
TA的排名 8w+

LOJ6041雅礼集训 决斗 【贪心】

LOJ6047SOL首先环其实是不存在的。。-重复的会向右边挤,但最后n个都可以一一对应,至少有一条边没有“人员流动”。我们设sumi=∑j=1ideg[j]−1sum_i=\sum_{j=1}^ideg[j]-1sumi​=∑j=1i​deg[j]−1,sumsumsum最小的一个点kkk和下一个点k+1k+1k+1之间没有“人员流动”。从k+1k+1k+1开始,用set维护...

2019-10-18 14:23:50

P2536 [AHOI2005]病毒检测 【LCS型dp】

洛谷P2536SOL在ac自动机上,用fft实现通配符区间匹配?还是别折腾了。咱先看看数据范围:len≤500,n<500len\le500,n\lt500len≤500,n<500,这是啥?一个个匹配就行了。。。思考一下我们刚学dp时的LCSLCSLCS问题,即longest common sequencelongest\common\...

2019-10-16 15:50:13

BZOJ3881 [Coci2015]Divljak 【AC自动机+树上差分】

darkSOL类似于阿狸的打字机?只是这道题需要一个路径并。具体的,对Alice的串建出ac自动机,每次拿新加入的BobBobBob串在上面跑匹配,把所有经过点拿出来,在failfailfail树上给到根的路径打+1+1+1标记。但是多次出现算作一次,所以做一个路径并就可以了。即给点按照failfailfail树上的dfsdfsdfs序排序,在相邻两个点的lcalcalca处减掉...

2019-10-16 14:14:19

LOJ2564 SDOI2018 原题识别【主席树+随机化分析】

loj2564SOL有两个操作,1.树上区间数颜色2.树上n2n^2n2版的操作1。-先放在序列上。操作1:对于每一种颜色,只在其在区间的第一次出现位置统计。我们求出每一个位置对应的颜色的前一次出现位置(记为preprepre)(第一次就是000),放在主席树中即可。操作2,计算每一个点被多少区间访问到。-对于(A,B](A,B](A,B]之间的点ppp,首先pre...

2019-10-15 21:52:21

BZOJ3674 可持久化并查集【主席树+并查集】

BZOJSOL可持久化并查集?难道可持久化非旋treap维护并查集森林?其实没那么麻烦。。可以看做是主席树的应用。从代码的角度思考并查集,我们只需要可持久化fafafa数组即可。这里不进行路径压缩(版本太多,感觉压缩了实测效果也不是那么理想)所以要按秩合并,再用主席树维护一个depdepdep数组即可。CODE/*********************************...

2019-10-14 19:28:55

BZOJ2989 数列【cdq分治】

darkbzojSOL据说可以对修改二进制分组+主席树在线做?学学吧。。。先把曼达顿距离转化成切尔雪夫距离,即:∣x1−x2∣+∣y1−y2∣≤k|x_1-x_2|+|y_1-y_2|\lek∣x1​−x2​∣+∣y1​−y2​∣≤k转化为max(∣x1′−x2′∣,∣y1′−y2′∣)≤kmax(|x_1'-x_2'|,|y_1'-y_2'|)\lekmax(∣x...

2019-10-14 18:19:49

BZOJ2653 middle 【主席树+二分】

BZOJSOL无法确定中位数?我们可以考虑转化思路。二分一个中位数,再判断是否合理。根据本题中中位数的定义,只需要小于它的数的个数≤∣len2∣\le|{len\over2}|≤∣2len​∣。我们可以将大于iii的数赋值成111,小于的赋值成−1-1−1。若maxLsum[a,b−1]+sum[b,c]+maxRsum[c+1,d]≥0若maxLsum[a,b-1]+s...

2019-10-14 16:44:06

BZOJ3339 Rmq Problem【离线/可持久化数据结构】

DarkbzojSOL法一:维护每一个值在原序列的最右出现位置的最小值,对于二分的左半部分,如果最小值大于等于当前左端点,说明已满。用主席树排除右端点超出qr的影响。在主席树上二分法二:增量法思想。从[l,r]到[l+1,r],只有a[l]可能能够拿来更新一段区间的mex,写一个以左端点为第一维的支持区间修改min,单点查询(可持久化标记)的主席树。(也可以离线,用线段树做)...

2019-10-14 16:25:22

【LOJ575】「LibreOJ NOI Round #2」不等关系 【容斥+分治NTT】

LOJ575SOL1,将原序列看成一段一段的连续的小于符号的区间(数字单增)。2,不考虑大于符号,方案数为n!∏leni!{n!\over\prodlen_i!}∏leni​!n!​;3,加入大于符号的影响。设f[i]:前i个元素的合法序列的方案数f[i]:前i个元素的合法序列的方案数f[i]:前i个元素的合法序列的方案数从最近的一段单增区间枚举,即枚举最近的大于符号的位置,...

2019-10-11 20:22:57

P5331[SNOI2019]通信【费用流+优化建图】

题面SOL首先去确定用费用流求解。对于每一个点的贡献,只和向谁连边有关,和后面的点无关。所以把每个点拆成入点,出点。1.将S和入点连边,cap=1,w=0cap=1,w=0cap=1,w=02.入点和T连一边,cap=1,w=Wcap=1,w=Wcap=1,w=W3.出点和T连边:cap=1,w=0cap=1,w=0cap=1,w=04.入点和前i−1i-1i−1个点的出点连...

2019-10-10 11:56:42

P3703 [SDOI2017] 树点涂色 【LCT+dfs序+线段树】

题面SOL维护颜色集合?树上莫队?好像做不了3操作,只有30分。。。仔细思考op1op1op1,若进行链修改,相当于把xxx到根路径拼成了一段,一开始点iii到根的权值为dep[i]dep[i]dep[i],相当于每一个点都是独立的一段。那么点到根的权值就是该路径上的“总段数”。但是我们还是不能快速处理op1op1op1。思考LCTLCTLCT的accessaccessaccess,...

2019-10-04 20:56:17

loj2552 [CTSC2018] 假面 【概率dp】

题面SOL做法貌似挺多?(比如多项式)比较水的一道模拟型的概率dp;首先我们read the problemread\the\problemread the problem,然后make a draftmake\a\draftmake a draft,然后ACACAC。其实中间背包dp的...

2019-09-29 18:25:11

P2056 [ZJOI2007] 捉迷藏 【动态点分治】

题面SOL树的直径?如果有∣S∣≤1e6|S|\le1e6∣S∣≤1e6之类的,说不定可以虚树做。然鹅并没有。另一种O(nlogn)O(nlogn)O(nlogn)讨论完树中所有路径的做法当然是点分治了。只是此题需要支持修改,于是记录一下点分治时候的fafafa,每个分治重心维护一个数据结构,我们便有了一个O(nlogn+mlog2n)O(nlogn+mlog^2n)O(nlogn...

2019-09-29 14:41:06

Loj3087 [GXOI / GZOI2019] 旅行者 【最短路扩展】

题面SOL法一:二进制分组O(mlog2n)O(mlog^2n)O(mlog2n)预计得分:50-60按二进制每一位0/1将特殊点分成两组,一组跑最短路,一组统计。一次的答案为两组之间的最小值。由于任意两个不同的数,二进制总有一位不同,所以总有一个分组方式能够将两个特殊点分开。法二:两次最短路+染色O(mlogn)O(mlogn)O(mlogn)预计得分:100把特殊...

2019-09-25 19:05:28

[SHOI2012]随机树 洛谷P3803 【期望dp】

题面SOL分两个问题讨论;Q1:显然的期望dp定义式:f[i]:第i步的期望平均叶子深度f[i]:第i步的期望平均叶子深度f[i]:第i步的期望平均叶子深度,转移方程:f[i]=f[i−1]∗(i−1)+f[i−1]+2i,−>f[i]=f[i−1]+2i.{f[i]={f[i-1]*(i-1)+f[i-1]+2}\over{i}},->f[i]=f[i-1]+{2\o...

2019-09-22 21:03:50

bzoj2400 Optimal Marks 【最小割】

darkSOL1.异或运算按位分开。2.0/1,想办法转化为最小割问题。可以看做把点分为两个0/1集合,如果有一条路径两端有确定的点,中间必定会产生"1"的代价,相当于割开此边的代价。3.建图,<u,v>=add(u,v,1),add(v,u,1)<u,v>=add(u,v,1),add(v,u,1)<u,v>=add(u,v,1),add(v,u...

2019-09-17 20:33:40

LOJ3110 SDOI[2019]快速查找【模拟】

传送门SOL输入有点复杂,仔细读完后发现不同的操作最多只有1e51e51e5种,离散化线段树算出来都2e82e82e8,更不要说大常数,TLETLETLE是无疑的。(好像有人用平衡树AAA了?)分析发现除了单点赋值,查值,其余都是全体的操作,可以O(1)O(1)O(1)做。对于赋值,有((x+b1)∗a1+b2)∗a2...=x∗a1∗a2∗...+K,K与x无关((x+b_1)*a_...

2019-09-16 22:44:26

SCU 4444 Travel 【次完全图最短路】

vjudge题面地址SOL对于a<b and Link[1][n]==0a<b\and\Link[1][n]==0a<b and Link[1][n]==0,对m条边正向bfs即可;对于a>b and Link[1][n]==1a>b\and\Link[...

2019-09-16 09:42:54

虚树【学习笔记】

个人觉得“手推”+代码阅读即可理解;故给出模板如下:inlinevoidinsert(intu){ if(!top){stk[++top]=u;return;} intlca=Lca(stk[top],u); if(stk[top]^lca){ //u在另一个子树里 while(top>1&&dfn[lca]<=dfn[stk[top-1]])...

2019-09-11 19:55:32

CF 377D Developing Game 【思维+线段树+扫描线】

传送门SOLLmax≤Vmin,Vmax≤Rmin;Lmax\leVmin,Vmax\leRmin;Lmax≤Vmin,Vmax≤Rmin;equals Exist P(x,y),L≤xP≤V,V≤yP≤R.equals\Exist\P(x,y),L\lex_P\leV,V\ley_P\leR.equals Exist P(x,y),...

2019-08-25 20:44:52

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。