BZOJ题目整理.pdf

BZOJ题⽬整理现在要写⼀些题⽬。现在已经做了：157题「BZOJ1529」「POI2005」PiggyBanks并查集「BZOJ3527」「ZJOI2014」⼒FFT「BZOJ1924」「SDOI2010」所驼门王的宝藏奇妙的建图强连通分量缩点+最长路dp「BZOJ3205」思博题「BZOJ2150」部落战争建图+最⼩路径覆盖(不知道什么⿁数据，原图不拆点直接⼆分图就A了)「BZOJ1050」「HAOI2006」旅⾏求⼀条使得最⼤边⽐最⼩边最⼩的路径，枚举最⼩边，并查集⽣成树(LCT可以做到不过谁想写啊)「BZOJ3884」欧拉定理「BZOJ3668」「NOI2014」起床困难综合症思博贪⼼「BZOJ4196」「NOI2015」软件包管理器树链剖分，快读导致1A失败，mdzz「BZOJ3670」「NOI2014」动物园奇妙的kmp递推「BZOJ1012」「JSOI2008」弱智线段树「BZOJ4872」「SHOI2017」分⼿是祝愿先观察发现必须从⼤到⼩按，那么我们对于还要按次，就有⼀个概率，然后求个逆元，直接推了「BZOJ2427」「HAOI2010」5分钟写了⼀个treedp，然后发现不连通，我蠢死好了，先缩点，然后建⼀个超级源点，给⼊度为0的分量连边，这样做依赖dp就好了，这个连接树的⽅法很好玩，然后就是Treedp都是的，我们做⼀个dfs序，然后求出每个节点⼦树的，就可以递推了「BZOJ1226」「SDOI2009」状态压缩dp，不太好写「BZOJ2216」「POI2011」对求导，发现斜率增长率递减，所以说当⼀个点距离远还⽐距离近的节点⼩，我们就可以直接让他出队，⼆分⼀下原数列，然后对于每个点做⼀个可⾏答案区间，然后就可以在的时间更新答案，注意到⽅程与后⾯的值有关，我们可以反向再做⼀遍。「BZOJ3437」第⼀次写斜率优化，有点恶⼼，这个式⼦好像已经到了⼈尽皆知我不会的地步了。。。我们做出两个sum，保证更新的时候查询距离乘积和的时候是的，然后发现这个式⼦可以斜率优化，答案在⼀个上凸壳上，再做两道再说吧，我太弱了。「BZOJ2749」「HAOI2012」外星⼈给了⼀个式⼦，好吧我看不懂题⽬。。其实是求phi迭代计算等于1的值。只有。好吧这个式⼦题⽬给了。。然后我们观察⼀下，每次做phi操作，使得的次数-1，然后添加了⼀个，在观察⼀下，我们每次操作还可以消去⼀个2，把它变成1，⽽⼀定是⼀个偶数，⼀定给这个式⼦添加了⼀个2，于是问题转化为了求给定数字可以转化为多少个2，我们要消掉它。然后再观察⼀下，这个关于每个数可以消成的2的个数的函数满⾜：，于是就可以线性筛了。「BZOJ1170」「APIO2009」思博tarjan+dp，但是dp死活过不了，改了个spfa。。。「BZOJ5039」「JSOI2014」思博线段树。「BZOJ1015」「JSOI2008」删点维护连通性，离线⼀下，反向并查集，挺好玩的。「BZOJ2763」「JLOI2011」思博spfa。（分层图「BZOJ1570」「JSOI2008」BlueMary的旅⾏暴⼒枚举答案，每次添加新的层次图，直到最⼤流==T。（不加当前弧16秒「BZOJ1562」「NOI2009」构造⼆分图，然后我不会了，然后我dfs，然后我TLE好吧，我们为了求字典序最⼩的最⼤匹配，可以反向求匹配，因为匈⽛利算法是后来的边更新前⾯的，然后⼀遍⼆分图最⼤匹配，把⽅案输出来就好了。「BZOJ1257」「CQOI2007」答案是sqrt区间不变的，我好蠢啊。「BZOJ1103」「POI2007」⼤都市meg我直接树链剖分了，dfs序啊啊啊啊，慢的要死。「BZOJ2190」「SDOI2008」仪仗队，观察性质，直接线性筛了。「BZOJ1067」「SCOI2007」有毒，线段树分类讨论。「BZOJ2599」「IOI2011」Race点分治，我咋⽼写错这个啊。。。「BZOJ3658」Jabberwocky离散化⼀下，开⼀个链表维护⼀个点两边能达到的点，每次树状数组维护删改操作。「BZOJ1093」「ZJOI2007」最⼤半连通⼦图tarjan+dp最长路「BZOJ1412」「ZJOI2009」狼与⽺的故事建图+最⼩割。「BZOJ1179」「Apio2009」AtmTarjan+dp「BZOJ4381」「POI2015」Odwiedziny树上分块「BZOJ3689」异或之01字典树，堆计数第k⼤「BZOJ1001」狼抓兔⼦平⾯图最⼩割->对偶图最短路「BZOJ1261」「SCOI2006」zh_treedp「BZOJ2134」期望dp「BZOJ1076」状压期望dp「BZOJ4008」⾮常神的期望dp「BZOJ4318」期望dp「BZOJ3585」莫队维护区间mex「BZOJ3143」「HNOI