3 Starria

尚未进行身份认证

jloi现役选手 dsfz最低水平

等级
TA的排名 9w+

蒟蒻名曰Starria-博客两周年纪念

「——这是回忆录吗?为什么不写在新博客里?」「——我有一定要发在这里的理由。」

2018-08-16 18:27:34

uoj#397. 【NOI2018】情报中心

uoj#397.【NOI2018】情报中心给出一棵N(≤5×10^4)个点的树,每条边有一个非负边权。再给出树上的M(≤10^5)条链,链有费用。求选出两条边相交的链,它们的并的边权和减去费用之和的最大值。多组数据,ΣN≤10^6+233,ΣM≤2×10^6+233。<del>我好菜啊我好菜啊我套路都不会我暴力都写挂</del>在赛场上获得了和自己水平很相配的5分。

2018-08-10 14:54:06

uoj#189. 【集训队互测2016】火车司机出秦川 //圆方树

uoj#189.【集训队互测2016】火车司机出秦川给出一棵N(≤3×10^5)个点的仙人掌,每条边有一个价值。Q(≤3×10^5)次操作,第i次给出Ki(ΣK≤3×10^5)个点对,询问这些点对间最短或最长路径的并的价值和,每次询问后接一次对一条边价值的修改。保证所有环都是奇环。//小半年前刷专题的时候觉得挺麻烦的就没动…最近想锻炼一下代码能力所以翻出来写了

2018-06-15 15:04:41

uoj#347. 【WC2018】通道 //点分治×虚树

uoj#347.【WC2018】通道给出三棵n(≤10^5)个点的树,边有边权Li(≤10^12),求max1≤i,j≤n(dis1(i,j)+dis2(i,j)+dis3(i,j))。

2018-05-23 20:40:46

loj#122.「强制在线」动态图连通性

loj#122.「强制在线」动态图连通性N(≤5000)个点,M(≤5e5)次操作,支持加边/删边/询问两点间连通性。强制在线。来看题的请向下翻一段。我挂一个人…。

2018-03-26 08:23:58

bzoj4768: wxh loves substring //后缀平衡树

给出一个字符串,要求资瓷:在末尾添加/删除字符;询问一个串的出现次数。原串长与变化长度之和<=800000,询问串总长<=3000000。后缀平衡树的板子题。刚开始以为后缀平衡树是个很厉害的suffixdatastructure…学完后感觉就是拿了个平衡树维护SA?我选择sgt,好写。<del>我可能不会treap</del>

2018-03-08 07:55:37

bzoj4695: 最假女选手 //吉利线段树

bzoj4695:最假女选手给出长为N(≤5e5)的序列,要求支持区间加、区间取min/max、区间求和、区间求min/max。我好久好久以前就想学这个科技…O(nlog^2n)的SegmentTreeBeats!

2018-03-04 16:15:56

bzoj4605: 崂山白花蛇草水 //替罪羊式重构k-d树

bzoj4605:崂山白花蛇草水题意Q(&amp;lt;=100000)次操作,支持:在二维平面上插入一个坐标(x,y)(x,y&amp;lt;=500000),点权为v(&amp;lt;=1e9)的点;查询矩形区域内第K大点权。强制在线。题解今天neither问我在做什么题,我说是一个kdt模板题双log的话空间似乎会炸?所...

2018-02-24 18:35:18

wc2018冲刺期总结

