- 博客(40)
- 收藏
- 关注
RSS订阅原创 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
1323
1
原创 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
855
原创 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
886
原创 loj#122.「强制在线」动态图连通性
loj#122. 「强制在线」动态图连通性 N(≤5000)个点，M(≤5e5)次操作，支持加边/删边/询问两点间连通性。 强制在线。 来看题的请向下翻一段。 我挂一个人…。
2018-03-26 08:23:58
31911
1
原创 bzoj4768: wxh loves substring //后缀平衡树
给出一个字符串，要求资瓷：在末尾添加/删除字符；询问一个串的出现次数。原串长与变化长度之和<=800000，询问串总长<=3000000。后缀平衡树的板子题。刚开始以为后缀平衡树是个很厉害的suffix data structure…学完后感觉就是拿了个平衡树维护SA？我选择sgt，好写。<del>我可能不会treap</del>
2018-03-08 07:55:37
1039
原创 bzoj4695: 最假女选手 //吉利线段树
bzoj4695: 最假女选手 给出长为N(≤5e5)的序列，要求支持区间加、区间取min/max、区间求和、区间求min/max。 我 好久好久以前 就想学这个科技… O(nlog^2n)的SegmentTreeBeats!
2018-03-04 16:15:56
1232
3
原创 bzoj4605: 崂山白花蛇草水 //替罪羊式重构k-d树
bzoj4605: 崂山白花蛇草水 题意 Q(<=100000)次操作，支持： 在二维平面上插入一个坐标(x,y)(x,y<=500000)，点权为v(<=1e9)的点； 查询矩形区域内第K大点权。 强制在线。 题解 今天neither问我在做什么题，我说是一个kdt模板题 双log的话空间似乎会炸？ 所...
2018-02-24 18:35:18
530
原创 wc2018冲刺期总结
写给自己。 写给以后可能会和我有相同经历的oier。prev: 「noip2017冲刺期总结」 时间：noip2017后~wc2018前（2017.11~2018.2） 这次感觉写了一堆无关紧要的东西…当回忆录看吧（雾 //整篇都是半夜写的，可能之后要斟酌一下词句改一下？ （续）十一月，等到了noip的正式分，发现比民间数据高真是愉悦，然而周围很多oier惨挂，包括一致认为...
2018-02-12 01:07:41
1413
10
原创 uoj#87. mx的仙人掌 //圆方树或者别的什么东西
uoj#87. mx的仙人掌 题意 给出一个N( 题解 既然有官方题解那么就不写题解了。 看起来有好多可怕的做法… 当作圆方树的模板题写了一发，对圆方树建虚树什么的很妙的样子 注意事项 邻接表要开到n*4…怎么就记不住呢 昨天刚写错一次 然后今天又开小了 代码 放个代码证明今天没有在颓废
2018-01-24 14:24:09
718
原创 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
588
原创 uoj#57./bzoj3051 【WC2013】平面图 //平面图转对偶图
uoj#57. 【WC2013】平面图 题意 给出由M( Q( 要求画一条不经过无界区域或顶点的曲线连接A,B，并使得其横穿的线段权值最大的最小。 判断是否有解，输出最优解下经过线段的最大权值。 题解 这道题的题解还是暑假学网络流的时候看到的…。 是一个听起来很高端实际上很暴力的东西。 几周前的模拟考了类似的东西，是平面图转对
2018-01-16 22:11:49
753
原创 uoj#55./bzoj3435 【WC2014】紫荆花之恋 //替罪羊式重构点分树
uoj#55. 【WC2014】紫荆花之恋题意 N(<=1e5)次操作，第i次操作会把第i个点挂到当前的树上。点有点权Ri，边有边权Ci。求每次操作后满足Ri+Rj>=dis(i,j)的点对(i,j)的个数。强制在线。//想知道那个非常非常短的写法是什么神奇的操作QAQ//我好像只会比较trivial的做法…进入正题。树上路径计数？哇这不是点分治模板题嘛，套个数据结构就好了。如果树的形态不确定呢？
2018-01-16 01:46:44
776
6
原创 bzoj3924: [Zjoi2015]幻想乡战略游戏 //动态点分治
bzoj3924: [Zjoi2015]幻想乡战略游戏 题意 给出一棵N(&lt;=1e5)个点的树。 特殊性质：每个点度数不超过20。 M(&lt;=1e5)次操作，支持更改一个点的点权，每次操作后输出∑(每个点的点权*该点到带权重心距离)。 题解 关于找带权重心： 规定sum[i]表示点i子树的点权和。 如果当前在x...
2018-01-13 16:05:08
585
原创 bzoj4871: [Shoi2017]摧毁“树状图” //树形dp
bzoj4871: [Shoi2017]摧毁“树状图” 题意 给出一棵大小为N(<=5e5)的树，求树上两条边不相交路径能把这棵树分成的联通块个数的最大值。 在年底之前改完了一道今年省选题xd 庆幸这道题出在了我只会暴力的时候… 以及，像上次那个寿司餐厅一样，我凭着大半年前的记忆去做这道题，于是又审错了题，写了一个边可以相交的东西…（好在变成边不相交只需要
2017-12-29 17:26:38
1235
1
原创 bzoj4530: [Bjoi2014]大融合 //线段树分治+并查集
bzoj4530: [Bjoi2014]大融合 题意 N<=1e5个点，Q<=1e5个操作。 支持加一条边(u,v)（保证图是森林）、询问经过边(u,v)的简单路径条数（保证(u,v)存在）。 如果不算询问的那条边，那么答案就是当前u的联通块大小*v的联通块大小。所以每条边原本的出现时间（加边的时间~结束）会被询问分隔成几段，所有边的总段数依然是Q级别的。
2017-12-25 17:29:37
543
原创 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
643
3
原创 bzoj3786: 星系探索 //ETT
bzoj3786: 星系探索 题意 给出一棵有根树，支持更改父节点、子树加权、询问根到某一点路径上的权值和。 N≤1e5。 题解 Euler Tour Tree的模板。 听jcy讲的时候感觉比LCT简单 于是写了一发 调了两个晚自修…。 ETT是用splay维护这棵树的欧拉序，就是形如”1,2,-2,3,-3,-1”这样的 每个点正编号在第一次访问到时出现，
2017-12-20 21:41:03
624
1
原创 「NOIP2017」列队 //线段树
题意有一个n行m列的方阵，第i行j列的点编号为(i-1)m+j。给出q次操作，每次把第x行y列的点拿出来，然后把这一行它之后的点都向左推，把最后一列x行之后的点都向上推，然后把之前(x,y)的点放到最后一个位置，询问这个点的编号。题解树状数组的做法我不会呀 写一写暴力一些的做法吧维护每一行和最后一列，于是需要实现的操作就变成了找到并删掉第k
2017-12-08 23:08:47
1333
原创 noip2017冲刺期总结
//第一次写总结，感觉这种东西好像不是这么写的 写给自己。 写给以后可能会和我有相同经历的oier。时间：noi2017后~noip2017前（2017.7~2017.11） 这一段的主线基本就是寻找文化课和oi的平衡了。 七月，中考结束，恢复代码力，认全了现在机房里的人，发现自己其实很弱，而大家都变强了，noi同步赛打了45还是55，听说alone_wolf/ljss/ah...
2017-11-14 19:08:56
930
1
原创 bzoj3698: XWW的难题 //有上下界有源汇最大流
bzoj3698: XWW的难题 给出一个N(<=100)*N正实数矩阵，保证除最后一行，每一行的最后一个数等于这一行前面的数之和；除最后一列，每一列的最后一个数等于这一列前面的数之和。要求对矩阵里的每一个元素进行上/下取整，使取整后矩阵依然满足该性质且元素和最大。 考虑每行每列建点的经典建图。 源点向每一行连边，下界为该行元素和下取整，上界为该行元素和上取
2017-10-09 13:57:14
617
1
原创 bzoj3944: Sum//杜教筛
bzoj3944: Sum前几天的blog，没写完，现在补上吧…题意求莫比乌斯函数和欧拉函数的前缀和。N<=2^31-1。T(<=10)组询问。题解杜教筛。然而这篇博客不是写题解的。这主要是因为1.网上有很多详细题解。2.不想打公式。 3.表达能力拙计。
2017-09-14 20:46:32
407
原创 bzoj4873: [Shoi2017]寿司餐厅
bzoj4873: [Shoi2017]寿司餐厅 题意 有n(<=100)种寿司，可以选择任意段连续的寿司，每次得到的美味度是该段所有子区间美味度之和。如果选取了第i种寿司，需要付出代价Ai。对于一个区间，无论被取多少次，其美味度只计算一次。花费同理。当m（一个常数）=1时，如果有代号为x的寿司被选取，需额外花费m*x²。
2017-09-11 18:06:05
566
原创 bzoj2879: [Noi2012]美食节
bzoj2879: [Noi2012]美食节 有n(<=40)道菜，第i道菜被点了pi(∑p<=800)次;有m(<=100)个人，第i个人做第j道菜用时tij(<=1000)，每人同时只能做一道菜，求所有菜需等待时间和的最小值。（这个题意好差啊 还是去看题面吧…题面也不长的说） 背景 今天noip模拟的T3…算错复杂度，以为很简单，想多路增广，调了2h整
2017-09-09 16:51:21
415
原创 bzoj3630: [JLOI2014]镜面通道
bzoj3630: [JLOI2014]镜面通道题意： n(<=300)个圆形或矩形光学元件组成一个镜面通道，求使光能够从一端射到另一端所需要去除的光学元件最小数目。题解 这题好妙啊……。听讲的时候一脸懵，原来还能这样的嘛…… 说是有一个类似【水能流过的地方，光也能经过】的定理。好感性啊（ 再感性一点地说，光学元件中间要有空隙。 再再感性一点地说，上下两个镜面不能由光学元件连通。
2017-08-08 23:05:25
710
3
原创 bzoj4557: [JLoi2016]侦察守卫
bzoj4557: [JLoi2016]侦察守卫 题意：给出一棵n(<=5e5)个点的树，可以选一些点放置守卫，覆盖与其距离不超过d(<=20)的所有点。每个点放置守卫有一定代价。给出m(<=n)个指定点，求所有指定点被覆盖的最小代价。 题解 我们感性地跑这样一个dp： · dp[i][d]表示以i为根的子树中，指定点被完全覆盖的最小代价。 · dp[i][d-j]表示
2017-08-05 21:13:41
1013
原创 bzoj3258: 秘密任务 （+一百题感言？）
bzoj3258: 秘密任务 题意：n<=400个点，m<=4000条边，可以在每条边的起点或终点截断这条边。求截断所有1到n最短路径的最小花费，以及方案是否唯一。显然是个最小割的模型。按照题意跑一遍最短路，把不在最短路里的边删掉，其他的拆成两条边，流量分别赋起点和终点的费用，跑最大流，第一问结束。有关最小割是否有唯一方案，参考了这个blog↓
2017-07-14 14:59:33
630
4
原创 bzoj1187: [HNOI2007]神奇游乐园 & bzoj2310: ParkII
bzoj1187: [HNOI2007]神奇游乐园 题意：在n*m的网格图内找一条简单回路使经过的权值和最大，n<=100，m<=6。 [bzoj2310: ParkII] 题意：在n*m的网格图内找一条简单路径使经过的权值和最大，n<=100，m<=8。 非常典型的插头dp。 逐格转移，根据j和j+1位置的插头情况分类讨论。t1在形成一条回路并且没有其他插头的时候记录……
2017-01-17 16:05:17
866
原创 bzoj1327: The Rotation Game
bzoj1327: The Rotation Game bz的这个题面啊。……是不是全世界只有我不知道要输出No moves needed…… 题解 传说中名为IDA*的剪枝暴搜。 判断一下中间八个格子里最多数字的数量，如果8-这个数要大于深度限制，说明理想情况下这一次也不会出解，于是可以剪掉了。 代码 代码非常丑。 非常丑。
2017-01-12 15:33:32
665
原创 bzoj1687: [Usaco2005 Open]Navigating the City 城市交通
bzoj1687: [Usaco2005 Open]Navigating the City 城市交通 输出方案bfs。刷一刷usaco增加信心。
2016-10-10 16:42:16
674
2
原创 bzoj4196: [Noi2015]软件包管理器
bzoj4196: [Noi2015]软件包管理器 一眼链剖，然而不知道为什么写得很长/写得很差
2016-10-10 12:55:47
644
1
原创 bzoj4195: [Noi2015]程序自动分析
bzoj4195: [Noi2015]程序自动分析 一次TLE：少个分号。 一次WA：e=0和e=1整个看反了。 这个故事告诉我们，不要被水题淹没不知所措。我们要认认真真地把它看完，哪怕它是道裸的并查集。
2016-10-01 21:57:44
645
原创 bzoj3675: [Apio2014]序列分割
bzoj3675: [Apio2014]序列分割 二维斜率优化DP。 首先手算一下就会发现，对于某种分割方法，计算顺序不影响结果。既然这样可以简化成简单DP。考虑f[i][j]表示前i个数分割j次的最大值，s[i]维护从1到i的前缀和，则f[i][j]=min(f[k][j-1]+s[k]*(s[i]-s[k]))。上斜率优化即可。另外，因为0会导致点重合，所以输入的时候忽略0。
2016-10-01 16:44:05
744
1
原创 bzoj1076: [SCOI2008]奖励关
bzoj1076: [SCOI2008]奖励关 看数据范围直接状压DP。偶尔写了个递归的居然还WA了一次真是sad 题解 类似背包的感觉…… 对于每一种状态的每一步，对每个东西选（合法时）与不选的最大期望求和，最后/n就可以了。
2016-09-18 21:09:41
1177
原创 bzoj1060: [ZJOI2007]时态同步
bzoj1060: [ZJOI2007]时态同步 有生之年可以见到一道裸的树DP真是幸运。 A了以后翻状态忽然发现有个代码长一样的，看了一眼是隔壁ljss神犇…… 题解 发现不会写题解，可能是因为太水了 mxlen[i]记录以i为根子树所需的时间。dfs即可。
2016-09-16 10:32:48
801
原创 bzoj1013: [JSOI2008]球形空间产生器sphere
bzoj1013: [JSOI2008]球形空间产生器sphere 想了想既然写了就发上来吧。题解 展开距离公式变成n元一次方程组，直接高斯消元即可，保证有解。
2016-09-15 23:32:20
803
原创 bzoj1033: [ZJOI2008]杀蚂蚁antbuster
[bzoj1033]:[ZJOI2008]杀蚂蚁antbuster 一道可以用来锻炼代码力的模拟。 也可能只是因为我太弱了。
2016-09-15 23:14:19
1322
6
原创 bzoj1798: [Ahoi2009]Seq 维护序列seq
bzoj1798: [Ahoi2009]Seq 维护序列seq 又一道裸线段树。 交过去一直RERERE，调了半天发现把叶子节点pushdown了可不RE。真是代码力低下。 直接上AC代码。 代码
2016-08-17 14:50:30
532
原创 bzoj1036: [ZJOI2008]树的统计Count
bzoj1036: [ZJOI2008]树的统计Count 树链剖分裸题，水到觉得发上来不太好。
2016-08-16 18:51:14
572
原创 bzoj1858: [Scoi2010]序列操作
bzoj1858: [Scoi2010]序列操作 一道裸线段树。的确是比较好想，然而代码写得莫名丑，于是调了很长时间。 维护区间中1的总数，左起连续1的个数，右起连续1的个数，最大连续1的个数，0同理。更新的时候左起连续1（0）要考虑左区间全为1（0）延伸到右区间的情况，右起同理。最大连续考虑左区间的右连续+右区间的左连续情况。标记打区间填充和取反。
2016-08-16 12:04:38
782
3
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人