本弱逼长期做题都是膜题解膜题解,感觉提供一些关键点在进行思考的话能够更快的加强算法能力,所以我就稍微的写一写。
upd 3.8 : 懒癌晚期不想写东西了,我就记录一些最近做的不想写的傻逼题吧。
【BZOJ1001】 最小割转平面图。
【BZOJ1002】 状态压缩dp。
【BZOJ1003】 最短路+dp。
【BZOJ1004】 每一种洗牌对应一种置换,用一下burnside。
【BZOJ1005】 prufer。
【BZOJ1006】 弦图最大势。
【BZOJ1007】 维护凸壳。
【BZOJ1008】 补集转化。
【BZOJ1009】 kmp+矩阵优化。
【BZOJ1010】 斜率优化。
【BZOJ1012】 线段树。
【BZOJ1013】 高斯消元。
【BZOJ1014】 splay维护hash值。
【BZOJ1015】 离线转成插入操作并查集维护。
【BZOJ1016】 从小到大插边维护每个连通分量的最小生成树个数。
【BZOJ1019】 令f(i,j)表示从i柱子移动到另一个柱子盘子为j的操作次数,g(i,j)表示从i移动到另一个柱子盘子为j的移动位置。
【BZOJ1022】 SJ定理。
【BZOJ1024】 dfs。
【BZOJ1025】 考虑这个由多少个环且每个环大小和为n,对于每种状态的贡献就是lcm(各个环大小),那么就是求lcm值的种类。
【BZOJ1027】 其中有一维是没用的,这样就是一个经典问题:给定平面n个点,求最小凸包包围查询点。这个用最小环就能解决。
【BZOJ1028】 贪心。
【BZOJ1029】 贪心。
【BZOJ1030】 ACM上面dp。
【BZOJ1031】 SAM。
【BZOJ1034】 花式贪心。
【BZOJ1036】 树链维护值。
【BZOJ1037】 设f(i,j,k)前i个人有j个男的从i开始向前的连续段里最多有k个男与女的差,再设个g(i,j,k)同样地不同的是最多有k个女与男的差。
【BZOJ1040】 基环树。
【BZOJ1041】 很容易知道\(2r=d(a^{2}+b^{2})\),其中\(d=gcd(r+x, r-x)\), \(r+x=da^{2}\), \(r-x=db^{2}\),我们枚举d,然后再枚举a就可以了,注意到如果对于合法的a, b如果交换他们的值对应的x, y是不变的,那么就将a枚举的值缩一半就可以了,最后乘4加4就可以了。
【BZOJ1042】 容斥原理。
【BZOJ1044】 第一问二分。第二问dp。
【BZOJ1045】 经典问题,转化成每个点向正方向扔多少点,转化下就是求一个中位数。
【BZOJ1046】 dp。
【BZOJ1047】 单调队列或用ST表。
【BZOJ1048】 dp。
【BZOJ1049】 dp依照前一个dp值可以写一个O(n^3)的dp但是跑的飞快。
【BZOJ1050】 枚举最小边跑一下。
【BZOJ1051】 tarjan。
【BZOJ1052】 二分+贪心覆盖下。
【BZOJ1053】 爆搜。
【BZOJ1054】 状态压缩爆搜下。
【BZOJ1055】 dp。
【BZOJ1056】 平衡树。
【BZOJ1057】 维护上左右的值单调队列维护下。
【BZOJ1058】 set维护。
【BZOJ1059】 就是求是否存在n个互不同行或同列的点。
【BZOJ1060】 dp。
【BZOJ1061】 线性规划转化网络流。
【BZOJ1066】 网络流。
【BZOJ1067】 分类讨论下就好了。
【BZOJ1068】 dp。
【BZOJ1069】 旋转卡壳。
【BZOJ1070】 每个员工拆成n个点,网络流。
【BZOJ1071】 我们考虑(min_s, min_h)对应的一个集合S,那么(min_s, min_h+1)对应的集合不过是S上加一些值再减掉min_h的点,那么考虑直接枚举min_s, min_h然后单调维护就可以了。
【BZOJ1072】 维护下模的值。
【BZOJ1076】 期望dp。
【BZOJ1079】 f(i1,i2,..,i5,last)表示能涂j次的是i_j,last颜色为last。
【BZOJ1083】 最小生成树。
【BZOJ1084】 m很小可以dp小。
【BZOJ1085】 枚举上限步数然后搜索。
【BZOJ1086】 树分块。
【BZOJ1087】 状态压缩。
【BZOJ1088】 暴力。
【BZOJ1098】 递推。
【BZOJ1090】 dp。
【BZOJ1095】 维护一堆树重心。
【BZOJ1101】 mobius反演。
【BZOJ1103】 线段树维护dfs序。
【BZOJ1106】 树状数组维护下。
【BZOJ1108】 画个图找下规律。
【BZOJ1110】 砝码的种类不多不会超过log次,考虑从小到大扔砝码就可以了。
【BZOJ1113】 维护一个单调栈。
【BZOJ1115】 前后做差就是阶梯nim。
【BZOJ1121】 找规律。
【BZOJ1132】 按极角排,就可以算一坨叉积和。
【BZOJ1135】 二分图匹配,用Hall定理优化。
【BZOJ1146】 区间k大。
【BZOJ1176】 cdq分治。
【BZOJ1179】 强连通分量。
【BZOJ1189】 网络流。
【BZOJ1190】 可以dp下有a*2^b+(w&((1<<b)-1))容量。
【BZOJ1191】 匹配一下。
【BZOJ1192】 嘿嘿嘿。
【BZOJ1196】 二分+MST
【BZOJ1202】 差分约束或并查集维护与父亲的差值。
【BZOJ1207】 暴力。
【BZOJ1208】 平衡树。
【BZOJ1210】 插头dp。
【BZOJ1211】 prufer序列。
【BZOJ1212】 Trie+dp。
【BZOJ1213】 高精度运算。
【BZOJ1218】 dp。
【BZOJ1228】 对一个组<a,b>进行找规律就可以了。
【BZOJ1237】 将a,b都排序,只有连续三个数可以被调整,也就是每个数最多能被调整3次,这样直接dp就可以了。
【BZOJ1251】 平衡树。
【BZOJ1257】 经典O(n^0.5)。
【BZOJ1260】 区间dp。
【BZOJ1263】 划分尽量多3。
【BZOJ1270】 dp。
【BZOJ1293】 扫描一下,用一个堆维护删除。
【BZOJ1295】 枚举判断可行。
【BZOJ1296】 dp。
【BZOJ1303】 从b位置向前向后统计下。
【BZOJ1305】 拆成三个点,并且判断是否可以完成i首歌。
【BZOJ1306】 记忆化搜索。
【BZOJ1316】 树分治把询问打包用set维护下。
【BZOJ1319】 求出原根,BSGS,线性方程弄一弄。
【BZOJ1336】 最小圆覆盖。
【BZOJ1337】 最小圆覆盖。
【BZOJ1396】 建出后缀树,一个节点代表的这一段[l,r]肯定是r-l+1,对于前面的1~l-1就是r-i+1的贡献了。
【BZOJ1398】 ①建出SAM,求这个串的最小表示。②对于每个头开始求一个hash,然后map判一判。
【BZOJ1406】 x^2=ny+1=>n|(x-1)(x+1),数很少判判重就可以了。
【BZOJ1411】 手玩一个位置的影响,只关乎两个,暴力下。
【BZOJ1412】 最小割。
【BZOJ1413】 对于[l,r]一边只有一个能改变胜负状态,那么就dp这个东西。
【BZOJ1414】 中间插空,先求一遍马拉车,对于每行正反跑一边,用O(1)-RMQ跑。
【BZOJ1417】 状态压缩下直接暴力dp。
【BZOJ1420】 同1319。
【BZOJ1429】 结论:S(2^k*m)=[m is odd] k=0?8d(m):24d(m)。其中d(n)为约数和。
【BZOJ1432】 手玩。
【BZOJ1433】 对每个拆点,in(i)->out(i)表示睡自己床,in(i)->out(j)表示i睡j的床,跑个最大流就可以了。
【BZOJ1441】 gcd。
【BZOJ1452】 2D数据结构。
【BZOJ1465】 设扔到左边的个数,然后列方程,可以得到一个绝对值式子可以用中位数做。
【BZOJ1467】 同1420。
【BZOJ1468】 树分治。
【BZOJ1482】 就是求gcd(i,j)=1的个数。
【BZOJ1483】 启发式合并。
【BZOJ1485】 这个就是个catalan数。
【BZOJ1486】 二分判是否有负环。
【BZOJ1488】 搜索每个环的大小,然后通过点的置换算边的置换。
【BZOJ1492】 按提示列dp,cdq分治。
【BZOJ1494】 状态数很少,dp用matrix加速。
【BZOJ1497】 最大权闭合图。
【BZOJ1500】 平衡树。
【BZOJ1502】 圆并。simpson。
【BZOJ1503】 平衡树。
【BZOJ1552】 平衡树。
【BZOJ1566】 注意到有个平方,我们就可以理解为两个人在取序列相同的方案有多少,那么直接dp搞了多少个,第一个人在上面一行弄了多少,第二个人弄了多少。
【BZOJ1571】 dp。
【BZOJ1572】 堆贪心。
【BZOJ1574】 BFS一下。
【BZOJ1576】 先找出最短路树,枚举每条非树边,然后就是把lca到两个点之间的边给更新,这个用树链剖分就可以了。
【BZOJ1597】 斜率优化。
【BZOJ1742】 dp。
【BZOJ1756】 gss的线段树。
【BZOJ1758】 二分+树分治。
【BZOJ1786】 考虑所有-1,显然单调最好,那么就dp第i个-1的值为j,前缀和优化下就是O(nk)。
【BZOJ1787】 LCA贪心下。
【BZOJ1789】 LCP贪心下。
【BZOJ1798】 经典打标记。
【BZOJ1800】 暴力。
【BZOJ1801】 dp。
【BZOJ1814】 插头dp。
【BZOJ1815】 点置换群算边置换。
【BZOJ1816】 二分暴力。
【BZOJ1818】 扫描线+线段树维护。
【BZOJ1821】 二分+并查集。
【BZOJ1828】 离线+线段树。
【BZOJ1906】 显然的我们枚举两个蚂蚁,分类讨论一下就可以了,估计是要用O(1)的LCA。
【BZOJ1937】 树边被非树边覆盖可以列一个不等式发现就是求顶标,KM算法算一下。
【BZOJ1977】 考虑每条非树边用lca求一求就好了。
【BZOJ1999】 求出直径,在直径上two pointer搞一搞。
【BZOJ2151】 加入每一个点用链表维护一下,每加入一个点将相邻两个点-中间的点扔到队列,并将这三个点合并成一个点。
【BZOJ2177】 转化成切比雪夫距离,那么对于一个点i分成8部分,那么有用的就是跟i最近的点,那么一个点最多8条边。跑一个MST就好了。
【BZOJ2182】 求出无向图的绝对中心之后瞎搞搞就可以了。
【BZOJ2362】 把重心当根统计直径不超过n的二叉树个数就可以了。
【BZOJ2368】 枚举每一个子树,然后提重心dfs判重构就可以了。
【BZOJ2466】 高斯消元。
【BZOJ2521】 考虑加入的边,那么跟它联通的边比它小的这个图不能联通,那么就是对于每个边加了一些值之后不连通,那么考虑最小割。
【BZOJ2560】 暴力dp。
【BZOJ2561】 跟2521同样做就可以。
【BZOJ2569】 提重心暴力组合数维护。
【BZOJ2690】 离线算法就是把所有串建一个trie然后dfs序就可以,在线只要把dfs动态维护,用重量平衡树就可以。
【BZOJ2740】 将串reverse下,找到一个最小表达式,找这个位置到底的重复串,将这部分看成s[0..i-1],再对剩下的做一个最小表达式就可以了。
【BZOJ2750】 对每个点dijkstra一遍,然后考察每条边有效贡献就可以了。
【BZOJ2783】 set维护。
【BZOJ2785】 跟2569差不多。
【BZOJ2812】 二分+树分治类似1758做法。
【BZOJ2822】 考虑必须选n个,每次必须划分成两队,那么就是catalan数。
【BZOJ2932】 树上dp。
【BZOJ3103】 同3350。
【BZOJ3166】 枚举次大值就能得到可行区间用可持久化trie就可以了。
【BZOJ3219】 跟2812同样做。
【BZOJ3226】 就是一个在线段树上打打标记。
【BZOJ3227】 考虑节点个数树高列两个dp推来推去就好了。
【BZOJ3251】 考虑一组数列不能构成三角形最多不超过46个,那么长度小于46就暴力。
【BZOJ3252】 考虑叶子到根最大的肯定选,那么用线段树维护一下就可以了。
【BZOJ3262】 三维偏序,排序cdq区间维护。
【BZOJ3276】 按照到初始点的距离排序,每次取肯定是在可行范围内取最小重量,然后把取出来的扔到数组里面不停的做,知道不可执行为止。
【BZOJ3302】 取树最中间的边,然后求出两块的重心,那么两个重心一定在这两个求出来的重心的链上,调整下就好了。
【BZOJ3322】 火车的那些点都是一样的就缩点,剩余的求最大生成树树上倍增求求就可以了。
【BZOJ3323】 注意到只有[l,r-1]不会修改,就在l之前加个0,把r加到r+1上。
【BZOJ3324】 可以看出来前面肯定有一坨1,那么剩余移动数不多直接考虑dp。
【BZOJ3325】 manacher做一遍把相同的位置找出来。
【BZOJ3326】 考虑每一位的贡献拿组合数瞎算算就好了。
【BZOJ3350】 manacher求出所有相等不等的关系,相等用并查集维护,不等连边。
【BZOJ3553】 树链剖分维护上面的值用二分找下位置。
【BZOJ3586】 枚举字符串出现的集合和当前匹配到的字符串的位置,这个可以用gauss来消元,状态数大概不会超过500。
【BZOJ3589】 树链剖分+容斥。
【BZOJ3321】 matrix tree找规律。
【BZOJ3731】 块状树。
【BZOJ3754】 边权大小不大,枚举平均数,跑个MST。
【BZOJ3756】 在Trie上建SAM,跑下S串就可以了。
【BZOJ3757】 树上莫队。
【BZOJ3748】 面向数据找规律。
【BZOJ3799】 枚举前缀相等长度,后面取最小字典序。
【BZOJ4180】 建出T的SAM,f(i,j)表示i开头j结尾的最短长度,二分倍增下。
【BZOJ4257】 二分下最小值,然后转化成圆链,最后肯定要成l1l2l3..lnr1r2..rn这样看下不降序列是否达到k就可以了。
【BZOJ4300】 按位dp。
【BZOJ4302】 分类讨论。
【BZOJ4303】 kd tree来打标记。
【BZOJ4304】 缩点变成DAG,讨论每个点的进出可行点集用bitset维护。
【BZOJ4305】 首先gcd(*)=d可以转化成d|gcd(*),这会耗费一个log,之后就是组合数搞一搞就可以了。
【BZOJ4310】 二分下最小串,从后往前找就可以了。
【BZOJ4311】 按时间分治[l,r],在这个时间出现的向量找出来,答案肯定在凸包上。
【BZOJ4379】 显然我们枚举每个删边,那么我们可以dp出上面一块的直径和子树的直径,做这个就只用搞出第一长第二长第三长的链就可以了,在记录一个向上延伸。
【BZOJ4380】 可以先dp出一段区间用的价格的代价,然后dp区间的最大花费。
【BZOJ4381】 按步数大小分块跑一下。
【BZOJ4386】 每个点拆成3个,记录长度为i的方案数,记录下一堆矩阵倍增搞一搞就可以了。
【BZOJ4401】 求下被整除d个数的子树个数推一推就好了。
【BZOJ4402】 需要观察出一个性质,本质不同的就两种序列,然后组合数算算就可以了。
【BZOJ4405】 一般图匹配。
【BZOJ4407】 稍微推推式子就可以了。
【BZOJ4408】 CC原题。
【BZOJ4414】 c*f_{n+m+1}=f_{n}*f_{m}+f_{m+1}*f_{n+1}。
【BZOJ4416】 注意到n>21时不存在解。用f_{S}表示用了S集合内的元素要到串的第f_{S}位才能表示完全,再用一个转移状态函数表示对于第i位接受了个j要到第几位。
【BZOJ4417】 推一下式子可以发现是个矩乘。
【BZOJ4419】 set。
【BZOJ4421】 乱搞。
【BZOJ4424】 搜一个dfs生成树考虑返祖边就可以。