2 Andres_Lionel

尚未进行身份认证

我要认证

谁无暴风劲雨时,守得云开见日明!

等级
TA的排名 2k+

Flower【HDU-6849】【动态点分治+树状数组】

2020 Multi-University Training Contest 7 F题 有一个N个点的树,给予其中M个操作,每次选其中一个点x,{x, r, v},给它一个影响范围为r的权值为v的值,我们现在想要选取最多的权值点,使得两两之间是没有可重叠区间的。 这个问题画在一维平面上其实很好做,也就是对于一段排序,然后维护的就是一个线段树优化dp,当我们选取这个点pos的时候,我们只能选择的点,或者说,我们假设在中,如果选择其他的更优,那么,我们可以不将这个点加进我们所选的集合中去。 于...

2020-08-12 17:16:07

[SDOI2017]树点涂色【LCT的Access函数的妙用】

题目链接 有一颗有根树,1为根节点,有这样的操作:我们给从1~x的节点染色成相同且未出现过的颜色,现在我们想知道u到v的简单路径上不同颜色的个数、或者u的子树下到根节点颜色数最多的颜色数是多少? 其实,我一开始没有往LCT想,但是它非要挂了个标签,于是开始想了,如果说我们将1号节点默认成根节点,并且是整棵LCT树上的根节点,那么,如果一开始将所有的节点看成是独立的Splay树上的节点,每棵Splay树上有且只有一个点。那么,颜色的个数,实际上就是它到根节点需要Access的次数,并且可以换一种表..

2020-08-10 10:36:22

[BJOI2014]大融合【LCT维护子树信息】

题目链接 本题保证不会构成环。——此为前提 然后操作是查询,或者接上一条边(保证之前两点不连通)。 好了,接下去就是正经事儿了,在此之前,已经有了利用LCT来维护树链信息了,现在只要在这基础上稍加改变,就可以维护某点(也可以是不定根)的子树信息了。 我们知道,改变LCT树的连接关系,只会在Access、link、cut这几种操作为基础的操作上,因为我们知道LCT树为多个Splay树的森林,他们通过虚链进行连接,先来举例一下Access时候。Access函数与子树关系 正常写...

2020-08-07 21:27:03

[WC2006]水管局长【LCT】

题目链接 就是说,有个水管(人),他要打开水管(物),使得水能从u流到v,然后每个水管打开需要时间,问能让水从u流到v,最少需要的时间,那么其实也就是路径上水管的最大时间了,现在我们要让这个最大值最小。 但是,有删除操作诶!那么,既然删除不会重复,我们不妨把删除当作插入来做,除了永久边以外,剩下的边从时间戳从后往前插入,不就相当于是删除了。 于是,实际上还是维护一个最小权生成树了,遇到一条边可以替换环上的最大边,就直接替换了,这样贪心的去找,就可以了。#include <ios...

2020-08-07 16:22:21

[NOI2014]魔法森林【LCT】

题目链接 有N个点,M条边,要使得从1点到N点的(最低要求ai和最低要求bi)的和最小,问最小和。 那么,很显然的,就是求一个联通关系,与最短路无关,因为限制条件不唯一,需要同时限制ai和bi,所以我们不妨枚举一维,然后再是维护一维。 我们对A关键字进行升序处理,然后我们维护一棵B关键字的最小生成树,然后枚举这样的最小生成树的答案不就可以了吗? 我们不断的进行加边操作,然后对B关键字操作,每次看新的B能否替换之前的B树,这就是我们维护的最小生成树了,然后更新答案即可。 更新答案...

2020-08-07 14:21:20

[SDOI2008]洞穴勘测【LCT维护联通关系】

题目链接 LCT判断两点联通的这样的一个基础问题,因为不存在环,所以直接LCT维护连接关系即可。#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#include <algorithm>#include <limits>#include <vector>#incl.

2020-08-07 09:04:29

Fragrant numbers【DP打表】

题目链接题意:用无限长的“1145141919”经过加、乘、括号、直接组成数字这四类方法用最短的前缀组成规定的数字。 首先,用dfs爆搜来进行初步估算,可以看出答案不会超过11,或者用穷举答案来看,如果存在非“3、7”的“-1”项,说明答案错了,扩大来看就可以了。 于是,我们就可以推个dp来进行打表了,我们用表示,来表示区间中,是否可以组成权值k的答案,然后我们推这样的一个区间dp就可以了。打表程序:#include <iostream>#include <..

