SanSiroWaltz's Blog

最近真是无比颓废啊，还是有一些明确的计划比较好

至于计划名没想好，就叫"xxx"吧

学习recursion神犇，开了一个50题的坑，不过感觉屯题太麻烦了，就不开这个坑了

题目来源：bzoj，uoj，传统弱省的省选题

UPD:

2015.3.19 bzoj终于AC500题了，好开心

2015.4.21 完结啦

50

【bzoj 3810】 一个比较神奇的结论是可以用切一刀分成两部分，发现这个结论后就是很sb的dp

【bzoj 3156】sb的dp优化题

【bzoj 3866】陈老师的水题，我觉得这种难度的题就没必要count了

【bzoj 3905】还是陈老师的题，dp套dp，抢到了fb(lavendir除外)

【bzoj 3861】题目名称跟题目一点关系都没有。。。显然可以用容斥计算答案，具体方案数用dp算一下就好了

【bzoj 3309】jcvb的神题，和jzp那道题有点像，主要是要想到如何进行线性的预处理

【bzoj 3860】看到模数就知道该要写fft，先用分治+fft求出n个1次单项式的乘积，求出错排后再用一次fft可以求出答案。竟然跑到了rank1，好开心

【bzoj 2666】求出每个分界点后对每个区间的二次函数求最值

【bzoj 3139】记忆化搜索

【bzoj 3900】很容易证明必然有一种最优解每只麋鹿必然会保留至少1只角，因此答案就是n-max环的数量，先用状压dp求出每个集合是否能组成环，再来一个dp求出最优值。代码最长，速度是倒数第二的将近10倍，空间也是最大的

【bzoj 2118】很神的一道题，对a[1]取模可以转化成最短路

【bzoj 2121】暴力dp，非常sb的题

【bzoj 3897】很显然要尽量取价值最大的，我们先求出最大的是那一个，判断它最多能取多少次，然后对左右递归处理

【bzoj 3622】大于等于k的方案数是很好求的，剩下只要减一下就行了

【bzoj 3333】比较有趣的一道题，先统计每个点之后比他小的数的个数，记为f[x]，每次修改就是将x以后的比a[x]小的数的f值减掉，而这个值只会被减掉一次，用线段树找一下就行了

【bzoj 1416】容易发现抽到每个球的概率是不变的，写个高精度就没了

【bzoj 2173】经过简单的推(da)导(biao)会发现这题就是个sb题

【bzoj 2157】树链剖分模板题，好久没写过了再来写一次

【bzoj 2172】显然要根据n的唯一分解形式分情况讨论。原题需要打方案，所以要用到奇怪的分解质因数的方法。但在bzoj上不用打方案，所以可以用枚举+miller rabin水过去

【bzoj 2163】网络流建模是比较显然的，然后可以根据图的特殊性用dp求出最小割

【bzoj 3916】很显然要求的串是原串的前缀和后缀，分别dp一下

【bzoj 2821】经典的分块，预处理出每对块之间的答案，剩下的点暴力统计

【bzoj 2750】对每个点求最短路径图，必然得到一个DAG，然后正反两遍求出到每个点的方案数，对最短路径图的边进行统计

【bzoj 3131】就是一个数位dp+heap的无机拼接，挺无聊的

【bzoj 2152】只需把题目下方的source无视掉就好了

【bzoj 3503】将第一行的数列为未知数，递推算出每个方格用这些未知数表示的形式，对最后一行可以列出异或方程组

【bzoj 3922】无脑分块

【bzoj 2124】挺nice的一个problem，可以将问题转化成动态维护子串是否相等

【bzoj 2131】sb题，把式子列出来后发现每个馅饼可以表示成平面上的线段，将左端点从大到小排序后树状数组维护

【bzoj 2150】sb网络流，那时候集训队人出的题怎么这么sb

【bzoj 2125】比较水的仙人掌题，比起mx的虚仙人掌弱爆了。。。

【bzoj 2162】一道无机拼接题。网络流建模还是挺帅的，接下来就是比较sb的dp了

【uoj 87】毛爷爷的仙人掌，题解毛爷爷已经帮我在uoj上发过

【bzoj 3930】做法大概就是暴力枚举后，暴力算莫比乌斯函数，比较小的数可以先预处理一下

【bzoj 3925】做法就不多说了，令人值得回味的一道题

【bzoj 3868】枚举距离标号后随便做

【jsoi2014 r3d1 story】由于版权问题就不多说了，去年自己好sb

【bzoj 3941】usaco的题，当时想到了分治，但没想到可以将边按极角排序直接扫一遍

【jsoi2014 r3d1 cluster】sb题

【bzoj 2806】后缀自动机好神好神，不过话说这题思考难度是noip级别啊。。。

【bzoj 2209】其实很久以前就看过这题了。。。有一个很神奇的结论，知道了就变成了裸的splay

【bzoj 1494】将连通性视作状态矩阵乘法，以前觉得这个东西很烦，现在发现其实也挺好写的

【bzoj 3990】容易证明每种方法都可以变成对于[tex]i[/tex]从小到大操作。不妨按照顺序考虑每一次操作，最多只存在两个块出现问题。在这两个块中穷举交换方法，check后继续递归下去，到达底层后，直接将答案累加操作数的阶乘。

【bzoj 3992】暴力寻找一个x，使得[tex]0,1,x,x^{2},...,x^{m-2}[/tex]是mod m的完全剩余系，取对数后就是裸的分治+fft

【bzoj 3991】比较神奇的结论是，答案就是所有dfs序相邻的点的距离和再加上首尾两点距离和，剩下就比较简单了

【bzoj 2780】题面比较逗。。。将模板串建成sam，问题转化成求子树中有多少种不同的数，转成dfs序后离线处理

【bzoj 3997】其实我只想吐槽题目名是什么意思。。。不错的cf A题

【bzoj 4010】hnoi竟然出了前不久bc的原题我也是醉了。。。线段树直接秒杀。。。

【bzoj 3994】这题有一个很厉害的结论：[tex]d(nm)=\sum_{i|n}^{ } \sum_{j|m}^{ }(gcd(i,j)=1)[/tex]，然后就很好做了

【bzoj 3996】最大获利。。。