广度搜索 - Page 2

POJ训练记录3
1379.RunAway模拟退火裸题[crayon-69fa1f68c0906367805843/]2758.CheckingtheText暴力+哈希[crayon-69fa1f68c0910334786929/]poj3156.Interconnect由于状态是满足拓扑序的，所以直接dp上，再用个hash记忆化[crayon-69fa1f68c0916706954672/]1837.Balancef(i,j)前i个力矩为j的方案,dp[crayon-69fa1f68c091c939055616/]3609.ResetSequence状压+bfs初始集合是0-n-1每个指令会使得集合中的一些元素消失，目标状态是只有一个0[c...
02015年5月19日5,382递推与动规,几何,哈希表,状压动规,广度搜索,记忆化搜索,概率与期望

「CF507X」Codeforces Round #287 (Div. 2)
A.AmrandMusic排序贪心[crayon-69fa1f68c0eb5732485901/]B.AmrandPins算出距离除以直径[crayon-69fa1f68c0ec3639845945/]C.GuessYourWayOut!按位考虑[crayon-69fa1f68c0ec9435497600/]D.TheMathsLecture从后往前dpf(i,j,k)表示后i位，当前模为j，是否有后缀被K整除[crayon-69fa1f68c0ed1462199493/]E.BreakingGood广搜，选可用边最多的路径[crayon-69fa1f68c0edd094418246/] ...
02015年5月16日3,426递推与动规,模拟,贪心,广度搜索
「CF543X」Codeforces Round #302 (Div. 1)
本场血崩A.WritingCode显然的n^3dp，滚动数组[crayon-69fa1f68c1415857624436/]B.DestroyingRoadsn个结点,m条边的无向图(边权全为1),问最多能删掉多少条边使得s1到t1距离不超过l1,s2到t2距离不超过l2。\(1\leqn\leq500,1\leqm\leqn(n-1)/2\)题解其实就是问，至少需要多少条边，才能使得s1到t1距离不超过l1,s2到t2距离不超过l2。如果这两条路径不相交，那么答案为dis(s1,t1)+dis(s2,t2)。如果相交部分为(p1,p2)，答案为p1,p2的...
12015年5月8日3,480递推与动规,树形动规,广度搜索
「JoyOI」五月有奖赛暨Loi 55 Round #1 Day1
题解http://pan.baidu.com/s/1bnjO0ij选择题（byDarkfalmes）[crayon-69fa1f68c1b3f550914655/]王的对决！(byrainheart&seavot)[crayon-69fa1f68c1b4a210912604/]dC的肥皂（byskyfall（Orz））60暴力[crayon-69fa1f68c1b52390634514/]DQS和序列（by帝江&Darkfalmes）[crayon-69fa1f68c1b59764259843/] ...
22015年4月30日4,567递推与动规,线段树,筛法,广度搜索,莫比乌斯反演
「BZOJ2282」[SDOI2011] 消防
Description某个国家有n个城市，这n个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为zi(zi<=1000)。这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。现在这个国家的经费足以在一条边长度和不超过s的路径（两端都是城市）上建立消防枢纽，为了尽...
62014年12月22日7,419二分法,广度搜索
NOIP2014寻找道路
题目描述Description在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：1．路径上的所有点的出边所指向的点都直接或间接与终点连通。2．在满足条件1的情况下使路径最短。注意：图G中可能存在重边和自环，题目保证终点没有出边。请你输出符合条件的路径的长度。输入输出格式Input/output输入格式：输入文件名为road.in。第一行有两个用一个空格隔开的整数n和m，...
32014年11月22日6,392广度搜索
「BZOJ1193」[HNOI2006] 马步距离
DescriptionInput只包含4个整数，它们彼此用空格隔开，分别为xp,yp,xs,ys。并且它们的都小于10000000。Output含一个整数，表示从点p到点s至少需要经过的马步移动次数。SampleInput1279SampleOutput5题解大范围贪心，然后小范围暴力[crayon-69fa1f68c3217263423537/] ...
22014年11月13日6,303贪心,广度搜索
NOIP2010引水入城
题目描述Description 在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个N行M列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此，只有与湖泊毗邻的第1行的...
02014年11月6日9,110贪心,广度搜索
「NOIP模拟赛」密室逃脱
即使czhou没有派出最强篮球阵容，机房篮球队还是暴虐了校篮球队。为了不打击校篮球队信心，czhou决定改变训练后的活动。近来，江大掌门的徒弟徒孙们纷纷事业有成，回到母校为机房捐钱捐物。财大气粗的机房组收回了五层六层的所有教室。Czhou决定将六层的教室改造为智能密室逃脱活动室。每天傍晚，神牛们可以依次逐个进入游玩。我们简单的将教室分割为n*n个房间，K是你初始所在房间，T是你最终逃脱的房间。如果你想要逃脱房间，你...
02014年11月5日4,195深度搜索,广度搜索
「NOIP模拟赛」藏宝图
背景Czy爬上黑红树，到达了一个奇怪的地方……题目描述Czy发现了一张奇怪的藏宝图。图上有n个点，m条无向边。已经标出了图中两两之间距离dist。但是czy知道，只有当图中的各个点刚好又是一颗树的节点的时候，这张藏宝图才是真的。如果藏宝图是真的，那么经过点x的边的边权平均数最大的那个x是藏着宝物的地方。请计算这是不是真的藏宝图，如果是真的藏宝之处在哪里。格式输入数据第一行一个数T,表示T组数据。对于每组数据，第一...
02014年10月31日4,315STL,prim,广度搜索
「NOIP模拟赛」Graph
「题目描述」给出N个点，M条边的有向图，对于每个点v，求A(v)表示从点v出发，能到达的编号最大的点。「输入格式」第1行，2个整数N,M。接下来M行，每行2个整数Ui,Vi，表示边⟨Ui,Vi⟩。点用1,2,...,N编号。「输出格式」N个整数A(1),A(2),...,A(N)。「样例输入」43122443「样例输出」4434「数据范围」对于60%的数据，1≤N,K≤10^3对于100%的数据，1≤N,M≤10^5。题解反建图bfs[crayon-69fa1f68d6e1e871039854/]&...
02014年10月30日2,744广度搜索
「BZOJ3417」POI2013 Tales of seafaring
DescriptionYoungBytenssonlovestohangoutintheporttavern,whereheoftenlistenstotheseadogstellingtheirtalesofseafaring.Initially,hebelievedthemall,howeverincredibletheysounded.Overtimethough,hebecamesuspicious.Hehasdecidedtowriteaprogramthatwillverifyiftheremaybeanygrainoftruthinthosetallstories.Bytenssonreasonedthatwhilehecannottellifthesailorsindeedweatheredallthosestorms,hecanatleastfindouti...
232014年10月29日5,264广度搜索,离线处理