https://hihocoder.com/problemset/problem/1457
要求求出来n个串中所有子串的十进制和。
考虑单个串的情况：顺着sam的边走的话，一个点的所有字串等于它所有的父节点的字串+c，c为从父节点转移来的路径字符，由十进制的性质可以知道当前节点（设为st）的和为则求出sam状态转移图的拓扑序然后刷sum即可；
多个串的情况：考虑把多个串合并为1个串，每两个串之间以‘9’+1填充（也就是: )，然后建立sam。此时要求出sam每个状态中有多少个不含：字符的子串，这里用到了一个性质就是，这个值恰好就是从初始状态S到状态st的所有”不经过冒号转移的边”的路径数目，而有向无环图上的路径数目也是一个经典的拓扑排序问题！
由此只需求拓扑序的过程中把有效子串个数求出来就行了。
wa点的话，注意第一次调用sam前要用init函数初始化。另外，拓扑排序无需纠结数据结构条件是指向父节点还是从父节点指向子节点。
继续阅读“[SAM][多串][不同子串十进制求和][拓扑排序] hihocoder #1457 : 后缀自动机四·重复旋律7”
http://newoj.acmclub.cn/problems/2057
看的时候没有什么思路，想过dp但是感觉数据量不可行，看了题解才意识到离散化即可O(n^2)，暴力刷表推出来每个点的最优值即可。
此外，还学习到了v[i][j]=v[i][j-1]+v[i-1][j]-v[i-1][j-1]+mp[make_pair(x[i],y[j])];这种处理方法，如果没有想到-v[i-1][j-1]的话，就不会想到推出来vij也就没有后面的操作了。此外，在二维平面上这种只有两个轴向转移的思想也是很重要。确定了dp的一个转移的方向。最后，确定答案的一步也很有趣，由于离散化导致的不能确定m天的位置，所以只能再遍历所有的点然后取小于等于m天的那些点向m天转移的最大值。
wa点的话离散化忘记去重。。。。很尴尬的操作
http://newoj.acmclub.cn/problems/2054
题目给了一个方块板子，每次要么给同一列所有数字加上同一个数，要么给同一行加上全一个数，然后现在给出经过若干次这种操作之后的一个局面但是把其中一个点换成了-1，要求出来这个点的值应该是多少。
一开始没什么思路，后来写了写表达式似乎发现了可以直接解出来。设ri是第i行加的总数字，ci是第i列加的总数字，row是现在的-1所在的一行的和，col是-1所在的一列的和，若-1坐标为x，y，则可以设要求的数字为t=rx+cy，这时候可以列出来两个方程：
① row+col+2t+21==nt+Σri+Σci
② n*(Σri+Σci)==t+1+Σboard[i][j]
其中第一个方程是要求的那一点的行和列的和的两种表达式，第二个方程式整个board上的所有的点的和的两种表达形式。如果把(Σri+Σci)看作一个整体消掉，可以直接求出来t的表达式t=(n*(row+col)+2*n-Σboard[i][j]-1)/(n-1)^2
http://codeforces.com/contest/1041/problem/E
比赛完5min想到了ac做法emmmm
并没有看懂官方题解，NO的判别其实很简单，只要有b不是n的情况就NO，因为不管怎么分都一定会有一个n。YES的情况怎么构造？我自己的做法是把n作为根节点，把条件排序后从小到大考虑：如果一个点出现了一次，那么就连一条从根节点到这个点的边，并且把这个点标记为用过的；如果出现了多次，那么就到前面找没有标记过的点找一个最小的插到当前点和他的父节点之间，并且把找到的点也标记为用过的。
所以为什么是正确的？首先按照a排序后可以发现如果一个数字重复出现了那么一定是从第ai个往前重复，如1 3 3 4，这个重复的3一定是从第3个往前延申，按照我的构造方法，如果不是这样那就不可能满足要求，因为3和5之间的路上的节点一定是全是小于3的数字，而且以3为根的子树我这里直接让他为空。这样的话总可以在前面找到足够数量的数字来插入到3的这一条链上（忽然感觉说不清楚了但是这么构造一定是对的emmmmm
wa的话感觉可能是当时很饿然后树上的插入操作和标记都写错n次，神奇的是每次都能通过前30个test然后被3x刷掉。。
题目链接：http://newoj.acmclub.cn/problems/2053
只要能想到用最小费用最大流去做，建图还是相对好想的：左边n个点表示n根蜡烛，右边n*m个点（或者m个点但是每个点有n条边连汇点，二者是等价的），然后源点连左边n个点之间cost为0容量为1，表示每个蜡烛最多被用一次，然后从左边到右边i到ai所有的n个分点连容量为1 cost为2*k-1的边，最后右边每个点跟汇点连容量为1 cost为0的边，最后跑最小费用最大流即可。
平方费用处理的话也不难毕竟看过lrj书上的处理平方费用的方法。。。这种平方费用的话可以拆点也可以拆边，但是思路都是新弄出来的边cost都是当流量从i到i+1的时候的增量，也就是i^2-(i-1)^2，因为这个差值是随着i增大而增大的，所以最大流增加的时候一定是从小到大选择这些边的，而这些边的cost从小到大依次选择就可以累加出来x^2，也就是与原来的要求等效了。
继续阅读“[最小费用流][平方费用][拆点/边建图] 2018camp Birthday”
http://codeforces.com/contest/1042/problem/D
嗯，大概是发现了自己以前一直没有正确理解mergesort。。。。
vp时候发现一开始这个题目过的人竟然比C多然后就提前去看了，但是竟然并没想出来正解emmmmmm，想过分治但是不知道怎么在线性合并左右段，看了前排dalao代码恍然大悟，其实就是逆序数的推广，这里把前缀和当成要处理的对象即可，如果是逆序数的话就是输出来一个数字右边有多少个比他大的，这里的话是sum[i]的右边有多少个比sum[i]+t小的，而t是常数所以其实几乎和逆序数一样。。如果仔细考虑逆序数的分治算法的话，会发现他能保证合并的时候线性是因为每次左右两边都是排好序的，这样的话就可以线性合并，而为什么排序这个操作不会影响到结果呢？因为在合并的时候左右两边各自的结果已经被计算过了，需要计算的仅仅是跨越中点的那些lr对！而这些计算和左右两边各自的顺序没有关系，只要保证左边的在左边右边的在右边就行了：因为我们是计算合法的数量，只要存在就+1，跟他什么时候存在早存在晚存在没关系。 继续阅读“[分治][mergesort][经典算法推广][实现] Codeforces Round #510 div2 D Petya and Array”
http://hihocoder.com/problemset/problem/1449
需要在O(n)时间内求出所有长度为k的字串中出现次数最多的字串的出现次数。这里的话首先肯定是要求出来endpos的大小了，球的方法是利用fa树上的不同的st之间的包含关系和子树之间的交集为空的性质。这样的话要想求出来某个点的endpos大小只需要知道它的子节点的endpos大小就行了，另外还有一种需要特判的情况就是当st包含S的前缀的时候需要再额外+1，因为这个前缀是后面的节点没有包含到的。
推的过程的话，首先求出来拓扑序，然后从后往前刷fa节点的cnt即可。但是如果就这样的话，要用朴素的算法求出来每个substring的长度还是需要n²的复杂度，仍然会卡住。然后这里有一个性质那就是长度短的substring中的最大值一定不会比长度长的小，然后我们只需要更新每个节点对应的maxlen的最大值就可以了，然后从后往前更新最大值。为什么这么做是对的？首先每个st里最大值那个点肯定是对的，然后每两个更新点之间的那一段一定是被某个右端点包含在内的一个st里的连续的一段，所以这些点其实和那个右端点的大小其实是一样的，刷过去肯定是对的。
写这个是还是从今天那个C题目来的。看正解的时候发现了他用了一个很神奇的遍历质因子的方法，没有多余的操作，就是完全的遍历每一个质因子，只不过需要预先用线性筛处理出来1到n的每一个数字的最小质因子。感觉适用于需要分解多个数字质因子的情况但是我自己写的暴力sqrt(n)貌似也不慢多少就很迷。。。emmmmmm不管了先记下来再说。
http://codeforces.com/problemset/problem/1034/A
题意问给定n个数，从中最少去掉多少个数之后可以使得剩下的数字的gcd严格大于原序列的gcd。
思路：先求出来原序列的gcd，无解的情况很容易判断，当序列中最大的数字就是gcd的时候无解。对于有解的情况，把每个数字除以这个gcd，剩下的一个序列就是gcd为1的序列，然后只要求出来去掉多少个数字之后可以使得序列gcd不为1就行了。这时候考虑去掉k个数字之后剩下的数字gcd为几，不妨设为w，很容易知道如果能求出来对于每个质数有多少个数字有这个质因子，那么取“在序列中出现最多次数的那个质数”的出现次数就是最大的剩下的序列中的元素个数，这里的出现次数是说如果ai%w==0则cnt++的意思。那么能求出来剩下的元素最多有多少个，也就能求出来去除的元素最少有多少个了。
比赛时候这个题是把我T爆了，主要是很难确定对于每个数暴力质因数分解好还是线性筛预处理出来1.5e7之内的素数比较好，一开始一直用的暴力质因数分解但是test23一直t，最后6min换了预处理素数ac了，其实手推渐进复杂度感觉二者差不多。。。。玄学卡常，而且最后过了也是800ms飘过。。。
题目：http://codeforces.com/problemset/problem/1030/F
这个题最主要的是自己没有想出来怎么求出那个“不动的点”，因为其实整体的cost用k去表示出来是很困难的，求出来也无法发现其极值点。但是如果考虑差分就会比较好做，很容易发现当当前设的k点变成k+1时，cost变化了(S(l,k)-S(k+1,r))*(p[k+1]-p[k])，其中S(l,r)=Σw[i](l<=i<=r)。这样的话很明显当且仅当S(l,k)≤S(k+1,r)S(l,k)≤S(k+1,r)时k+1比k更优。所以我们只要找到最小的k使得S(l,k)>=S(l,r)/2就行了！
然后是对于一个[l,r]对求出k之后，如何快速的求出其cost。
对于i∈(l,k)i∈(l,k) 代价是∑(pk−pi−(k−i))∗wi（l<=i<=k)
对于i∈(k,r)i∈(k,r) 代价是∑(pi−pl−(i−k))∗wi（k<=i<=r)
把pi-i看成一个整体，记为ai，就可以得到cost=∑(ak−ai)∗wi(l<=i<=k)+∑(ai−al)∗wi(k<=i<=r)
展开整理就可以得到cost=ak*(S(l,k)-S(k,r))-(Σwi*ai(l<=i<=k)-Σwi*ai(k<=i<=r))。这样的话用一个BIT快速求S(l,r)，另一个BIT快速求Σwi*ai就可以了。
wa点的话，发现了一个以前没有注意到的bug，那就是我每次判断都是if(x>mod)x%=mod;但是忽然意识到在有减法的运算中，还有一种下越界的可能性，所以应该是if(x>mod||x<-mod)x%=mod; 继续阅读“[BIT][思维][反证][差分求极值] codeforces1030F Putting Boxes Together”
