day1
(T1) https://www.cnblogs.com/zzqtxdy/p/12181226.html
(T2)
一堆(01)串，有一些挖了一个空。要求找到一个填数方案，使没有一个串是另一个的前缀。
trie优化2-sat建图即可
(T3) https://www.cnblogs.com/zzqtxdy/p/12181283.html
少打了一个小时。。。
(T2)第三次写还是花了一个多小时，数组开小爆了(30)，码力太菜。。。
(T1)只会个两个(log)的做法，还爆成(10pt)。。。
(T3)写了个压状态的(dp)，根据数据水的程度应该能过，但是来不及调。。。
排名居然还不低
这(T1)咋对拍啊。。。
day2
(LOJ6041)~(6143)。。。昨天好像也是雅礼集训(2017)的一场。。。
(6041) https://www.cnblogs.com/zzqtxdy/p/12184870.html
(6042) https://www.cnblogs.com/zzqtxdy/p/12185072.html
(6043) 只有大于等于(4)的时候需要枚举，搜一下就行了。场上非常(sb)地每次修改把环上所有点打标记，这样就多了个(n)，虽然不知道能怎么卡。
看题花了一个小时，(T1)第一眼会个(nsqrt{n}logn)和一个(nm+nsqrt{n})，想来想去也不会正解，(T2)大概会个(n^2)搞一搞，(T3)切了。
然后写完拍完(T3)花了将近一个小时，想(T1)想了半个小时无果就开始写。
结果剩下将近(2h)全用来写(nsqrt{n}logn)了，一看这一堆(stl)就觉得自己连(50000)都过不去。
(T3) (A)了，(T1)跟(n^2)同分，没碰(T2)。神仙(lxy) (AK)了，被吊打了。。。
(T2)场上(sb)了，想着把大的那棵子树跟小的平衡一下，就很难搞，实际上插到这个点上就行了。。。
没想到自己码力这么菜。。。应该先把暴力写了。。。
T2并不难想，就是场上(sb)+(T1)浪费时间，(T1)常数又大，码力还菜，早知道写(n^2)了。。。
day3
(T1)
一棵有根树，每条边有一个容量，给出(m)条路径，一个端点是另一个端点的祖先，价值为(w)。选出若干条路径，不超过边的容量，最大化价值和。
所有路径都是从下往上的，树上从上往下连边，选一条路径就是选一个环了，然后就可以发现是费用流了。。。
求解最小费用循环流的方法：负边((u,v,w,-f))拆成((S,u,w,0)) ((u,v,w,f)) ((v,T,w,0))，相当于先假装流满，如果不想流满就得通过中间那条边撤销。
(T2)
投骰子，每一面有一个朝上的概率，投(n)次，求点数和的期望和方差的期望。
卡精度实在是太毒瘤了。。。
直接(G-F^2)算方差会爆精度，把方差中减掉的那个期望(/n)后减到点数上，再算一次即可。
(T3)
数轴上(n)对鞋子，设(k)个鞋柜，每对鞋子必须放到同一个鞋柜里，求最小距离和。
神仙题。。。
首先每对鞋子都是选离中位数最近的柜子，把每对鞋子按中位数排序，一个柜子就会贡献到一个区间里，这样就可以很方便地(dp)了。
考虑如何快速求出（以排好序的鞋对编号为下标）一段区间内的鞋子的代价。
如果选好柜子那么代价就是所有鞋子到柜子的距离和，所以取中位数即可。
这个要用到所有鞋子的位置信息，查询不能拆开，但是信息满足可减性，所以用主席树维护即可。
然后后加进来的鞋对对中位数偏左的区间影响较大，满足决策单调性。
详细证明：
就是要证不存在(f_{j-1}+w(j,i)>f_j+w(j+1,i),f_{j-1}+w(j,i+1)>f_j+w(j+1,i+1))的(i,j)，(w(j,i))的意思是([j,i])的鞋子的代价。
化简一下就是只要证出对于任意(i,j) (w(j+1,i)+w(j,i+1)>w(j+1,i+1)+w(j,i))就得证了。
就是证第(i+1)对鞋子放在([j+1,i])比放在([j,i])优。
首先第(i+1)对鞋子的中点肯定大于等于([j+1,i+1])的中位数，否则右边的点数不超过一半。
所以往右边加鞋子中位数不左移，往左加不右移。
中位数是偶数个鞋子中中间靠左的数，两边是平衡的，往右加一个数最多右移到原来的下一个鞋子，不会改变原有鞋子的距离和；加完后([j,i+1])中位数比([j+1,i+1])左，跟新加鞋子的距离不会比较小，故加在([j+1,i+1])不会比([j,i+1])劣。
总结
场上看题后会(40+100+30)，写了(T2)和(T3)暴力和(T1)的(10)分，然后去想(T1)，期间感觉这题网络流不太能流的样子就没想网络流。
时间不多就写了(T1)的(20)，然后这个并不能套到链的(10)分上。。。然后就没时间了。
(T2)爆精度了，要用题解中的(trick)优化精度。。。
然后(T3)对拍了还爆成(10)分。。。
网络流可能还是差了一点，暴力写挂也是个问题。。。
day4
看题，(T1)是个数据结构题，想法不难，写出来可能有点复杂，(T2)是个毒瘤题，(T3)好像是个(sb)题
写完拍完(T1)花了(2h)，加上看题(3.5h)
然后兴冲冲写(T3)，写完过不了样例后发现是子序列，只好盲猜状态数不多写个类似麻将那题的做法。
写完后完全不知道(T2)怎么写，手玩了一组数据发现(T3) (WA)了，调到结束都没调出来（事后还经过了漫长的调试。。。）。
结果(T3)水过去了，足见(JZ)的数据之弱。。。
(T1)用的做法太毒瘤了，用前几场(ZR)那题的做法不就行了吗。。。
(T3)搞个前缀和就可以发现状态数最多(2^{10})，没看出来。。。
(T2)差点就想出正解了。。。当然我是不会场上去写的。。。
这场发挥得挺不错的，(T3)的性质没看出来，对结论题还是不太擅长。。。
(T1)
一棵树，支持：
1.路径上所有边反色。
2.对于路径上所有点，对其邻边反色。
3.询问路径黑边数量。
个人(sb)做法：
线段树维护区间两端点的颜色，区间(0)的个数，(1)的个数（整个翻转颜色的时候要交换），连着左右子区间的边的颜色。
整个翻转点颜色就改一下两个端点，整个翻转边颜色就交换一下答案，改一下中间边的颜色。
然后单独维护一下轻边即可。
线段树有很多地方不能套板子，还好这次码力不错。。。
正常的做法：
每个点记父亲的颜色，正常套路每个轻儿子标记挂到父亲，变成区间打标记
一些轻边重儿子什么的还是单独修改一下。
查询也就一些重点颜色链底标记什么的。
(T2)
长度为(n)的字符串划分成(k)段，每一段字典序最大值的最小值（表示成字符串）
(n,kleq 2000)
太毒瘤了。。。
答案一定是子串，搞出所有子串就可以二分了。
可以(O(n^2))或(O(n))求出每个点作为划分点，最远能到哪都不进行下一次划分（即字典序在这段区间内都不会过大，字典序很小的话就是(n)）
然后看看哪些点能作为划分点。首先能走的长度为(0)肯定不行，把它们扔掉（具体是能走到的分为包含了这个点的点能走长度--）然后如果一个点变成(0)了，那么既然它不能走到原序列上下一个长度(geq 0)的点，那它也不行了。如此这样一个个扔掉，直到剩下的长度都(geq 0)为止。
如果剩下的点数(<k)就凉了。这样，只要我们能构造出一种划分次数(leq k)的方案，就可以在每个划分点前面加些划分点构造出(=k)的方案了。
所以枚举出发点，一直往下走，维护再走一次能走到的范围即可。
环形这东西实在是太毒瘤了。
(T3)
给一个长度为(n)的字符串，求长度为(m)的字符串与其最长公共子序列为(1,...,n)的方案数。
(nleq 10,mleq 1000)，字符集为(4)。
考虑如何求最长公共子序列，就如果加了一个相同字符，等于一个前缀(max+1)，否则不变。
这样不太好看出来，改变一下(dp)数组的定义，变成到上一个点在第(i)位及以前的答案（及定义成存一个前缀(max)），每次用差分来转移。那任一时刻一个点的(dp)值不小于前面一个，最多比前一个多(1)，所以状态数不到(1024)，(dp)套(dp)或状压维护差分均可。
day5
看题后会(T1)暴力(T3)正解，(T2)不太可做的感觉。
(T3)的(MTT)竟花了我(2.5h)。。。
然后匆忙写完(T1)暴力就结束了。。。
两题都爆了第一个点，(T1)是因为太贪了想水分结果(kmp)写挂了，(T3)是因为暴力的取模位置错了。
考完后发现(T2)非常简单，只是我压根没去想。。。
对多项式之类的一些基础不够熟练。。。
(T2)这见过类似的题没反应过来，比赛的时候要每题都仔细思考一下。。。
本来能(200+)的，太可惜了。。。
T1
一个(n*n)的矩阵，每个点上有一个字符，随机选一个点往一个方向走(k)步得到一个字符串，求走两次得到相同字符串的期望，(nleq 500)。
只要把每个字符串求出来就可以塞进(map)中求答案，所以倍增求出每个点每个方向走(k)步的哈希值即可。
T2
(n*m)的网格上每一个点有一个方向，不会指向边界，染黑恰好(k)个格子，求一种染色方案使得第一列每个点出发，要么陷入循环走不到最后一列，要么第一次走到最后一列时经过且只经过一个黑点，(n*mleq 10^6,kleq 50)。
这种题当然是形成基环内向树森林然后搞一搞，走到环的点和没有第一列的点能到达的点可以随便染不染色。剩下的只有不会到达其它第一列的点的点能染色，这些点形成森林，相当于一棵树上用黑点覆盖所有叶子，黑点不能互为祖先关系的问题，直接(dp)即可。
T3
(n*n)网格的第一列和最后一列有数，然后每个格子等于上面(*b)，加上左边(*a)，再加上(c)，求((n,n))上的数。
MTT：
相当于每个格子的数往右(*a)，往下(*b)，移到右下方求和，(c)就一开始填在每个位置就好了。
拆开贡献主要就是要求
day6
(T1)感觉可以(dp)，写完才发现是(O(n^4))的，然后搞来搞去还是(O(n^4))，自闭了。。。
(T2)一看就不可做。
(T3)一开始没想出来，写完(T1)后打个表就会了，然后长剖都没调出来就结束了，只能写个链走了。早知道先写(n^2)暴力了。。。
不知道为什么这几天做题越来越慢。。。
(T3)爆成(5)分，结果是(OJ)没有开栈。。。
被(JZ)的队爷们吊起来打，才发现前几天都是在被人家学校的初中生吊打。。。深感自己的菜。。。