其实主要是做那几场多校的题T^T（虽然杜教那场我也是去打的但是全程一直被2048卡常数所以其他题也没有去看

[3.20]今天总算有时间把这50题交掉了，完结撒花O(∩_∩)O~~。

现在做了几题

50

【BZOJ3850】ZCC Loves Codefires 直接按照[tex]\frac{K_i}{E_i}[/tex]排序贪心就好了

【BZOJ3856】Monster 就是一个一个循环节考虑，特判几种情况就行了

【BZOJ3858】Number Transformation 当操作到差不多[tex]\sqrt x[/tex]次后每一次增长的值就不变了，所以只要算[tex]\sqrt x[/tex]次就行了

【BZOJ3851】2048 场上一直被卡常数。。其实就是只考虑2的幂次然后跑类似背包的东西，要预处理逆元啥的来算组合数。

【BZOJ3847】ZCC Loves March set,map什么乱搞，缩到一起的点一起考虑复杂度就对了。开始一个地方忘取模调了一个多小时。

【BZOJ3853】GCD Array 可以用莫比乌斯反演推出一个式子来，然后就用树状数组维护前缀和[tex]O(n\sqrt n \log n)[/tex]大力搞。

【BZOJ3841】ZCC Loves Intersection 每一对线段相交的概率是独立且相等的。然后可以推出来是个式子用高精度搞。

【BZOJ3844】ZCC Loves Cards 先大暴力选出集合，然后假设没有圆周的限制是不是比现在最优的答案优，如果是的话再枚举圆周的排列判断。因为是随机数据所以跑的还是很快的。

【BZOJ3846】ZCC Loves words 这种数据范围和题面显然AC自动机加矩乘，但是因为有出现位置的影响所以不能无脑搞。因为模数是三个小质数的乘积，对于每一个小质数只有一百多种不同的矩阵，于是就可以一个循环节一起乘在最后一个一个乘上多余的。最后用中国剩余定理合并一下就好了。开始快速幂写错WA了好几发实在是不能多说。

【BZOJ3860】Permanent 令对角线上选出[tex]i[/tex]个数的所有方案的权值和为[tex]F_i[/tex]，则显然[tex]F_i=[x^{n-i}]\prod_{i=1}^n (x+a_i)[/tex]，这个可以用分治FFT算。显然边长为[tex]m[/tex]时答案就是[tex]\sum_{i=1}^m F_i \times D_{m-i}[/tex]其中[tex]D[/tex]为错排方案数，有递推式[tex]D_i=(i-1)(D_{i-1}+D_{i-2})[/tex]。直接用FFT算卷积就好了。（开始连标题都看不懂直接就暴露了我拙计的数学水平

【BZOJ3861】Tree 把非空集合当做点，图中每一个点也作为一个点，如果第[tex]i[/tex]个点不在第[tex]j[/tex]个集合中，则[tex]i[/tex]和[tex]j[/tex]之间连一条边。显然答案就是这个二分图的最大匹配的个数。可以用[tex]dp_{i,j}[/tex]表示前[tex]i[/tex]个集合中有[tex]j[/tex]个被匹配的方案数，只需要考虑前面剩余的点来匹配这个集合以及这个集合的点去匹配前面的集合，还是挺好转移的，时间复杂度[tex]O(n^2)[/tex]

【BZOJ3840】ZCC Loves COT 就是各种差分然后搞，我为了图方便复杂度中有一个[tex]nq[/tex]，这样居然都能过。

【BZOJ3843】ZCC Loves Army 把树用左儿子右兄弟的方式表示，那么第一个操作就可以变成删除插入[tex]O(1)[/tex]条边，第二个操作可以在把一个优先级最高点点权设为1求链和注意要特判公共祖先，第三个操作是询问点到根路径中的点数。最后还要用[tex]n[/tex]棵平衡树来维护父子关系以及顺序。BZ上的数据有误，我开始错的和标程一样然后就过了，改对了就WA了。

【BZOJ3817】sum 见清华集训题目练习那篇博客

【BZOJ3879】SvT 似乎是DZY搬运的一道COCI题目的弱化版，先把后缀sort然后扫一遍，LCP一定是单调的若干段，用栈维护就好了。

【BZOJ3168】【HEOI2013】钙铁锌硒维生素 先判断第[tex]i[/tex]个备用机器人取代了第[tex]j[/tex]个机器人是否仍然线性无关，我好像是消了一个逆矩阵啥的，年代太久远记不真切了，然后就直接匹配就好了（字典序最小有点蛋疼）。

【BZOJ3615】MSS 把所有点按照[tex]x[/tex]轴排序后，一定可以把这些点分成[tex]y[/tex]单调增或减的至多[tex]\sqrt n[/tex]个集合，然后分每一个集合进行所有操作，这个可以用线段树的分裂、合并维护，用势能分析可以得到复杂度是靠谱的。

【BZOJ3875】【AHOI2014】骑士游戏 用堆每一次选取最小值更新，出烂了的题目。

【BZOJ3876】【AHOI2014】支线剧情 上下界网络流直接上就好了。

【BZOJ3824】【Usaco2014 Dec】Guard Mark 无脑状压就好了。

