再来一波BZOJ？

2015年终于在BZ刷进了第一面，为了今年不掉下去，再来刷一波BZOJ吧...

3.30 update:暂且撒个花吧...这个坑也是在无意识中随便开的...没想到竟然填完了...并不能找到什么好题做啊T_T

4.8 update:最近做的杂题也扔上来吧。

完成数：70

[bzoj4350] 原来不会捉，今天一看范围只有300，那就直接区间dp了。

[bzoj3262] 经典题。我本来打算试试3维k-d tree的，想想还是算了...

[bzoj1112] 傻逼的题，傻逼的我。

[bzoj1115] 差分变成阶梯nim。

[bzoj1106] 直接贪心。树状数组维护。

[bzoj1111] [tex]f[i],g[i][/tex]分别表示到第[tex]i[/tex]位进位和不进位最少砝码数与方案数，转移即可。

[bzoj2180] 等价于找绝对中心。预处理最短路，对每个点的dist排序，然后相当于球若干条折线的最低点。

[bzoj4002] 神数学题，感觉我数列白学了T_T不过出题人sxb(i)k(e)，模数7528443412579576937乘2会爆longlong，简直逗我笑

[bzoj3979] 玄学大爆搜，bitset大法吼！

[bzoj2599] 树分治。

[bzoj4328] 过了四年我终于会捉这题了...分度数奇偶情况分别列异或方程，bitset优化。

[bzoj1122] 枚举操作2的次数，贪心。单调队列可以优化到[tex]O(n)[/tex]。

[bzoj2626] 众所周知的题目...

[bzoj4314] 即SRM502hard。dlh的数学方法太神了看不懂...正解是一个非常厉害的dp，不过复杂度好像很玄学，似乎上界是[tex]O(k\log ^2 n)[/tex]？

[bzoj3681] 你们非常熟悉a+b problem那一套理论，但出来出去的数据结构啊，都too simple！

[bzoj3007] 二分+对偶图bfs。略卡常。

[bzoj1052&&3760] 二分答案，每次放的正方形一定覆盖了最小覆盖矩形的一个角，爆搜判断。

[bzoj2125] 麻麻窝终于会静态仙人掌啦！找环的过程异常难写T_T

[bzoj4321] 手推了下dp感觉不难的样子...于是我就oeis大法了...

[bzoj4401] 抄了个多校题的结论，然后dfs一下就好了。

[bzoj2711] 并不会证明结论...

[bzoj4385] 终于A了这破题。set超时，st表爆内存，单调队列维护就好了。

[bzoj4403] lucas定理。

[bzoj4108] [tex]k[/tex]个搬运工只会影响1号点的出度，直接跑费用流就好了。

[bzoj3149] 爆搜每一个联通块可A。

[bzoj1758] 树分治+二分答案+单调队列。

[bzoj3504] 即SRM556 hard。

[bzoj4405] 真的是很神的图论题啊...

[bzoj3924] 暴力爬重心。

[bzoj2671] 除掉gcd，枚举较大数，枚举约数后莫比乌斯反演。复杂度大概是[tex]O(n^{3/4}\log n)[/tex]？

[bzoj3944] 神奇黑科技。花式记忆化可以做到[tex]O(n^{2/3})[/tex]。不过用了unordered_map很卡常。

[bzoj3456] 补习了一下多项式逆元的姿势。感觉还是不难写而且很优美的>_<跑起来确实比我原来的分治fft快多了，不过复杂度优势并不明显...

[bzoj2124] pear很久以前讲的一道好题。利用排列的性质可以转变为判断回文串。越来越怀念pear时代的讲课了T_T

[bzoj3576] 用烂的idea，转移只有根号个，暴力SG即可。

[bzoj4406] 考场上输错样例的题...正解好神啊...

[bzoj3319] 离线倒过来做就好了...很巧妙的做法。

[bzoj4407] 经典莫比乌斯反演。现在已经不会推了T_T

[bzoj4026] 主席树直接搞。

[bzoj4372] 一个点分治板子调了一个小时，感觉最近这代码能力药丸啊...

[bzoj4416] 一开始推错结论以为大暴力就行了。状压dp表示每种序列在序列自动机的最后出现位置，暴力转移。最大点过不去可以感性认识一下[tex]n[/tex]比较大的时候肯定是NO。

[bzoj4419] 在加边删边的时候更新答案就行了。

[bzoj4421] 转成前缀和，直接统计。

[bzoj3581] STL狗的胜利(大雾→_→)清澄上只有80分...

[bzoj3561] 暴力莫比乌斯函数推一下，复杂度是调和级数。

[bzoj4444] 语文题。倍增环为链，dfs一遍。

[bzoj3716] bx2k教我的题目= =

[bzoj4426] 若一个区间覆盖了另一个区间，那么这个区间要么没卯用，要么单独成一组。去掉这些区间以后排个序，左右端点都是单调的，直接dp就行了。最后枚举单独成了几个区间。

[bzoj4428] 暴力记忆搜。不大会证复杂度。

[bzoj3206] 先强制选特殊边跑mst，mst里的其他边是必选的，缩起来，暴力枚举特殊边选哪些，更新答案就行了。

[bzoj2655] 正解似乎是推出一个卷积类似物每次将范围缩小一半。不过列出递推式容易发现答案是个多项式...暴力跑跑dp然后拉格朗日插值就行了...

[bzoj4310] 二分答案+后缀数组。

[bzoj4459] 当年不会做的小学奥数题。

[bzoj4468] 当年不会做的sb题。怀疑数据有点问题？

[bzoj4465] 当年不会做的sb题。把斯特林数递推式改一下就行了。

[bzoj3600] 线段树维护序列。利用重量平衡树打tag的方法维护所有数可以[tex]O(1)[/tex]比较两个数的大小。

[bzoj4380] [tex]f[i][j][k][/tex]表示[tex][i,j][/tex]这个区间最小值为[tex]k[/tex]的答案，暴力枚举转移。

[bzoj4378] 把大于[tex]s[/tex]的数变成[tex]s[/tex]然后判断和即可。线段树维护。

[bzoj4347] 智商太低想了半天不知道[tex]m[/tex]的范围有什么用。事实上按从小到大排序以后dp转移就可以做到[tex]O(md)[/tex]了。

[bzoj4519] 最小割树。

[bzoj4382] 每种颜色会划分出若干段，对每个位置属于哪些段hash，直接统计。

[bzoj4521] sb数位dp。

[bzoj4514] 显然是二分图，跑费用流即可。一个sb错调了一上午。

[bzoj4517] sb题。组合数乘错排数。

[bzoj4516] sam板子题。

[bzoj4518] 上古斜率优化。

[bzoj4542] 球个后缀和，暴力上莫队。记得特判[tex]p=2[/tex]和[tex]p=5[/tex]。

[bzoj4546] 卡常卡常卡常卡常卡常卡常卡得意识模糊。为什么claris的常数跟我差了十几倍啊...[update]似乎这个题因为版权被和谐掉了...

[bzoj3614] 比较类似fft的做法。每次消掉一位。

[bzoj4343] gcj的神题。先二分答案，然后令[tex]f[i][/tex]表示i元钱到[tex]i+\frac{1}{G}[/tex]元钱赢的场数与期望赢的场数的差的期望。dp出来之后结论是如果[tex]f[R]\geq 0[/tex]，那么当前二分答案合法...感性认识一下很科学...