我又来作死了== 然而我刷的题都是水题。。。神犇们都很鄙视我。。。

orz tzg orz 所有吉林神犇。。

但愿我NOIP能过。

虽说是八月刷题记录，但是有好多7月的题。。基本都是BZOJ的。。

在例题里的我就不说了。。还有这里只记录一些比较有意义的题。。

还有这里是没有代码的！ 因为我代码写的太难看了

CPU监控
bzoj3064
这个必须整理下。。写完太有成就感了。。
大意就是让你维护区间最值，区间曾经的最值，有区间修改区间加某数两种修改
然而就这两种修改搞得我好难受
一开始直接写的普通线段树，发现普通的标记会出现一些身体不适，对于那个区间曾经的最值。
因为有的时候你有一个add标记，这个add标记没有下传，后来又来了个lazy标记，你这个add标记就没了。
然后曾经的最值就不对了。。。。
解决方法是 维护区间最值 曾经的最值 普通的 add lazy标记 曾经最大的 add lazy标记
这样就完美解决了。。
然而写起来巨麻烦。。。。

problem c
bzoj2302
神DP
设比i大的可行编号数量为 a[i]
那么a[i]>n-i+1才是可行方案 先预处理a[i]
设f[i][j]为i以上剩余j个没选
那么f[i][j]=Σf[i+1][j-k]*c[j][k] 枚举k 这k个可以在j个里随便放所以是c[j][k](组合数)
c数组递推就行了

朋友圈
bzoj2744
神TM二分图题。。
经过观察 发现B国都是奇数跟奇数连边 偶数跟偶数连边。。
然后建立反图之后。。。 B国就是个二分图。。
然而A国怎么办。。
继续观察 发现A国的反图和B国的反图是反的。。。
A国的最大团最多只有2
所以枚举一下A国选0个 1个 2个就行了。。（考试时莫名WA了一个点，不要在意这些细节。。。）

子矩阵
洛谷2258

普及比提高难系列。。
看到数据范围首先想到状压
首先把列状压了 枚举某列选不选。。
然后就相当于降维了 变成序列上的问题了。
f[i][j][s]表示列状态为s时，必须选第i行，选了j行的答案
f[i][j][s]=min(f[k][j-1][s]+w[i][k],f[i][j][s]); w[i][j]是代价 按照题意预处理一下就行了。。
总复杂度O(C(m,c)*n^2*r) 可以过 应该有更优的做法？

[Usaco2015 Jan]Meeting Time
bzoj3890
拓扑排序+DP
由于最大边权<=100 所以一条路径的边权和最大也就10000 那么我们可以选择做一个背包一样的东西 设f[i][j]为到i点走第一种路径是否能凑成j 设g[i][j]为到i点走第二种路径是否能凑成j 既然是可行性问题 就应该上bitset了。。。 用bitset优化一下背包 就水过了（好像不优化也能过 [Hnoi2010]Bounce 弹飞绵羊
bzoj2002
比较特殊的link-cut-tree
因为这个是有向边 所以换根深度不会改变了，就不用reverse了，直接splay就行
link操作直接把原来的干掉加上新的就行了。。

[Heoi2013]Eden的新背包问题
bzoj3163
泛化背包。。。。。神了
这题中间要删一个物品，注意是一个物品。。。
我们可以前n个物品做个背包 后n个物品做个背包
预处理出f[i][j]和g[i][j]
然后再把f[i][*] g[i][*]看做物品 再做一个小的dp
那么最后凑出来的就是f[k-1][i]+f[k+1][m-i] 取一下max即可

[Usaco2006 Oct]Building the Moat护城河的挖掘
bzoj1670
裸凸包算法。。。
凸包大概就是先把点排序。然后维护一个栈。
然后看看栈顶元素和栈顶的下一个元素 以及下一个点的角度关系 这个用叉积判断。
就可以轻松做出一个凸包啦

Tyvj 1729 文艺平衡树
bzoj3223
splay的题。。第一次写感觉萌萌哒。
首先splay要写双旋的 因为单旋不能改变树的结构
还有可以认为一次双旋相当于某个节点跳过了他的父亲。。
然后撸玩splay 发现这题好像需要维护编号 维护完了把左右子树交换一下 再把编号换回来就行啦！
然而并不是这样的。。。。。。。。发现如果用splay维护编号 翻转区间变得很麻烦。。。
于是求救JL神犇，JL神犇表示维护个size就好啦！
splay操作是不会改变顺序的 而且一开始建的树就是1-N的 所以维护size询问第K大相当于维护编号了。。
然后左右子树就可以随便换了。。。然后就过了。。
我会说这玩意我撸了一下午？