2020-08-06 21:05:45

[HNOI2010]弹飞绵羊【LCT】

题目链接 很明显,如果和下一个弹到的节点连接一条边的话,那么就会形成一棵森林,我们要求的答案实际上就是它父亲节点的个数+1,但是维护一个森林,我们还需要存储每个森林的位置,比较的麻烦了,所以我们不妨开一个点,作为超级点,将所有的森林连接起来,那么现在的答案就是它到超级节点连接的边的个数了,实际上就是节点数-1,于是就可以利用LCT进行维护了。#include <iostream>#include <cstdio>#include <cmath>#incl.

2020-08-06 09:51:05

[国家集训队]Tree II【LCT动态树lazy标记】

P1501 [国家集训队]Tree II 因为本题树形结构会改变,所以这里需要使用LCT来代替树链剖分来解决问题,所以就要涉及到关于LCT的一条链上的lazy标记的下放了。 很明显的一件事就是,我们可以在pushdown()操作中进行下放懒标记,因为本题与是否翻转没有直接关联,所以无须考虑r[]的翻转标记的作用。void pushdown(int x){ clear(0); if(mul[x] ^ 1) { if(c[x][0]) ..

2020-08-06 09:12:45

[HEOI2013]Segment【李超线段树】

题目链接 有N次操作,强制在线,每次要么查询时候的与已有线段的最大交点值的对应线段序号,要么就是插入一个线段。 于是,就是一个很明显的一个李超线段树了,用永久化标记来进行操作,当插入对应区间的时候,利用它和已有的覆盖线段来进行比较,我们可以知道它们的关系。#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring&g..

2020-08-05 10:49:23

All-Star Game【LCT维护最大权生成树】

题目链接 题意:有N个球员,还有M个球迷,然后有:这是球迷去看球员比赛的条件,然后现在问最少多少个球员,就可以使得所有的球员都可以去看球赛。 然后有Q次操作,会使得球迷x和球员y的关系进行转换,如果球迷x原本喜欢y现在就不喜欢了,如果原本不喜欢,现在就喜欢了。 好了,我们可以发现这Q次操作,实际上就是保证了原来存在的边,现在把它删除;原来不存在的边,现在把它加进去。于是,再分析,我们可以发现,我们实际上要求的是有关M个球迷的合法联通块的个数(一定要有一个球员的联通块)。 于是...

2020-08-04 10:43:37

Pointer Analysis【2020牛客多校第7场J题】【翻译+模拟】

题目链接 好一篇阅读理解!——题记 这题就是给你一个关于指针的定义。首先,有指针、成员、对象三个定义,这些与基础的C语言无差别。 然后有四种操作:A = x:表示指针A指向成员x; A = B:表示指针A指向(指针B指向的所有的成员); A.f = B:表示指针A的全体成员的指针f指向(指针B指向的所有的成员); A = B.f:表示指针A指向(指针B的全体成员的指针f指向的成员)。于是,现在问你,全局指针A~Z所可能指向的小写成员(小写字母)有哪些?升序输出。为了方...

2020-08-02 22:40:46

Car【HDU - 6778】【二分答案+状压DP】

题目链接 我们可以二分答案,然后再去判断它的可行性,可行性可以用dp来贪心判断,但是如果不经过预处理的直接爆搜,时间复杂度是显然,是有可能被卡的,所以我们对这部分预处理了一下,就可以卡过去了。#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#include <algorithm>#incl.

2020-07-31 17:26:03

线段树/扫描线 优化网络流建图

例题 CF793G Oleg and chess我们可以构造这样的矩阵,令白色矩阵为不可以走的矩阵,令有色矩阵为我们的匹配阵。 于是我们可以将每一个可以用作匹配的矩阵拆出来,就有它最远延伸到的点,以及延伸到的终点,每一个延伸到的终点,实际上就是每一个白色矩阵的起点的前一个位置(因为我们要保证矩阵没有相交面积)。这里我们的参考系选择是从左往右来看的,扫描也是从最左开始的。 所以,我们要知道每个点的最前面的到达的位置,然后我们就可以确定每一个有色矩阵的位置区间了,就譬如我们现在拿出一..

2020-07-31 10:01:27

Tokitsukaze and Colorful Tree【树状数组+离线+dfs】

题目链接 HDU-6793题意:有N个点的树,每个点有颜色和权值,现在有两种操作,要求的是树上的同种颜色的非祖先与子孙节点的两点的异或和。更改某个点权值为v 将某个点的颜色更改为c 于是我们可以这样考虑,现在将所有的颜色离线下来,每次我们先对一种颜色求贡献,因为有N个点,每个点的颜色都是固定的在几个中的一个的,并且操作数是只有Q次,所以这样的总的点复杂度在级别。 将操作分成增加一个节点、删除一个节点、以及修改一个节点的操作,于是,我们可以对这棵树结构固定的树来进行操作了,因为树结构固..

2020-07-29 16:02:11

Legacy 【CodeForces - 786B】【线段树优化建图】

题目链接CF-786B题意:有N个点,Q次操作,图的起点是S,问经过Q次操作之后,S到每个点的最短路。增加从点v到点u的距离w的边 增加从点v到点[l, r]区间的每个点的距离w的边 增加从区间[l, r]到点v的距离为w的边 于是,我们可以开两棵线段树,分别表示出入的情况,然后操作结束之后跑一次堆优化的Dijkstra即可。#include <iostream>#include <cstdio>#include <cmath>#include.

2020-07-28 10:37:06

Fight【枚举】

题目链接 有三个人,初始都是1000血,现在要让活着的两两相互打架,每个人都有固定伤害,每一回合都是相互受到对方的伤害。问最少几个回合结束游戏(只剩下一个人活着)。 然后,我们枚举两个人打架的回合数,也就是枚举每两个人要打几个回合,然后就可以O(1)贪心的去算出剩下要打的回合。#include <iostream>#include <cstdio>#include <cmath>#include <string>#include &l..

2020-07-26 20:33:43

In Search of Gold【二分答案+树DP】

题目链接 题意:给一棵N个点的树,每条边有Ai、Bi权值可以选,现在问的是选K条边作为A边,其余N-1-K条边为B边,求最短直径。 一开始的时候,想直接在树上做一个DP,但是写完之后发现不对劲,如果我们直接在树上写DP的话,由于他们的关系是相互制约的,所以确实不大好维护,因为这个dp要考虑从祖先节点的另外的方向的节点。 所以,我二分了一个答案,假定现在直径为,接下去维护点u为根的子树,当选择kk个A边的时候,此时的可行解中的最小链长是多少?只要使得1节点(也就是根节点)存在合法解就可以证明...

2020-07-26 11:07:18

Ancient Distance【整体二分】

2020牛客多校第四场A题题意:给一个有根树,在树上选择 k 个关键点(根必须选)最小化点到最近关键祖先距离的最大值求出 k 分别为 1,2,…,n 时答案的和思路: 对于我们要求某个答案下的最少需求,可以知道对于一个点,如果不是取的最后一个点,都可以取至少个点,除去本身以外个点。于是乎,我们可以看到对于关键点个数有的时候,答案个数大概会在左右,那么,这里岂不是有一个类似于整数除法,那么,可以推测不同的关键点个数,可能答案是会相同的,所以我们不妨去处理出表示答案为i时候,所使用的关.

2020-07-23 23:55:35

Prefix Flip【小模拟】

题目链接CF-1382-C2 题意:有两个字符串,现在我们要让第一个字符串变成第二个字符串,只允许使用2N次操作,问操作。 每次操作是选前缀x个,然后首先前缀x全体异或1,然后字符串翻转。 于是,很明显的,我们可以按次数每次维护最后一个字符串,先满足最后一个,然后往前推就是了,但是我们不能真的对操作实际化了,因为时间不够的做法,所以我们将目前剩下的需要处理的字符串存储即可,然后进行操作。#include <iostream>#include <cstdio>...

2020-07-22 11:00:02

查看更多

勋章 我的勋章
  • 领英
    领英
    绑定领英第三方账户获取
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 签到王者
    签到王者
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 技术圈认证
    技术圈认证
    用户完成年度认证,即可获得
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 阅读者勋章Lv1
    阅读者勋章Lv1
    授予在CSDN APP累计阅读博文达到3天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 学习力
    学习力
    《原力计划【第二季】》第一期主题勋章 ,第一期活动已经结束啦,小伙伴们可以去参加第二期打卡挑战活动获取更多勋章哦。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。
  • 原力探索 · S
    原力探索 · S
    在《原力计划【第二季】》打卡挑战活动中,发布 12 篇原创文章参与活动的博主,即可获得此勋章。(本次活动结束后统一统计发放)