题目推荐—BZOJ水题推荐.pdf

题⽬推荐—BZOJ⽔题推荐[bzoj1756]Vijos1083⼩⽩逛公园裸题--。。线段树维护lmax,rmax,max,sum然后搞之。。[Ahoi2008]Meet紧急集合求两两点的lca然后会发现必然有两个lca是相等的，枚举三个lca然后特判下[Usaco2010Feb]slowdown慢慢游线段树维护dfs序。。很裸--。。[Usaco2006Nov]Roadblocks第⼆短路我写的a*。。吐槽下。。这题的数据真的很弱。。第⼀次提交都忘判断第⼀短和第⼆短是否相等结果还a了。。囧[Usaco2006Nov]FenceRepair切割⽊板倒过来就是⽯⼦合并。。[Usaco2007Oct]Money奶⽜的硬币囧。。这为什么会是gold的题。。[HNOI2003]激光炸弹各种做法。。我看时限是10s就暴⼒枚举所有正⽅形了==。。[SCOI2009]粉刷匠先dp出每⼀⾏涂k次的最多正确粉刷，再⽤对每⾏dp[Usaco2008Nov]安慰奶⽜cheer转化⼀下就是最⼩⽣成树。。边权=边权*2+端点点权。。再找到最⼩点权的起点加到ans⾥就好[HNOI2005]狡猾的商⼈裸并查集。。--[HNOI2004]打鼹⿏按时间dp。。--[bzoj1251]序列终结者裸splay题。。--[Scoi2010]游戏明显是匹配。。[POI2008]BLO构造dfs树，对于⼀个点x去掉后它的⼉⼦的low如果⾃⼰dfn的那么就说明这颗⼦树在去掉x后是独⽴的。。求出所有这些独⽴⼦树中的孤⽴点对。。再加上这些⼦树和x的⽗亲们的孤⽴点对[Jsoi2011]括号序列这题搞死我了。。==。。维护flip,reverse,flipreverse三个形态。。然后狂写就好。。注意别把建树的复杂度搞成n^2。。（我是沙茶啊啊啊因为这t了⼀晚上。。）[JSOI2010]Group部落划分按边权排序，然后⼀次⼀次合并两个端点。。⽤并查集维护[HNOI2008]GT考试kmp上dp+矩阵乘。。好久不写kmp了。。[Usaco2007Jan]Running贝茜的晨练计划dp。。⼀开始我还想暴⼒写2维的。。结果好像没这个必要--[Baltic2009]monument枚举坐标轴，在⼀个和这个轴垂直的所有⾯上做dp求出以x,y为左上⾓能得到的最⼤正⽅形。。然后再枚举正⽅形上每个点，沿着垂直于正⽅形的⾯上来回扫⼀遍就ok[Zjoi2011]礼物(gift)同上==。。[HNOI2006]超级英雄Hero⼜是裸匹配。。--[BeiJing2010组队]次⼩⽣成树Tree这题囧。。求出最⼩⽣成树以后枚举每个⾮树边，求两个端点的lca。。记录dp[i][j][2]表⽰从i开始往上数2^j个的最⼤值和次⼤值。。次⼤值必须严格⼩于最⼤值，否则记为0。。⼜因为本题保证存在最⼩⽣成树。。所以也不⽤特判T_T[POI2007]Zap写过题解，见前⼀篇⽂章[Usaco2006Oct]AnotherCowNumberGame奶⽜的数字游戏⽆语的题。。[ZJOI2010]network⽹络扩容先求最⼤流，再新建⼀个超级汇点T，连t-->T容量为k，再在原来那些边上再建⼀个容量为inf，费⽤为wi的边。。再跑⼀遍费⽤流。。（好像看⼈说可以只跑⼀次费⽤流。。没想出来。。）Usaco2008Feb]Line连线游戏囧。。。排个序然后扫⼀遍。。[Usaco2008Feb]EatingTogether⿇烦的聚餐nlgn求最长⾮降，正着逆着都求⼀遍取最⼤。。[Usaco2008Mar]RiverCrossing渡河问题裸dp。。[Usaco2007Jan]BalancedLineup排队裸线段树或树状数组或sparsetable。。[Usaco2007Dec]宝⽯⼿镯01背包==[Usaco2008Oct]灌⽔新增⼀个点连向所有的点边权是wi。。然后最⼩⽣成树之==[ZJOI2007]仓库建设斜率优化==。。[BeiJing2010组队]能量魔⽅Cube[POI2008]砖块Klo要求⼀个数据结构满⾜插⼊/删除⼀个数以及求中位数和对区间求和。。splay⽔掉。。[BeiJing2010]取数游戏gamedp。。如果⼀个数能被取到，那么更新它所有>=L的约数。。[POI2008]CLO可以发现只有树结构不满⾜条件。。枚举连通分量然后判断是不是树结构[Poi2008]海报PLA⽤栈维护⼀个递增序列。。搞搞就过了[POI2008]激光发射器SZK这题太囧了。。⼀开始不会。。去orz题解。。结果。。。。。。。。。。。。。。printf("%d\n",n/2);[bzoj1475]⽅格取数最⼤权独⽴集。。转化成最⼩割来做就好。。⽹络流24题⾥原题[Usaco2008Feb]Hotel以前poj上做过，也是维护左、右、