作者： itewqq

发布于

[SAM][拓扑排序][计算endpos大小] hihocoder 1449 : 后缀自动机三·重复旋律6

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里的连续的一段，所以这些点其实和那个右端点的大小其实是一样的，刷过去肯定是对的。

继续阅读“[SAM][拓扑排序][计算endpos大小] hihocoder 1449 : 后缀自动机三·重复旋律6”

发布于

[学习] 线性筛+预处理+遍历/分解质因子

写这个是还是从今天那个C题目来的。看正解的时候发现了他用了一个很神奇的遍历质因子的方法，没有多余的操作，就是完全的遍历每一个质因子，只不过需要预先用线性筛处理出来1到n的每一个数字的最小质因子。感觉适用于需要分解多个数字质因子的情况但是我自己写的暴力sqrt(n)貌似也不慢多少就很迷。。。emmmmmm不管了先记下来再说。

继续阅读“[学习] 线性筛+预处理+遍历/分解质因子”

发布于

[数学][质因数分解][预处理优化] codeforces 1034A Enlarge GCD

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飘过。。。

继续阅读“[数学][质因数分解][预处理优化] codeforces 1034A Enlarge GCD”

发布于

[BIT][思维][反证][差分求极值] codeforces1030F Putting Boxes Together

题目：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”

发布于

[暴力][分块][思维] CF 1030E Vasya and Good Sequences

题意如果一个序列中[l,r]里面的数，可以通过调整每个数的二进制位使得其异或和为0，那么这个[l,r]对就是good的，然后求有多少个这种[l,r]对，序列长度3e5。

一开始想dp，又是分位又是奇偶的，始终没搞出来。看了官方题解才发现判定一个[l,r]段是否为goog的充分必要条件只有两个，首先设bi为ai的二进制表示中的1的个数，则充要条件为：

① Σbi(l<=i<=r) 为偶数

② max(bi)<=Σbi(i!=index(max(bi)) 继续阅读“[暴力][分块][思维] CF 1030E Vasya and Good Sequences”

发布于

[几何][数学][思维] CF 1030D Vasya and Triangle

题意：给定n,m,k,要求在横坐标小于n纵坐标小于m的整点中找到一个三角形使得三角形面积为 n*m/k。一开始一直纠结于存在性。首先可以证明如果2*n*m%k!=0那么一定是NO。当满足这一条件的时候，可以把n*m/k上下拆分，把k拆成gcd(n,k)*(k/gcd(n,k))，然后上下约分就可得到一组ab，这时候如果后者和m不能完全约分说明分母里会剩下一个2（因为分子上*2是可以完全约分的），这时候ab就是答案的两条边因为不需要除2了。如果能完全约分则还需要在分子的a或者b上乘一个2，哪个小乘哪个就好了。为什么乘2不会超过原来的n或者m？因为我们这时候一定是n*m%k==0，而且题中k>=2，所以n和m至少有一个可以除一个2。
感觉做的时候问题主要在于无法验证正确性，但是后来发现k>=2这个条件是极其重要的。。。。没有这个条件就可能无解了 继续阅读“[几何][数学][思维] CF 1030D Vasya and Triangle”

发布于

[比赛][暴力][循环][复杂度分析] 2018 icpc 青岛网络赛 J Press the Button

还好没有鸽这场比赛，当时是做数模的最后几小时，我和lyq没办法只能让iSika单挑，期间顶着40小时没休息的脑袋帮他过了一个水题和一个计数递推形的dp，然后看看J过的人挺多，准备去看却发现脑子实在太疼根本读不完题，然后iSika说他大概能过那个B，然后我就不管了去瞎编数模论文。。。

没想到的是晚上肝完数模去打印论文的时候，掏出手机发现代哥给我发消息问去沈阳赛区不去。。当时其实本来已经累得要死了但是看到这个瞬间高潮了，简直哭了，真的好不容易得到的icpc现场赛机会。。。

然后我在队里小群兴高采烈地发消息结果半天没人回我，嗯友尽系列（都在睡觉吗朋友们？？

然后后来一直在忙微软俱乐部的面试，到现在在高铁上才有空去看这几场区域赛攒的题，先把这个J补了，当时以为复杂度不可取，实际上就是一lcm循环，而lcm里a或c的倍数的数量最多1e6，所以不会超时。需要分成三段处理，第一段是[0,lcm)，第二段是[lcm,k*lcm)，第三段是[k*lcm,t]，其中第二段的计算只需要算(k-1)*[lcm,2*lcm)就可以了，也就是说三段复杂度都是1e6。当然有几段还得根据t与lcm的相对大小来具体判断。之所以第一段和中间循环段分别考虑，就是因为一开始的条件是灯都是灭的，但是在第一个lcm循环结束之后灯光却有可能是亮的，所以需要特别考虑这种情况。最后把三段的答案加起来就得到了最后的答案。

继续阅读“[比赛][暴力][循环][复杂度分析] 2018 icpc 青岛网络赛 J Press the Button”

发布于

[比赛][二分][计算集合][定长圆最大点覆盖] 2018 ICPC 沈阳网络赛 E The cake is a lie

比赛的时候一看计算几何直接跳过了，其实不是不可以做。。。

这个里面，各个草莓的半径其实对计算影响不大，由于圆的对称性，只要求出能覆盖s个草莓的圆心的最小圆就可以了，输出答案时加上草莓的半径r即可。

然后求定长圆的最大点覆盖就是有点模板了，有两种算法，n^3和n^2logn的，但是既然是抄板子那肯定是抄最快的了。。。

继续阅读“[比赛][二分][计算集合][定长圆最大点覆盖] 2018 ICPC 沈阳网络赛 E The cake is a lie”

发布于

[二分图][建图] UVa 12168 Cat vs Dog

比赛时候其实想的就是正解，但是没时间实现了。

这里并不是把猫狗分离开来，而是把voter分离开，换句话说原来的边变成了点，支持猫的在一边，支持狗的在另一边，如果有冲突的话连一条边，这样的话就是求最大独立集了。

本来看这个输入感觉头疼，后来想了想，忽然意识到：1 重复的人可以不用管，照例读入建立点，因为把他变成点之后对图没有任何影响。2  可以不用管字符后的数字，直接把他们当成一个整体就好了，整个字符串比较。 3  建立图的时候可以不用分左右两边，只要i和j有冲突就line[i][j]=line[j][i]=1；这样会使得建图的过程更简单，然后相当于把二分图对称了一下，最后输出的时候最大匹配数除以2就可以了.

继续阅读“[二分图][建图] UVa 12168 Cat vs Dog”