wyxdrqc
wyxdrqc
全部文章
分类
未归档(64)
题解(3)
归档
标签
去牛客网
登录
/
注册
wyxdrqc的博客
全部文章
(共67篇)
[十二省联考2019]异或粽子
[十二省联考2019]异或粽子 先吐槽一下,在考场上完全没有将这道题和超级钢琴联系起来,然后\(GG\),喜提\(60\)走人 赛后听说直接上可持久化\(Trie\)用堆维护就好了 然后自己回来又打开了超级钢琴. 这道题就有思路了 很明显,这道题我们可以利用前缀和优化到最大的\(k\)...
2019-04-28
0
322
二维数点问题
二维数点问题 二维数点在OI中有着广泛的应用,很多题目正解或其部分分都可以转化为二维数点的模型. 一般性的静态二维数点问题: 给出平面上的\(n\)个点的坐标\(P_i(x_i,y_i)\),\(Q\)次查询,每次查询\((a,b,c,d)\),表示,求在矩形\((a,b),(c,d)\)中的...
2019-04-04
1
1485
后缀数组复习笔记
[后缀数组复习笔记] 首先推荐一篇写的非常好的Blog,本文中部分内容也会选自该博客。 个人认为后缀数组的核心内容其实就是对\(2^x\)的字符串按照\(2^{x - 1}\)求出的第一第二关键字进行排序.然后进而一步一步对数组进行排序. 所以要用到基数排序: 基数排序在后缀数组中可以在\(...
2019-04-03
0
424
LuoguP3521 [POI2011]ROT-Tree Rotations
P3521 [POI2011]ROT-Tree Rotations 题目大意: 给一棵\((1≤n≤200000)\)个叶子的二叉树,可以交换每个点的左右子树,要求前序遍历叶子的逆序对最少。 我们发现交换两个子树并不会影响某个子树内的逆序对个数,只会对两个子树之间的逆序对产生影响. 所以我们...
2019-04-02
0
427
P2839 [国家集训队]middle
LuoP2839 [国家集训队]middle 主席树好题,点个赞! 这道题让我知道了,主席树不只是维护权值线段树。也是可以去像普通线段树一样操作的. 首先,关于求区间中位数的一个小\(trick\)(反正我之前没听说过) 二分答案 将大于等于\(mid\)的值看做\(1\),小于\(mid\)的看...
2019-04-02
0
336
LuoguP3066 逃跑的BarnRunning Away From…
LuoguP3066 先吐槽一下,这道题名字好长啊 一个非常明显的思路,利用倍增数组不断向上跳.直到数值大于\(L\),然后直接差分统计答案就好了. 这种ZROI也考过,不多赘述了. 我们来考虑主席树做法 我们设\(d_x\)为\(x\)点到跟的距离 让我们求满足\(d_v - d_u<= ...
2019-04-02
0
362
P3567 [POI2014]KUR-Couriers
LuoguP3567 [POI2014]KUR-Couriers 菜死了,竟然没看出来这是一道主席树的模板题.还自己瞎YY了写奇技淫巧。 首先\([l,r]\)这个区间的主席树我们是很好求的。 如果一个数出现的次数严格大于\((r - l + 1) / 2\) 那么,第\((r - l + 1) ...
2019-04-02
0
419
主席树复习笔记
主席树复习笔记 首先简单复习一下之前学过的主席树和线段树合并的题目 因为主席树打的比较熟,所以就稍微简单一些吧。 LuoguP3834 【模板】可持久化线段树 1(主席树) 非常形象的一个图 本质是一颗权值线段树? 我们每次加入一个点,发现最多只有\(log\)个点会受到影响,所以我们就把...
2019-04-01
0
423
LuoguP2765 魔术球问题
LuoguP2765 魔术球问题 首先,很难看出来这是一道网络流题.但是因为在网络流24题中,所以还是用网络流的思路 首先考虑完全平方数的限制。 如果\(i,j\)满足\(i < j\) 且 $i + j \(为完全平方数我们就在\)i - j $连一条有向边 练完之后我们会得到这样一...
2019-04-01
0
326
LuoguP1402 酒店之王
LuoguP1402 酒店之王 最大流题目。带有一定的思维技(tao)巧(lu) 依旧分析题目。如果只有房间或者菜一种限制。那么就是一道裸的最大流了 可是两种条件都应当满足, 这貌似也可以做。 因为每个菜和房间都只能选择一次。我们很容易建出这样一个模型 上图中矩形表示房间,圆表示顾客...
2019-04-01
0
354
首页
上一页
1
2
3
4
5
6
7
下一页
末页