[Noi2015]软件包管理器
bzoj4196
NOI出这题什么鬼 裸树剖+维护dfs序。。。。
在这里整理一下树剖好啦 第一次写树剖和dfs序
树剖就是把整棵树剖成logn条链 再把这些链按照顺序排好放到线段树中 这样就可以轻松的维护链上信息了
具体实现就是把树上的链分成两类 一类是重链 一类是轻链 轻链长度最多只有1
重链是指重儿子所在链 某个点的重儿子是子树个数最多的儿子
这样维护一些变量：
num[v] 以v为根的子树的节点数
deep[v] v的深度
fa[v] v的父亲
son[v] v的重儿子 即num[u]最大的
top[v] v所在的重链的顶端节点
tree[v] v在线段树中的编号
pre[k] 线段树中的标号所对应的点
然后获取信息的话：
设f1=top[x] f2=top[y] 令deep[f1]>=deep[f2]
这样就再线段树中查tree[f1] tree[x] 然后令x=fa[f1] f1=top[x] 迭代下去
知道f1==f2 然后最后查一下tree[x] tree[y] 就行了。。
一条重链 一条轻链的查上去了就。。。
真是神了。。。。

Dynamic Rankings
bzoj1901
区间第k大带修改 那么就是树状数组套主席树喽。
修改还是很好想的 就是把每颗树看成前缀和 修改前缀和 即把某颗树的x位置+delta
查询就恶心了。。。想了好半天 因为这些树只有拼起来才是完整的 然而他们的指针并不完整。。
求救于JL神犇 JL神犇表示两个数组就搞定了。。。
开两个数组，一个记录[1,l-1]的树的根 一个记录[1,r]的树的根
这样query的时候的sum=Σrr.sum-Σll.sum rr和ll分别为两个数组
二分下去 如果查左边就另所有的rr[i]=tr[rr[i]].l ll[i]=tr[ll[i]].l 顺理成章的又成为了子树的根
我都想贴代码了有木有！！！！

Xorequ
bzoj3329
wfy神犇推荐的题，搞了半天。。。一点也没想到会是数位dp。
首先第二问随便打打表。。诶 2 3 5 8 13 fib数列？瞎猜了
然后看第一问。。打表拆成二进制发现。。对于每个满足条件的数，二进制表示出来后，没有两个1挨着。
就都是000101010这样的。。或者00001000001这样的。。
然后我感觉这个可能是按指数增大的 没准能暴力算
然后花了好长好长时间做了一个知道上一个数算下一个数的函数== 然并卵
10^9秒出 10^18。。。出不来。。
由于10^18过大 无法分块打表。。
尼玛究竟是啥啊。。。。 瞄了一眼题解 数位DP。。。
f[i]表示开头为0的合法数量 g[i]表示开头为1的合法数量 (都是有i+1位,注意是i+1)
f[i]=f[i-1]+g[i-1] 这个是很明显的。。就是多加了个0
g[i]=f[i-1] 多加个1
然后按位统计就行了。。。
水题本质啊啊啊啊啊啊！

[Usaco2007 Nov]tanning分配防晒霜
bzoj1707
一看就是网络流，怒敲dinic算法。。然后怒TLE。。。
然后加小剪枝。。。还是TLE。。想了想好像可以贪心。。然后怎么瞎写也不对。。然后求助题解了。。
真是非常巧妙的贪心。首先要对牛的右区间排序，再对防晒霜的spf排序。然后能选多少就选多少。
这个贪心的正确性是基于两个方面的：
1 一头牛用了某个防晒霜，那么一定要选取合适范围内最低的spf 这样不会对后面的牛产生影响。。
2 如果某个牛用了防晒霜，别的牛用不了了，那么其实这两头牛是等效的，给谁都行。。

[SCOI2008]奖励关
bzoj1076
第一次见状压跟期望结合的。。有点蒙。。
不过牢记一点：这一步的期望=(上一步的期望+这一步的影响)/影响的概率
然后列出方程f[i][s]表示剩余n个奖励 已经拿过了的东西状态为s时的期望得分
f[i][s]=f[i+1][s’]+w[j] or f[i][s]=f[i+1][s]

[HAOI2006]聪明的猴子
bzoj2429
网上题解都是最小生成数啊。。。真是很没有意思啊
这里说一种不同的解法。。
首先我们可以发现暴力是M*N^2的 就是看每一个猴子是否可以走完全程 这个复杂度我们无法接受
但是有一个小性质 即跳的远的猴子能走完全程 跳的更远的更能走完全程 满足单调性。。
然后我们把所有猴子排下序。。二分+判定即可。。这样就是logM*N^2了
2333跑的飞快 比最小生成树快