【BZOJ3825】【Usaco2014 Dec】Marathon 线段树维护在每一个位置修改对答案的贡献以及区间的答案，每一次修改一定是取贡献最小的，直接维护就好了。

【BZOJ3826】【Usaco2014 Dec】Cow Jog 每一个人跑的一定是个区间，如果区间相包含说明就相交了，直接贪心搞就好。

【BZOJ3881】【COCI2015】Divljak 先对初始串建AC自动机，得到fail tree，每一次对查询串跑过的点建虚树，相当于询问虚树的点权和之类的东西，直接搞就好了。

【BZOJ2594】【WC2006】水管局长数据加强版 离线倒着做，LCT维护最小生成树。

【BZOJ3434】【WC2014】时空穿梭 无脑上莫比乌斯反演，然后把一个多项式状物体给展开，然后直接做就好了。

【BZOJ1453】双面棋盘 离线动态图，显然就可以对时间分治+按秩合并并查集做，跑的挺快。

【BZOJ3159】决战 用treap维护树链剖分，然后链反转相当于把这条链上的treap合并起来倒序再分配回去，还是不难写的。

【BZOJ3870】Our happy ending 数据范围挺吓人的其实直接无脑暴力就好了，状压现在哪些数可以表示然后暴力枚举放哪个数，常数还是挺小的。

【BZOJ3864】Hero meet devil 把最长公共子串的那个DP数组状压起来DP，因为那个数组差分后任意位都是0或1所以状态只有[tex]2^n[/tex]

【BZOJ3884】上帝与集合的正确用法 开始一直想着解[tex]2^x=x[/tex]然后发现爆炸了，其实可以用欧拉定理模拟，然后如果模数是偶数就把2的幂次的部分和奇数部分分开来再用中国剩余定理合并就好了。

【BZOJ3866】The Romantic Hero 直接暴力DP前缀加暴力合并。

【BZOJ3867】Nice Boat 和pyx那道CF D差不多，用平衡树把相同的一段一起维护复杂度就对了。

【BZOJ3862】Little Devil I 一个操作时反转边权，可以把另一个操作当做反转点权然后一条边实际的边权定义为他的两个端点以及自己的权值的异或，然后就直接树链剖分对于虚边直接搞就好了。

【BZOJ3888】【Usaco2015 Jan】Stampede 把关键的时间点排序用set维护一下当前的线段顺序就好了。

【BZOJ3889】【Usaco2015 Jan】Cow Routing 直接无脑最短路。

【BZOJ3890】【Usaco2015 Jan】Meeting Time 暴力DP大法好。

【BZOJ3891】【Usaco2015 Jan】Piggy Back 当成三个出发点分别跑最短路然后枚举交汇点算答案取最小值就好了。

【BZOJ3892】【Usaco2015 Jan】Marathon 暴力DP大法好

【BZOJ3893】【Usaco2015 Jan】Cow Jog 每一头牛跑过的一定是一个区间，然后从后往前扫就好了。

【BZOJ3885】【Usaco2015 Jan】Cow Rectangles 枚举最左端的牛和最右端的牛，然后往上、下扫出极限的边界更新答案就好了。

【BZOJ3886】【Usaco2015 Jan】Moovie Moving 预处理出看了一个电影之后可以看哪些，然后DP一个状态最迟能看到什么时候，状压搞就好了。

【BZOJ3887】【Usaco2015 Jan】Grass Cownoisseur 先把强连通分量缩掉，然后把所有点分成1所在强连通能到达的和不能到达的，把这两部分之间的边反向跑最长路就好了。

【BZOJ2173】整数的lqp拆分 把斐波那契数拆开就发现是可以直接递推的。

【BZOJ3895】取石子 DP状态是当前1的个数以及除了1以外所有石子的石子总数加上堆数-1，然后无脑记忆搜。

【BZOJ3896】求和 伯努利数直接上，如果用多项式的话可以做到[tex]n\log n[/tex]但是好麻烦的样子。

【BZOJ3894】文理分科 出烂了的最小割模型，至于约束只要新建点然后和约束的点连流量无穷的边就好了。

【BZOJ1093】【ZJOI2007】最大半联通子图 显然选取的一定是缩掉强连通后的DAG上的最长链（点权是强连通分量的大小），然后直接DP就好了，注意缩点之后会有重边，贡献会被多次计算。

【BZOJ1095】【ZJOI2007】Hide捉迷藏 树链剖分，然后可以每一个点套一个堆来维护，考虑每一对点的贡献，分别分为路径中没有边在LCA所在重链上和路径中有边在LCA所在重链上维护，然后就各种堆和线段树搞搞就好了，还是挺好写的。

【BZOJ1411】【ZJOI2009】硬笔游戏 分治，发现当操作了[tex]2^n(n>1)[/tex]次后每一个位置都相当于两个数异或起来，所以可以直接用类似快速幂的方法做。

【BZOJ1413】【ZJOI2009】取石子游戏 开始在YY区间DP的做法，然后感觉好像不难的样子去搜了一发题解。然后就看到了网上的鬼畜做法。。。于是我也就直接混关过了。