标签 线段树 下的文章:

4881: [Lydsy2017年5月月赛]线段游戏 线段树 二分图判定
发表于: | 分类:Oi | 评论:0 | 阅读:67
首先我们对于相交的两条线段之间连一条边然后考虑检验生成的图形是否是二分图 这个原理就是考虑我们取出的东西必然在一侧,否则必然相交,如果不是二分图就说明形成的奇环中必然会使得取出的边相交 然后就是怎么快点二分图染色的问题了 考虑大力线段树,每次找出可能符合条件的两个...

阅读全文>>

BZOJ 4911: [Sdoi2017]切树游戏 基于变换合并的树上动态 DP 的链分治算法 树链剖分 线段树 树形dp
发表于: | 分类:Oi | 评论:0 | 阅读:80
跪烂 immortalco 这题的话我们直接链分治就行了,完全是那个动态链分治做法的套路 注意到需要算异或所以套个$FWT$就行了 复杂度爆炸,有关链分治的简单讲解戳这里就行了链分治 一个细节是0没有逆元所以单独记录一下0的个数就行了,关于0的运算可以看里面的 d...

阅读全文>>

BZOJ 4127: Abs 树链剖分 线段树
发表于: | 分类:Oi | 评论:0 | 阅读:63
最近主攻tc已经快一周没写数据结构了qwq,写的脑袋疼然后回BZ找几道傻题写写 直接考虑序列这玩意咋做就行了剩下的就是强行套树剖 因为加的数字都是正的。考虑在修改的时候如果当前区间的负数的最大值+要加的数字>0就递归左右区间修改,否则直接打标记,分正负讨论即...

阅读全文>>

4707: B君的技巧 DP
发表于: | 分类:Oi | 评论:0 | 阅读:67
非常神奇的一个dp 首先我们完全不要考虑在这个矩阵上划范围dp,这个思路会陷入瓶颈然后无法解决 把矩阵作为正常的权值矩阵然后考虑直接在值域区间上大力dp 注意到一个非常奇怪的约定是他们二进制上的第$k$位必须是完全相同的,然后由于这个更大的块也会满足这个所以其实是...

阅读全文>>

BZOJ 4644: 经典傻逼题 线性基 线段树
发表于: | 分类:Oi | 评论:0 | 阅读:68
经典傻*题 我刚开始的时候以为所选的点必须是连在一起的然后就YY了一个无向图最大割,后来发现根本不对,然后再看一遍题发现和割其实一点关系都没有233333333 我们把一个点的点权设置成连在他身上的所有边的边权的异或,那么显然这个东西求的其实就是最大异或和,如果一...

阅读全文>>

Title - Artist
0:00

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

TOP