写给自己。写给以后可能会和我有相同经历的oier。prev:「noip2017冲刺期总结」时间:noip2017后~wc2018前(2017.11~2018.2)这次感觉写了一堆无关紧要的东西…当回忆录看吧(雾//整篇都是半夜写的,可能之后要斟酌一下词句改一下?(续)十一月,等到了noip的正式分,发现比民间数据高真是愉悦,然而周围很多oier惨挂,包括一致认为...

2018-02-12 01:07:41

uoj#87. mx的仙人掌 //圆方树或者别的什么东西

uoj#87.mx的仙人掌题意给出一个N(题解既然有官方题解那么就不写题解了。看起来有好多可怕的做法…当作圆方树的模板题写了一发,对圆方树建虚树什么的很妙的样子注意事项邻接表要开到n*4…怎么就记不住呢昨天刚写错一次然后今天又开小了代码放个代码证明今天没有在颓废

2018-01-24 14:24:09

uoj#58./bzoj3052 【WC2013】糖果公园 //树上带修改莫队

uoj#58.【WC2013】糖果公园题意有一棵N(一条路径的权值定义为∑i(Vi∗∑tij=1Wj)\sum_i(V_i*\sum_{j=1}^{t_i}W_j),其中i为路径中出现的不同种类糖果,ti为第i种糖果的出现次数,V和W给定。Q(题解半年前写了一半,然而代码弄丢了。树上莫队和带修改莫队放一起,算是比较

2018-01-17 22:37:47

uoj#57./bzoj3051 【WC2013】平面图 //平面图转对偶图

uoj#57.【WC2013】平面图题意给出由M(Q(要求画一条不经过无界区域或顶点的曲线连接A,B,并使得其横穿的线段权值最大的最小。判断是否有解,输出最优解下经过线段的最大权值。题解这道题的题解还是暑假学网络流的时候看到的…。是一个听起来很高端实际上很暴力的东西。几周前的模拟考了类似的东西,是平面图转对

2018-01-16 22:11:49

uoj#55./bzoj3435 【WC2014】紫荆花之恋 //替罪羊式重构点分树

uoj#55.【WC2014】紫荆花之恋题意N(&lt;=1e5)次操作,第i次操作会把第i个点挂到当前的树上。点有点权Ri,边有边权Ci。求每次操作后满足Ri+Rj&gt;=dis(i,j)的点对(i,j)的个数。强制在线。//想知道那个非常非常短的写法是什么神奇的操作QAQ//我好像只会比较trivial的做法…进入正题。树上路径计数?哇这不是点分治模板题嘛,套个数据结构就好了。如果树的形态不确定呢?

2018-01-16 01:46:44

bzoj3924: [Zjoi2015]幻想乡战略游戏 //动态点分治

bzoj3924:[Zjoi2015]幻想乡战略游戏题意给出一棵N(&amp;amp;lt;=1e5)个点的树。特殊性质:每个点度数不超过20。M(&amp;amp;lt;=1e5)次操作,支持更改一个点的点权,每次操作后输出∑(每个点的点权*该点到带权重心距离)。题解关于找带权重心:规定sum[i]表示点i子树的点权和。如果当前在x...

2018-01-13 16:05:08

bzoj4871: [Shoi2017]摧毁“树状图” //树形dp

bzoj4871:[Shoi2017]摧毁“树状图”题意给出一棵大小为N(<=5e5)的树,求树上两条边不相交路径能把这棵树分成的联通块个数的最大值。在年底之前改完了一道今年省选题xd庆幸这道题出在了我只会暴力的时候…以及,像上次那个寿司餐厅一样,我凭着大半年前的记忆去做这道题,于是又审错了题,写了一个边可以相交的东西…(好在变成边不相交只需要

2017-12-29 17:26:38

bzoj4530: [Bjoi2014]大融合 //线段树分治+并查集

bzoj4530:[Bjoi2014]大融合题意N<=1e5个点,Q<=1e5个操作。支持加一条边(u,v)(保证图是森林)、询问经过边(u,v)的简单路径条数(保证(u,v)存在)。如果不算询问的那条边,那么答案就是当前u的联通块大小*v的联通块大小。所以每条边原本的出现时间(加边的时间~结束)会被询问分隔成几段,所有边的总段数依然是Q级别的。

2017-12-25 17:29:37

uoj#274. 【清华集训2016】温暖会指引我们前行 //LCT

uoj#274.【清华集训2016】温暖会指引我们前行N≤1e5个点,M≤3e5个操作。每条边有一个权值T(保证互异)和一个长度L,资磁加边、改变一条边的L、询问u到v在关于T的最大生成树上的路径长度。这题主要难度大概都在读题上…。lct模板题,维护一下最大生成树即可。txl学长说那个高级的边权lct写法并不比拆点优越到哪里去…所以写了一发边拆点的lct

2017-12-25 08:48:08

bzoj3786: 星系探索 //ETT

bzoj3786:星系探索题意给出一棵有根树,支持更改父节点、子树加权、询问根到某一点路径上的权值和。N≤1e5。题解EulerTourTree的模板。听jcy讲的时候感觉比LCT简单于是写了一发调了两个晚自修…。ETT是用splay维护这棵树的欧拉序,就是形如”1,2,-2,3,-3,-1”这样的每个点正编号在第一次访问到时出现,

2017-12-20 21:41:03

「NOIP2017」列队 //线段树

题意有一个n行m列的方阵,第i行j列的点编号为(i-1)m+j。给出q次操作,每次把第x行y列的点拿出来,然后把这一行它之后的点都向左推,把最后一列x行之后的点都向上推,然后把之前(x,y)的点放到最后一个位置,询问这个点的编号。题解树状数组的做法我不会呀写一写暴力一些的做法吧维护每一行和最后一列,于是需要实现的操作就变成了找到并删掉第k

2017-12-08 23:08:47

noip2017冲刺期总结

//第一次写总结,感觉这种东西好像不是这么写的写给自己。写给以后可能会和我有相同经历的oier。时间:noi2017后~noip2017前(2017.7~2017.11)这一段的主线基本就是寻找文化课和oi的平衡了。七月,中考结束,恢复代码力,认全了现在机房里的人,发现自己其实很弱,而大家都变强了,noi同步赛打了45还是55,听说alone_wolf/ljss/ah...

2017-11-14 19:08:56

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!