wyxdrqc

未归档

题解(3)

/ 注册

全部文章 / 未归档（共64篇）

LuoguP3521 [POI2011]ROT-Tree Rotations

P3521 [POI2011]ROT-Tree Rotations 题目大意：给一棵\((1≤n≤200000)\)个叶子的二叉树，可以交换每个点的左右子树，要求前序遍历叶子的逆序对最少。我们发现交换两个子树并不会影响某个子树内的逆序对个数,只会对两个子树之间的逆序对产生影响. 所以我们...

2019-04-02

0 506

P2839 [国家集训队]middle

LuoP2839 [国家集训队]middle 主席树好题,点个赞！这道题让我知道了,主席树不只是维护权值线段树。也是可以去像普通线段树一样操作的. 首先,关于求区间中位数的一个小\(trick\)(反正我之前没听说过) 二分答案将大于等于\(mid\)的值看做\(1\)，小于\(mid\)的看...

2019-04-02

0 429

LuoguP3066 逃跑的BarnRunning Away From…

LuoguP3066 先吐槽一下,这道题名字好长啊一个非常明显的思路,利用倍增数组不断向上跳.直到数值大于\(L\),然后直接差分统计答案就好了. 这种ZROI也考过,不多赘述了. 我们来考虑主席树做法我们设\(d_x\)为\(x\)点到跟的距离让我们求满足\(d_v - d_u<= ...

2019-04-02

0 446

P3567 [POI2014]KUR-Couriers

LuoguP3567 [POI2014]KUR-Couriers 菜死了,竟然没看出来这是一道主席树的模板题.还自己瞎YY了写奇技淫巧。首先\([l,r]\)这个区间的主席树我们是很好求的。如果一个数出现的次数严格大于\((r - l + 1) / 2\) 那么,第\((r - l + 1) ...

2019-04-02

0 505

主席树复习笔记

主席树复习笔记首先简单复习一下之前学过的主席树和线段树合并的题目因为主席树打的比较熟,所以就稍微简单一些吧。 LuoguP3834 【模板】可持久化线段树 1（主席树）非常形象的一个图本质是一颗权值线段树？我们每次加入一个点,发现最多只有\(log\)个点会受到影响,所以我们就把...

2019-04-01

0 497

LuoguP2765 魔术球问题

LuoguP2765 魔术球问题首先,很难看出来这是一道网络流题.但是因为在网络流24题中，所以还是用网络流的思路首先考虑完全平方数的限制。如果\(i,j\)满足\(i < j\) 且 $i + j \(为完全平方数我们就在\)i - j $连一条有向边练完之后我们会得到这样一...

2019-04-01

0 385

LuoguP1402 酒店之王

LuoguP1402 酒店之王最大流题目。带有一定的思维技(tao)巧(lu) 依旧分析题目。如果只有房间或者菜一种限制。那么就是一道裸的最大流了可是两种条件都应当满足，这貌似也可以做。因为每个菜和房间都只能选择一次。我们很容易建出这样一个模型上图中矩形表示房间，圆表示顾客...

2019-04-01

0 420

luoguP4313 文理分科

luoguP4313 文理分科复习完之后做了道典型题目。这道题条件有点多我们逐个分析如果没有\(sameart\)或者\(samescience\)的限制,就是一个裸的最大权闭合子图的问题了但是再考虑有的话（其实还是一个最大权闭合子图）很明显我们还是可以按照套路分成两个集合....

2019-04-01

0 395

简单最大流/最小割复习

网络流复习笔记主要用来复习一下自己之前学过的网络流。因为当时都是直接抄的题解,莫得印象。所以写篇博客加强记忆。最大流 LuoguP3254 圆桌问题先分析题目。比较明显，如果我们用网络流的思路去分析这个问题。将会将每个单位和每个餐桌都看做点。然后由于每个单位的人理论上可以坐在任...

2019-04-01

0 517

3.31考试总结

3.31考试题解及总结 Noip难度的题目还翻车，真的是菜出了天际。自己最近思维出现问题.静不下心来 T1 很明显的套路题，转化为差分数组.我们可以花费\(1\)的代价来对一个一个位置\(+1\)另一个位置\(-1\).最后统计一下大于\(k\)的之和与小于\(-k\)的差值之和取个\(max...

2019-03-31

0 429