• 「CF1229X」Codeforces Round #588

    「CF1229X」Codeforces Round #588

    A.MarcinandTrainingCamp若A觉得自己没有B强,B向A连边度数为0的点,是觉得自己比其它人都强的,把它们依此拓扑排序删除[crayon-67550cade5717010544348/]B.KamilandMakingaStream从一个点向上走,区间gcd单调下降,且最多变化log次可以用树上倍增维护区间gcd,枚举每个点往上二分跳,暴力统计答案更简单的做法是用vector维护一个点往上的不同gcd,以及它们贡献答案的次数,这个vector大小是logdfs暴力往儿子转移倍增:...

  • 2017 训练赛 1 by hzwer

    2017 训练赛 1 by hzwer

    「poj1054」TheTroublesomeFrog(恼人的青蛙)「poj1037」decorativefence「hdu2197」本原串「poj2112」OptimalMilkin「bzoj4010」[HNOI2015]菜肴制作「hdu2462」TheLuckiestnumber「bzoj3172」[Tjoi2013]单词「poj1054」TheTroublesomeFrog(恼人的青蛙)首先O(n^3)的算法是显然的,即枚举两个点,check一下这条路径上所有点,由于这道题时限放的比较宽,实际上图可以直接用二维的bool数组存下来网络上的题解大多...

  • 「CF698X」Codeforces Round #363 (Div. 1)

    「CF698X」Codeforces Round #363 (Div. 1)

    A.Vacations题意:给出每天contest和gym的开关状态,不能连续俩天参加相同活动,问n天最少休息多少天用F(i,0-2)表示前i天,第i天的状态为(rest,contest,sport),最多能有多少天不休息简单dp一下[crayon-67550cade7004266713234/]B.FixaTree给出n个结点的父亲,问至少修改多少个能够使得其变成一棵树先用拓扑排序消去外向树,剩下的每个环要选出一个当根,然后再把所有的环连成树答案是环数-(是否存在自环)[crayon-6755...

  • 「CF512X」Codeforces Round #290 (Div. 1)

    「CF512X」Codeforces Round #290 (Div. 1)

    做了俩题就丧失了动力A.FoxAndNames建图完拓扑排序[crayon-67550cade7495960144531/]B.FoxAndJumping记忆化暴力QAQ[crayon-67550cade74a1586284096/] 

    02015年5月24日3,796拓扑排序,记忆化搜索
  • CERC 2012 填坑计划(4 / 11)

    CERC 2012 填坑计划(4 / 11)

    A-Kingdoms把所有破产状态状压dp[crayon-67550cade7918971796677/]C-Chemist'svows无聊的抄表题。。。[crayon-67550cade7922856654555/]H-Darts模拟题[crayon-67550cade7928009141717/]J-Conservation怀疑数据是不是有问题。。。贪心+拓扑排序[crayon-67550cade792c397597821/] ...

    02015年5月22日4,051模拟,STL,贪心,状压动规,拓扑排序
  • 「BZOJ4011」[HNOI2015] 落忆枫音

    「BZOJ4011」[HNOI2015] 落忆枫音

    Description「恒逸,你相信灵魂的存在吗?」郭恒逸和姚枫茜漫步在枫音乡的街道上。望着漫天飞舞的红枫,枫茜突然问出这样一个问题。「相信吧。不然我们是什么,一团肉吗?要不是有灵魂……我们也不可能再见到你姐姐吧。」恒逸给出了一个略微无厘头的回答。枫茜听后笑了笑。「那你仔细观察过枫叶吗?」说罢,枫茜伸手,接住了一片飘落的枫叶。「其实每一片枫叶都是有灵魂的。你看,枫叶上不是有这么多脉络吗?我听说,枫叶上有一些...

    02015年5月7日7,373递推与动规,拓扑排序
  • 「BC35」DZY Loves Topological Sorting

    「BC35」DZY Loves Topological Sorting

    问题描述一张有向图的拓扑序列是图中点的一个排列,满足对于图中的每条有向边(u→v)从u到v,都满足u在排列中出现在v之前。现在,DZY有一张有向无环图(DAG)。你要在最多删去k条边之后,求出字典序最大的拓扑序列。输入描述输入有多组数据。(TestCase≤5)第一行,三个正整数n,m,k(1≤n,m≤105,0≤k≤m).接下来m行,每行两个正整数u,v(u≠v,1≤u,v≤n),代表一条有向边(u→v).输出描述对于每组测试数据,输出一行字典序最大的拓...

    02015年3月30日3,274STL,贪心,拓扑排序
  • 「CF516B」Drazil and Tiles

    「CF516B」Drazil and Tiles

    Drazilcreatedafollowingproblemaboutputting1 × 2tilesintoann × mgrid:"Thereisagridwithsomecellsthatareemptyandsomecellsthatareoccupied.Youshoulduse1 × 2tilestocoverallemptycellsandnotwotilesshouldcovereachother.Andyoushouldprintasolutionabouthowtodoit."ButDrazildoesn'tliketowritespecialcheckingprogramforthistask.Hisfriend,Vardaadvisedhim:"howaboutaskingcontestantonlytoprintthesolut...

    02015年2月25日2,960深度搜索,拓扑排序
  • 「BZOJ2815」[ZJOI2012] 灾难

    「BZOJ2815」[ZJOI2012] 灾难

    小强和阿米巴0.0fhq神犇的题==http://fanhq666.blog.163.com/blog/static/8194342620124274154996/[crayon-67550cade8dc2407848129/] 

  • NOI2009植物大战僵尸

    NOI2009植物大战僵尸

    DescriptionInputOutput仅包含一个整数,表示可以获得的最大能源收入。注意,你也可以选择不进行任何攻击,这样能源收入为0。SampleInput32100200-100-51001001211000SampleOutput25HINT在样例中,植物P1,1可以攻击位置(0,0),P2,0可以攻击位置(2,1)。一个方案为,首先进攻P1,1,P0,1,此时可以攻击P0,0。共得到能源收益为(-5)+20+10=25。注意,位置(2,1)被植物P2,0保护,所以无法攻击第2行中的任何植物。「大致数据规...

    02014年12月17日6,533最小割,拓扑排序
  • 「BZOJ1093」[ZJOI2007] 最大半连通子图

    「BZOJ1093」[ZJOI2007] 最大半连通子图

    DescriptionInput第一行包含两个整数N,M,X。N,M分别表示图G的点数与边数,X的意义如上文所述。接下来M行,每行两个正整数a,b,表示一条有向边(a,b)。图中的每个点将编号为1,2,3…N,保证输入中同一个(a,b)不会出现两次。Output应包含两行,第一行包含一个整数K。第二行包含整数CModX.SampleInput6620070603122113245664SampleOutput33HINT对于100%的数据,N≤100000,M≤1000000;对于100%的数据,X≤...

  • 「NOIP模拟赛」混合图

    「NOIP模拟赛」混合图

    Hzwer神犇最近又征服了一个国家,然后接下来却也遇见了一个难题。Hzwer的国家有n个点,m条边,而作为国王,他十分喜欢游览自己的国家。他一般会从任意一个点出发,随便找边走,沿途欣赏路上的美景。但是我们的Hzwer是一个奇怪的人,他不喜欢走到自己以前走过的地方,他的国家本来有p1条有向边,p2条无向边,由于国王奇怪的爱好,他觉得整改所有无向边,使得他们变成有向边,要求整改完以后保证他的国家不可能出现从某个地点出发...

    12014年7月7日4,471拓扑排序
1 / 2 1 2 下一页 »