2 Andres_Lionel

尚未进行身份认证

我要认证

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

等级
TA的排名 2k+

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

Sequential Nim【博弈】

题目链接CF-1382-B 题意:有N个石子堆,每个石子堆有a[i]个石子,现在从第一堆开始往后取,谁最先没法取石子,谁就输了,问最后谁先手还是后手赢了? 于是乎,可以看到,影响胜负的只有开局的为1的石子个数,就譬如说第一个石头不为1,那么我们就可以控制了,是取成一个其他数来匹配后面的,还是直接取完,然后他就一定能获胜了,所以真正影响胜负的,是谁开始控制局面,怎么控制,就是第一堆“>1”的石子堆(因为他是知道后继石子堆的),所以就可以开始控制了。#include <iostre..

2020-07-22 10:06:11

Points Construction Problem【构造】

2020牛客多校第三场D题 题意:有一个无穷大的平面,原本全是白点,现在给N个黑棋子,然后放入图中,使得黑白搭配对数有M对,问是否有解和方案输出。 首先,我们先把它构造成下限,来判断可行性,然后我们慢慢的把里面的点拆出来,就可以达到接近M的作用,构造下限的方法就是用构造一个近似正方形的方式。 然后我们算出还缺多少个,然后一个个的从里面拆出来。#include <iostream>#include <cstdio>#include <cmath>...

2020-07-20 22:15:13

Directing Edges【Codeforces 1385E】【拓扑排序】

题目链接 题意:N个点,M条边,其中“1”边是有向边,“0”边是无向边,我们要给无向边定向,使得这个图不会构成环。 构成环会让我们想到关于拓扑排序,因为如果成环了,就会使得有点不能出拓扑了,所以当我们跑拓扑序的时候,我们可以给无向边的指向定为从拓扑小的指向拓扑序大的。#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cst..

2020-07-19 09:10:20

Boke and Tsukkomi【HDU-4687】【一般图最大匹配 带花树】

题目链接 题意:问有哪几个匹配一定不会出现在任意一个最大匹配中。 那么,我们不妨直接暴力去枚举每一个匹配,因为带花树的复杂度是的,所以就算加上枚举的复杂度也是在允许范围内的。 只是注意判断条件,先强制让每次需要的匹配边自动匹配上,然后他们就不允许再换了。#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring&...

2020-07-17 23:05:16

Hard Problem【HDU-3551】【一般图最大匹配 带花树】

题目链接 题意:有N个点,M条边,给出每个点的度限制,问能不能用M条边中的几条达成这个目的? 很明显的就是一个建图的问题,很明显的,少于等于度为1的,是可以直接连的,不用限制增广,而大于度为1的,需要限制增广,就可以用这样的限流的方法:#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#incl..

2020-07-17 18:31:08

1 or 2【一般图最大匹配 带花树】

2020牛客多校第一场I题 题意:有N个点,M条边,要求使用其中的一些边,使得N个点每个点的度固定为d[i],问是否存在这样的解? 那么,我们对于d[i]不同时等于2的边,我们可以直接对两边的点直接相连了,但是d[i]同时等于2的时候,就不可以,因为要避免他们自己相互连接了。当d[i]同时等于2的时候,我们需要限制增广,也就是增加中间的两个新的点,来进行限制,同时最大的匹配上限,应该是增加1个。#include <iostream>#include <cstdi..

2020-07-17 16:14:11

[WC2016]挑战NPC【一般图最大匹配 带花树】

题目链接 很容易想到的是每个球肯定是去和它能连接边的对应的篮子的三个状态进行连接边,但是怎样生成更多的半空框子呢?这里我们可以将每个框子拆开来的点的第2和第3个点连接,也就是我们也想让更多的半空的框子生成,所以的话,最后的半空框子的个数就是总的匹配数减去N个球都必须要匹配的个数。#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <.

2020-07-17 15:28:06

Game【ZOJ 3316】【一般图最大匹配+带花树】

题目链接 有两个人在下棋,先让对手先下,下一个人下棋的位置,只能下在距离上一个人曼哈顿距离小于等于L的点上,谁最先无法下子,谁就输了,现在问大家都是最优的下的时候,后手的那个人能否赢得比赛。 所以,当一个人下棋的时候,我们可以下到他的一个匹配位上去,所以如果最大匹配的两倍是N的话,那么就是后手赢了,否则先手必胜。#include <iostream>#include <cstdio>#include <cmath>#include <stri..

2020-07-17 10:21:40

璀璨光滑【牛客】【题意解析+BFS+贪心】

题目链接中文题意,表面平静,实则暗藏玄机,而打开本题的突破口,也确确实实就在于题目的描述: 也就是说,这张图的边的数目是确定的,并且这是一张连通图,而且图上的个点每个点连接出去的边的数目都是条,因为每个数都刚好只与个数在二进制位上差1。 那么,这张图的形态是固定的,好了,现在开始想解决问题的方法。 于是乎,我们可以贪心的,为了让字典序是最小的,所以1号点一定选的是点权0。那么接下去与1号点相连的点肯定是,那么我们不妨先假设给他们赋值,就先随便的给他们找一组可行解,于...

2020-07-16 15:42:01

Interval【对偶图优化最小割(最大最小定理 周冬)】

2020牛客多校第二场I题首先,我们考虑最小割的方式来处理该问题:很明显的,这就是一张对偶图了,因为它没有任意两线会存在相交的可能了。所以根据对偶图的做法,我们可以将最小割问题转化为最短路了:绿色和粉色是新的对偶图所构成的边和点。然后我们在对偶图上跑一个最短路就可以了。#include <iostream>#include <cstdio>#include <cmath>#include <string>#includ

2020-07-15 16:55:59

查看更多

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