8月浪了一个月，滚回了普及组水平（从来都是这水平）。

新学期开始了，班主任要求好好上课做作业，野花经常性煽动不做作业不听课……T_T

求每天有点输出……

[Upd 10.1] 9月结束了，居然只做了这么点题……实在是浪……

Counter:30

9.29~9.30:

CC:XRQRS:在后面加数删数，求区间k大、区间与x最大异或。函数式Trie、函数式线段树。

CC:SEAARC:n个点，相同颜色之间连弧，问不同色弧相交了多少次。花式问题转化，花式前缀和。

9.23~9.28:

怎么突然过了这么多天……意识模糊。

CC:RIN:每门课要选一个时间上，课程之间有拓扑关系，每门课每个时间有个价值，要价值最大。最小割。

CC:CHEFBOOK:一个矩阵，可以把每行所有非空的数+Pi，每列非空的数-Qi。要求后来每个非空格子的权值都在Sij~Tij的范围内。并且要所有权值和最大。有点神奇巧妙的线性规划。

BZOJ:4245:[ONTAK2015] OR-XOR:把一个序列分成m段，使每段xor的or值最小。作出前缀异或和然后从高位往低位贪心。一位是0的条件是包括An在内有m个数这位是0.然后把不能选的数去掉就行了。

BZOJ:1061:[NOI2008] 志愿者招募:每个变量只在两个限制中出现且系数是正负1的线性规划问题，加上Δ差分后费用流跑一下就行了。队列开小调了一下午。excited。

BZOJ:4260:Codechef REBXOR:n个数，选两段不相交区间xor之和最大。从前从后各做一遍Trie就行了。

BZOJ:4151:[AMPPZ2014] The Cave:一棵树，找到一个点x，满足所有形如Dis(x,Ai)+Dis(x,Bi)<=Di的限制。有点厉害的题。假设1号点满足条件就输出1号点，否则不满足了一个限制肯定要往它们LCA的方向爬到深度>=a为止。所有的限制要取个交集。那么直接找到限制深度最大的那条限制的最浅点，检查是否满足所有限制就行了。

BZOJ:4149:[AMPPZ2014] Global Warming:要求一个最长的区间使得它最大值唯一，最小值也唯一。维护出每个点为最小最大值的区间，枚举每个点作为最小值，线段树查找点在左边，最大值尽量靠右或点在右边最大值尽量靠左。

9.20~9.22:

CC:FNCS:有一个数列，有一些函数是求区间和的。要支持数列中单点修改，查询一段连续的函数的和。比较无脑的分块。块内标记，块外暴力。块开成 \( \sqrt{ \frac{n}{log n} } \) 最合适但是空间有点不够。好在不卡常数。WA1个点是因为要开unsigned long long。

CC:DISTNUM:感人肺腑。在哲大爷的教导下爆过了这道题……插入、删除、修改，查询区间内不同的数的0、1、2、3次方和。用Splay维护出最终的序列，然后每个点记一下前驱，查询的时候树套树就行了。轻松写上6k+，还卡了半天的常数。要把外层的线段树换成BIT，查询不经过的BIT结点就不要修改……从昨天中午开始搞到今天中午……

9.17~9.18:

16号整天无自修课，中午做初赛，晚上做作业到半夜T_T……17~18主要在打Gym。

CF Gym:[ASC34] H:Peaks:省选讲课题。我看了一中午的题解没看懂暴力，问灿爷才明白……求n个数的排列，“峰”的个数为k的方案数，%239。f[i][j]=f[i-1][j]*2j+f[i-1][j-1]*(i-2(j-1))。其实就是考虑最大的那个放在哪里。放在原先的峰旁边峰数不变，否则+1。然后n很大k很小，可以矩乘，转移矩阵和i有关，由于模数小，就可以搞出239个转移矩阵，合起来转移，剩下的再暴力乘上去就行了。

[某3星Gym] ABDFGKL。。

BZOJ:3551:[ONTAK2010] Peaks加强版:学了Kruskal重构树，就是做Kruskal的时候把边新建成点连边过去。这样有几个比较好的性质:是个大根堆;点数是O(n);原图中两点路径上最大边权就是新图中两点LCA的权值。那么询问就是倍增下祖先，查询子树K小。

9.15:

BZOJ:1206:[HNOI2005] 虚拟内存:用堆维护一下，取最小值的时候更新Lazy直到Lazy为空。

BZOJ:1224:[HNOI2002] 彩票:不要想太多太复杂的剪枝，用小数表示加上上下界剪枝就行了。一开始整数表示分母大力gcd结果T了……

9.14:

英语单元考失意地滚粗了。只能靠刷点水寻找慰藉了。求每天过题量英姿。

BZOJ:1014:[JSOI2008] 火星人:Splay维护Hash值，二分+Hash。

BZOJ:1294:[SCOI2009] 围豆豆:射线法判点在多边形内。经过横向直线不算，上闭下开就能搞好边界了。BFS之。

BZOJ:1217:[HNOI2003] 消防局的设立:f[x][i]表示x的子树最近的消防局距离为i。i≤5.DP。

BZOJ:1299:[LLH邀请赛] 巧克力棒:先手取出一个Nim游戏的必败态，即极多的数异或起来=0.后手不管怎么搞都是一个Nim必胜态。

刷的题实在太水有点不好意思……

9.9~9.12:

BZOJ:3589:动态树:子树加,求5条链的并的和，容斥下，考虑维护每个点到根的和。两个BIT维护下就行了。

BZOJ:3276:磁力:把点按照距离排序，线段树维护重量最小值就行了。

CF:145C:对于非Lucky number直接算，Lucky number暴力背包即可。

CF:356E:大大大大大大大暴力。暴力枚举每个点修改成什么，减去原先的贡献，然后去暴力DFS加上新的贡献就行了。约束有点多所以效率还不错。考虑一个Lucky string，假如当前修改的字符可以影响到它，一定是修改的字符为中心的一个Lucky string是其子串。往两边不停拓展就行啦。代码实现挺有技巧性的。做完这种题总感觉“写出标程的人和出题人是一伙的”。

Before 9.8:

BZOJ:1533:[POI2005] Lot-A Journey to Mars:A的前缀和的每个值都不小于B的前缀和对应值即可，CF上有类似的题，当时我好像是线段树维护A-B的最小值什么的，其实单调队列就行了。

BZOJ:1113:[POI2008] 海报:单调栈。两边低中间高答案就能-1.

BZOJ:2648:SJY摆棋子/2716:[Violet 3] 天使玩偶/3053:The Closest M Points:KD-Tree模板

BZOJ:2762:[JLOI2011] 不等式组:BIT。边界搞搞。