[HAOI2011]problem a
bzoj2298
这题神优化方法。。
首先我们转化一下问题 有a个人比他高 b个人比他低 那么意味着有n-a-b个人和他相同（包括他自己）。。这些人在[a+1,n-b]之间
这样就转化成了区间覆盖问题 有一堆区间 每个区间有个权值 选出尽量少的区间让权值最大 权值即为相同的人数
f[i]=max(f[j-1]+sum[j][i])
然后我就不会优化了。。这个由于Max里面是两个东西 没法扔进树状数组。。好像也不满足单调性。。
然后我就看题解了。。。题解告诉我（copy):
考虑到大多数sum[j][i]为0，为冗余数据，不必枚举，所以我们建立一个数组match[i][j]来表示第j个数k使得sum[k][i]不为0（c++可以使用vector），减少决策的枚举量。
神TM减少枚举量！这TM不是暴力+剪枝吗？神TM剪枝！
orz 有没有更好的优化方法呢。。。 @吉林神犇

两道高斯消元：
[中山市选2009]树
bzoj2466
第一次写枚举自由元 发现原来的消元方法是很不适合枚举自由变元
因为消成对角线的话每个元之间的联系就变得不那么紧密了 自由元在整个矩阵中的位置的不定 给枚举自由元造成极大困难
所以我们选择消成上三角 上三角大法好啊。。 只有上三角部分是有数的 其他部分一律可以不管
按照原来出解的方式直接递归枚举就行了
[Hnoi2013]游走
bzoj3143
这个题再次让我感到了上三角的优越性
首先我们可以贪心的想 边权大的一定走的次数少 这样才能保证最优
然后转化成一般图游走问题 每个点的期望次数为 f[i]=Σf[j]*p[j] p[j]=1/d[j] d[j]为出度 稍稍变形扔进矩阵 消元
然后出来每条边的期望次数 a[i]=a[s]*1/d[s]+a[e]*1/d[e]
然后我TM死也A不掉了 调了大概半个小时。。。然后无耻的把题解扔下来对拍
然后。。。。然后发现了一些神奇的精度问题。。。。 然后开了long double 好像也不行。。。
果断选择用上三角 精度问题直接没了。。。。 因为上三角的运算次数少。。。
神TM上三角！！！！

还有一道假高斯消元：
[中山市选2010]生成树话说中山市好强啊
bzoj2467
题意太裸了吧 还告诉你是生成树计数问题 数据范围还只有100
我直接无脑上了matrix tree定理+模意义下高斯消元。。。然后无脑的T了
然后打个表A了。。。
正解是神递推。。。并没有看懂 把递推式粘下来又A了一遍

这里有道神数学：
[HAOI2008]圆上的整点
bzoj1041
这个我只想到了枚举r^2约数的做法。。。不过显然不行。。
然后我看了题解。。。【捂脸跑】
这么做:
原式可以变成：y^2=(r-x)(r+x)
设d=gcd(r-x,r+x) 谁TM知道要这么设
然后再搞个u,v r-x=d*u^2,r+x=d*v^2 显然gcd(u,v)=1
然后把r-x和r+x加起来。。 剩下2r=d(u^2+v^2)
然后你想到了什么 约数暴力即可。。。 枚举2r的约数再枚举u 计算v 判定即可

[Usaco2004 Mar]Lying Livestock 说谎的牲畜
bzoj3373
再次用bitset水过一个题。。。暴力枚举每一头牛 然后floyd判定。。。
2333这题好像没题解的。。【我也不知正解是啥】

[Zjoi2012]旅游(journey)
bzoj2657
又一道脑筋急转弯
我们可以把每个三角形看做一个点 和他相邻的三角形连边。。
这样连边是和原题描述的连边方式是等价的【不信你可以画图啊】
然后是个无向无环连通图。。【树】
求下树的直径即可

[Ahoi2009]Mincut 最小割
bzoj1797
这个可以记下来。。。
我们都知道二分图最大匹配的必须边和可行边 然而最小割的必须边和可行边呢？
以下所说的强联通分量是在残量网络上的
必须边：
若这条边满流 且这条边连接的两个顶点处在不同的强联通分量中 即为必须边
【很好想的 割了这条边一定可以把两个分量隔开 且满流 所以满足最小割】
【如果两个点在相同分量中 则割了这个边还能从别处走】
可行边：
若这条边满流 且这条边连接的两个顶点分别与S和T处在同一个强联通分量中 即为可行边
【去掉这条边也许S就到不了T了。。。】

教主的魔法
bzoj3343
第二次写分块。。好多细节又写挂了。。
首先没有修改直接离线树状数组就行了。。
有修改比较麻烦。。一开始想的splay 好像不行
好像cdq分治可以？并不会cdq分治。。
默默地想了想分块 恩 可以
每块块内排序 然后询问每个块二分 块外暴力
修改每个块直接加标记 块外暴力。。
然后码了半天== 累死。。分块还是不很好写。。