hzwer.com _ Home | http://hzwer.com

« 上一页Current position : 首页 >> 点分治 >> 第2页

• WC2010重建计划

  

  DescriptionInput第一行包含一个正整数N，表示X国的城市个数.第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi其中城市由1..N进行标号Output输出最大平均估值，保留三位小数SampleInput423121132143SampleOutput2.500HINT20%的数据,N<=500030%的数据,N<=100000,原有方案恰...
  22014年12月3日7,525二分法,点分治,单调队列

• 「BZOJ3697」「FJ2014集训」采药人的路径

  

  Description采药人的药田是一个树状结构，每条路径上都种植着同种药材。采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到...
  92014年9月26日8,790点分治

• 「BZOJ2599」[IOI2011] Race

  

  Description给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.Input第一行两个整数n,k第二..n行每行三个整数表示一条无向边的两端和权值(注意点的编号从0开始)Output一个整数表示最小边数量如果不存在这样的路径输出-1SampleInput43011122134SampleOutput2题解这题有点怪的点分治。。。我的做法也比较逗，就是开一个100W的数组t,t[i]表示权值为i的路径最少边数找到重心分成若干子树后，得出一棵子树的所有点到...
  22014年9月7日8,008点分治

• 「BZOJ2152」聪聪可可

  

  Description聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下...
  22014年9月7日6,461点分治

• 「POJ1741」Tree

  

  DescriptionGiveatreewithnvertices,eachedgehasalength(positiveintegerlessthan1001).Definedist(u,v)=Themindistancebetweennodeuandv.Giveanintegerk,foreverypair(u,v)ofverticesiscalledvalidifandonlyifdist(u,v)notexceedk.Writeaprogramthatwillcounthowmanypairswhicharevalidforagiventree.InputTheinputcontainsseveraltestcases.Thefirstlineofeachtestcasecontainstwointegersn,k.(n<=10000)Thefollowi...
  122014年6月15日9,826点分治