标签 数据结构 下的文章:

4825: [Hnoi2017]单旋 线段树
发表于: | 分类:Oi | 评论:0 | 阅读:126
我去了 我服了这题了……考试的时候肯定稳妥50滚粗了…… 从下午两点想到晚上七点然后发现了一个非常显而易见的性质,然后巧妙的避开了所有需要维护原树的东西23333333,累死我了…… 首先通过撕烤容易发现一次单旋只会让除了他右子树的所有点的深度+1,右子树的点的深...

阅读全文>>

BZOJ 4826: [Hnoi2017]影魔 线段树 离线 扫描线
发表于: | 分类:Oi | 评论:0 | 阅读:164
我们先来分析一下题吧 = = 首先看到最大值最小值我们枚举一下嘛 …… 从大到小枚举一下最大值,然后我们得到每个权值的控制区间,考虑区间左右两个数字必然是第一个比他大的数字,假设位置分别是 $L,R$ 最大值所在位置是 $pos$ 然后……然后讨论一下嘛,$(L,...

阅读全文>>

4538: [Hnoi2016]网络 线段树套堆+标记永久化+树链剖分
发表于: | 分类:Oi | 评论:0 | 阅读:156
傻逼bz,卡我做法,毁我青春 听说要做数据结构题,直接手动@BZOj hnoi2016 做这题你需要一点创新的精神,你需要把不在这条链上的信息存储在这条链上 然后……说到这应该都会了吧 树链剖分线段树,每个节点挂一个支持删除操作的堆作为标记,由于每次删除标记的区间...

阅读全文>>

BZOJ 1835: [ZJOI2010]base 基站选址 dp + 线段树优化
发表于: | 分类:Oi | 评论:0 | 阅读:130
浙江题里面最可做的一道QwQ 首先你需要一个$O(n^2*K)$的$dp$ $f(i,j)$ 表示当前基站是第$j$个基站,然后他建在了位置$i$ 显然有一个通俗易懂的转移方程$f(i,j) = f(k,j-1)+calc(j+1,i-1)$ $calc(j+1,...

阅读全文>>

BZOJ 4561: [JLoi2016]圆的异或并 扫描线+平衡树
发表于: | 分类:Oi | 评论:0 | 阅读:142
开始做去年的省选题,有的题有点思路了,但是还是有的题目一脸懵逼 这题告诉你圆圆之间不相交,然后这题就有了一个优美的性质,就是在不加入新远且没有圆退出的情况下,他们的上下关系是绝对不会改变的 然后……然后就好办了吗,维护一条从左到右的扫描线,然后用一个treap维护...

阅读全文>>

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP