拓扑排序 - hzwer.com

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

2017 训练赛 1 by hzwer
「poj1054」TheTroublesomeFrog（恼人的青蛙）「poj1037」decorativefence「hdu2197」本原串「poj2112」OptimalMilkin「bzoj4010」[HNOI2015]菜肴制作「hdu2462」TheLuckiestnumber「bzoj3172」[Tjoi2013]单词「poj1054」TheTroublesomeFrog（恼人的青蛙）首先O(n^3)的算法是显然的，即枚举两个点，check一下这条路径上所有点，由于这道题时限放的比较宽，实际上图可以直接用二维的bool数组存下来网络上的题解大多...
02017年3月7日9,885递推与动规,贪心,二分法,最大流,AC自动机,快速幂,拓扑排序,欧拉函数
「CF698X」Codeforces Round #363 (Div. 1)
A.Vacations题意：给出每天contest和gym的开关状态，不能连续俩天参加相同活动，问n天最少休息多少天用F(i,0-2)表示前i天，第i天的状态为（rest，contest，sport），最多能有多少天不休息简单dp一下[crayon-673fbe10ec300476768339/]B.FixaTree给出n个结点的父亲，问至少修改多少个能够使得其变成一棵树先用拓扑排序消去外向树，剩下的每个环要选出一个当根，然后再把所有的环连成树答案是环数-（是否存在自环）[crayon-673f...
02016年7月20日4,778递推与动规,状压动规,拓扑排序,概率与期望
「CF512X」Codeforces Round #290 (Div. 1)
做了俩题就丧失了动力A.FoxAndNames建图完拓扑排序[crayon-673fbe10ec743904804934/]B.FoxAndJumping记忆化暴力QAQ[crayon-673fbe10ec74e887388480/]
02015年5月24日3,786拓扑排序,记忆化搜索
CERC 2012 填坑计划(4 / 11)
A-Kingdoms把所有破产状态状压dp[crayon-673fbe10ecbc1720197663/]C-Chemist'svows无聊的抄表题。。。[crayon-673fbe10ecbca654079058/]H-Darts模拟题[crayon-673fbe10ecbd0110310103/]J-Conservation怀疑数据是不是有问题。。。贪心+拓扑排序[crayon-673fbe10ecbd3058753689/] ...
02015年5月22日4,042模拟,STL,贪心,状压动规,拓扑排序
「BZOJ4011」[HNOI2015] 落忆枫音
Description「恒逸，你相信灵魂的存在吗？」郭恒逸和姚枫茜漫步在枫音乡的街道上。望着漫天飞舞的红枫，枫茜突然问出这样一个问题。「相信吧。不然我们是什么，一团肉吗？要不是有灵魂……我们也不可能再见到你姐姐吧。」恒逸给出了一个略微无厘头的回答。枫茜听后笑了笑。「那你仔细观察过枫叶吗？」说罢，枫茜伸手，接住了一片飘落的枫叶。「其实每一片枫叶都是有灵魂的。你看，枫叶上不是有这么多脉络吗？我听说，枫叶上有一些...
02015年5月7日7,350递推与动规,拓扑排序
「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,266STL,贪心,拓扑排序
「CF516B」Drazil and Tiles
Drazilcreatedafollowingproblemaboutputting1 × 2tilesintoann × mgrid:"Thereisagridwithsomecellsthatareemptyandsomecellsthatareoccupied.Youshoulduse1 × 2tilestocoverallemptycellsandnotwotilesshouldcovereachother.Andyoushouldprintasolutionabouthowtodoit."ButDrazildoesn'tliketowritespecialcheckingprogramforthistask.Hisfriend,Vardaadvisedhim:"howaboutaskingcontestantonlytoprintthesolut...
02015年2月25日2,950深度搜索,拓扑排序
「BZOJ2815」[ZJOI2012] 灾难
小强和阿米巴0.0fhq神犇的题==http://fanhq666.blog.163.com/blog/static/8194342620124274154996/[crayon-673fbe10ee005337282705/]
22015年2月5日6,960树形动规,拓扑排序,最近公共祖先
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,517最小割,拓扑排序
「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≤...
22014年10月8日7,480递推与动规,拓扑排序,图的连通
「NOIP模拟赛」混合图
Hzwer神犇最近又征服了一个国家，然后接下来却也遇见了一个难题。Hzwer的国家有n个点，m条边，而作为国王，他十分喜欢游览自己的国家。他一般会从任意一个点出发，随便找边走，沿途欣赏路上的美景。但是我们的Hzwer是一个奇怪的人，他不喜欢走到自己以前走过的地方，他的国家本来有p1条有向边，p2条无向边，由于国王奇怪的爱好，他觉得整改所有无向边，使得他们变成有向边，要求整改完以后保证他的国家不可能出现从某个地点出发...
12014年7月7日4,459拓扑排序