分类 Oi 下的文章:

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

阅读全文>>

4880: [Lydsy2017年5月月赛]排名的战争 排序乱搞
发表于: | 分类:Oi | 评论:0 | 阅读:66
考虑把每个点的$x_1,x_2$都减去选定点的$x_1,x_2$ 然后一切的一切变得和谐了起来…… 把$x_2$看成是纵坐标然后你每次的合法区域就是一个半平面 直接新坐标按照极角排序然后双指针扫扫扫就行了 注意到可能有多点共线甚至有多点重合的情况需要好好特判 #i...

阅读全文>>

4879: [Lydsy2017年5月月赛]失控的数位板 并查集加速染色
发表于: | 分类:Oi | 评论:0 | 阅读:57
开始刷五月月赛找状态 这题的话我们可以考虑这样一个问题,假如我们已经知道了最后一次他被访问的时间,那么显然我们可以列出不等式 一个点如果被访问而且被染色那么显然不染色的时间需要大于等于最后一次访问他的时间 一个点如果没被访问,那么显然不染色的时间需要严格小于最后一...

阅读全文>>

基于变换合并的树上动态 DP 的链分治算法学习笔记
发表于: | 分类:Oi | 评论:0 | 阅读:87
写在前面 这是一篇有关链分治算法的学习笔记……我完全就是照着 immortalCO 论文和 他的博客 里面写的学的 先丢链接immortalCO ,论文的话直接去uoj找17年的集训队论文就好了 不保证都能看懂,不保证看了之后都会…… 建议读不懂论文的可以上这看看...

阅读全文>>

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

阅读全文>>

Title - Artist
0:00

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

TOP