分类： ACM题解

发布于

[SAM][最长公共子串][循环串] hihocoder #1465 : 后缀自动机五·重复旋律8

题意要求所有的T中的循环串在S中出现了多少次，多次出现重复计数。

先考虑处理循环串，我们可以把循环串往后复制一遍变成定长单串，这时候如果我们可以把处理定长单串的方法搞出来就也能搞出来循环了。现在考虑的是对于一个串T，以T[i]为结尾的长为n的串出现了几次。很容易想到用endpos的大小去求，所以应该先把endpos大小求出来，之后就是应该确定是哪个endpos。可以先考虑如何求出对于T[i]来说与S的最长公共子串，这时候只要在SAM上顺着fa树走一直到走到原点或者有可以往后转移就可以了。如果走到了根节点还是没有能转移的，那就说明就没有这个字符，直接全0就可以了。注意这时候的长度可能过大，也就是stl超过了n，而在计算的时候应该是只需要“刚刚好包含长度为n”的那个状态节点的endpos。所以需要再顺着fa往前跳到fa的len小于n就可以了。然后这时候还有一个重复计算的问题，这是由于循环串可能有重复产生的，这时候我们就得给同样的条件打上标记了，而怎么判断是同样的呢？显然当串相同的时候一定会走到相同的节点上，只需要在最后的+环节打标记就可以了。

wa点主要出在指针和状态下标的转换上以及数组的长度上，注意循环串要复制一遍的话得是2倍长度。。。emmm

继续阅读“[SAM][最长公共子串][循环串] hihocoder #1465 : 后缀自动机五·重复旋律8”

发布于

[欧拉序][树上线段树][LCA] POJ 2763 Housewife Wind

https://cn.vjudge.net/problem/POJ-2763

欧拉序线段树裸题，每次要求出两点之间的距离，单点修改，区间查询。

欧拉序其实就是把树拍扁的一种方法。。。对给定的树先求出欧拉序，在欧拉序上通过权值的正负来抵消多余的往返操作，然后每次求得时候先求LCA，再求出lca到两个端点的距离相加即可。有了欧拉序LCA就是一个rmq问题，用线段树做就能实现动态求lca，然后端点距离可以用BIT或者仍然用线段树做，求和最后输出即为答案。

实现的主要注意点是下标之间的关系。。。。这其中欧拉序求出来的点个数是2*n-1，然后BIT上存储的又是2n-2个间隔，然后BIT差分又得考虑左端点往前移动一下。。

继续阅读“[欧拉序][树上线段树][LCA] POJ 2763 Housewife Wind”

发布于

[思维][meet in the middle] codeforces 1023 E

其实也不是正常意义上的meet in the middle了，只是这个处理的思想有点像。（似乎每次做交互题都会卡？

自己做的时候是理解错题目意思了，以为图上只要联通的点都能返回YES，但是其实是按照他的限制下走的时候能走到才能返回YES。这样的话需要考虑的问题就比较好处理了。。。。一开始理解的那种的话根本没法在4*n次询问的限制下做出来。

因为右下半矩阵的路线只能通过询问（1，1）到该点的可行性来获得，左上半矩阵的路线只能通过询问（n,n）到该点的可行性获得，要想获得完整的可行路线只能在交界重合的地方处理，也就是反对角线上的方块。为了使得两个方向的推法能够走到同样的对角线点上，可以采取极端策略，左边的就尽量往下走，右边的尽量往左走，这样两种操作到最后的结果都是相同的，会走到对角线上的极端点（最左下的可行点），这时候就保证了两条路能够接上。 继续阅读“[思维][meet in the middle] codeforces 1023 E”

发布于

[二分图][棋盘][连通分量] codeforces Chemical table 1013D

http://codeforces.com/contest/1013/problem/D

题意：每次可以从矩形的3个角产生第4个角，问至少需要添加多少个方块可以使得让整张图都充满方块。

自己想的是奇怪的思路，因为发现一个联通的块可以扩展到这个块的maxx，maxy，但是之后就不知道怎么做了。看了题解才恍然大悟，原来是把坐标转化成二分图的左右节点，然后考虑连通分量的个数就可以了。证明的时候，首先注意到一点就是二分图中两个点之间的路径个数一定是奇数，对于同一个连通分量中的左右两个点x，y，他们之间的距离如果是1的话那说明二者之间一定有了一条路径了，也就是这个点已经有一个方块了，如果不是1那么至少是3，每次取距离y最近的3个点，按照题目中给的性质，就可以生成一条新的边，也就是从倒数第四个直接联到y，这样的话，每次边的数量都会-2，到最后一定能减少到1，回到之前的情况。所以在同一个连通分量里的左右所有的点一定能连到一起，也就是说所有的方块一定能被涂上。这时候等于说连通分量和能全部染色等价了，我们就只需要计算出来最少需要多少条边使整个图成为连通图就行了。。其实也就是 连通分量数-1

wa点的话因为把n+m写成了2*n错了还以为横纵坐标是一样大的。。。愚蠢的错误emmmm

继续阅读“[二分图][棋盘][连通分量] codeforces Chemical table 1013D”

发布于

[线段树][字符串hash][假算法] bzoj2124 等差子序列

这个题在codeforces上有几乎一模一样的：http://codeforces.com/contest/452/problem/F

cf上的题说的是考虑长度为3的等差序列，bzoj这个说的是等差序列其实也是找长度为3的，因为显然能找到长度大于3的肯定也能找到等于3的。cf那个题有个假算法可以过掉所有数据，就是暴力枚举中点，然后往左右延伸的时候不超过5个就行。。之所以能这么做是因为这个题目要想构造出来NO的数据确实很难。。不过假算法依然是假算法。。

正解是每次出现过一个点之后把他在线段树上值变为1，然后求一个中点左右两边有没有相同的时候需要判断左右两边是不是完全一样，如果不是一定有解。这里判断的方法是hash。。。分别在两个线段树上维护正反两个方向的左右01字符串的hash值就可以了。
wa点：首先是对于这种多项式形式的线段树合并的时候要分三种情况，完全在左/完全在右/跨越中点；其次是跨越中间点的情况下一定要考虑清楚应该累加的数值是多少。。在这里是pw[mid-max(ql,l)]；最后是当ai==1和ai==n时候的特判，这时候不能query，但是必须update，我一开始写了单独处理1，然后i从2开始循环，后来忽然意识到a1并不一定等于1啊。。。傻了。。。

继续阅读“[线段树][字符串hash][假算法] bzoj2124 等差子序列”

发布于

[换轴][并查集][异或性质][连通分量] codeforces 1040E Network Safety

http://codeforces.com/contest/1040/problem/E

这个做法最重要的是原本的每一条边两端点一定不相等，所以两个点如果同时被异或结果一定仍然不相等。     然后就是考虑一个点被异或另一个点没有被异或的情况，一开始觉得会很复杂？但是实际上不是这样的，远没有想象中的复杂：  当x确定的时候，只有a⊕b==x的那些边会受到影响，这些边必须同时被选中，而剩下的，无所谓。。所以就把这些边连起来的点缩点之后就成了2^q的选择方式了。。

实现细节：①会卡并查集退化，所以必须写按秩合并   ②每次只要记录下被改动的点，然后下一次把这些点并查集复原即可，否则由于并查集的初始化时间复杂度会退化。

继续阅读“[换轴][并查集][异或性质][连通分量] codeforces 1040E Network Safety”

发布于

[比赛][TreeDP][树的性质][换轴][统计技巧] codeforces 1060E Sergey and Subway

自己思路的问题：每次用一个中转节点多连一条线就是等于跳过了一个节点，想到了偶数就是/2，奇数是+1/2，但是没有想到怎么去统计实现。

这个问题最后的答案可以表示为（S+O)/2，其中S是所有点对之间的路径长度之和，O是路径长度为奇数的路径的数量。然后就是如何计算这两个数字的问题。

我以前的理解是求S得用两遍dfs的treeDP，然而这次学到了新操作就是可以分别考察每一条边他被多少对点之间的路径包含了，只需要求出有根树每个点对应的子树中的节点个数即可，S+=(n-subts[x])*subs[x]。

求O的方法就更妙了，画出来一颗有根树就可以发现，两个节点之间的距离奇偶性可以用他们到根节点的奇偶性来表示！（因为树形结构本身对于根节点来说有某种意义上的差分性质emmm），假如两个点到root的路径长度（也就是depth）奇偶性相同，那么他们之间的路径就是偶数的否则是奇的。所以只需要求出来所有的奇数层的节点个数乘以所有的偶数层的节点个数就可以得到O了。

继续阅读“[比赛][TreeDP][树的性质][换轴][统计技巧] codeforces 1060E Sergey and Subway”

发布于

[比赛][贪心][STL] codeforces1060D Social Circles

比赛结束智商上线系列

昨天的时候看C没整明白然后来看D，没想出来构造方法又回去卡C结果最后都没出呵呵呵，今早起来写了几个样例，组合了下就发现了规律：每次找到left最大的那个人和right最大的那个人，如果不是同一个人就合并中间left和right重合部分，ans加上这一部分（ans+=max(maxleft,maxright)）然后把这俩人重合的部分消去合并成一个新人放回集合里；如果是同一个人那就自己一个人一个圈子就好了。

感性理解的话就是要尽可能的让长的段之间有重复，重复就可以节省椅子，而始终都找最长的left和right就能保证这一要求。

wa点：multiset中如果两个元素它们定义<运算符的那个信息相同他就认为是相同的，而erase的时候会把所有相同的都erase掉，所以为了区别不同的人加上了一个id。。。很神奇吧。。

继续阅读“[比赛][贪心][STL] codeforces1060D Social Circles”

发布于

[比赛][CF][预处理][问题本身的性质] codeforces 1060C Maximum Subrectangle

这场有点惨的过分了，怎么说呢。。。经过了这一段的训练感觉该提高一些了但是却还是这样子。。。继续努力吧

这个题卡了是最最难受的，因为从矩阵的角度考虑不管怎么样都搞不出来一个O(n3)的算法，无论如何都不可能，然 而 ，然 而！这题目根本就不用考虑矩阵。。。因为每一行每一列都是成比例的啊。。。光给个矩阵怎么可能n²算出来答案？很明显是跟题目数据自身的性质有关系的，然后自己就傻脸看了俩小时不知道怎么操作，呵呵，出发点就不对怎么可能算出来。。。

因为每一行都是成比例的，比例是bi，所以要求一个最大的不超过x的子矩阵，只需要枚举上下边然后给预处理出来的sb数组乘个上下边之差就可以了，小于x的操作可以用sb[x/(pa[j]-pa[i-1])]来操作。。。。。。所有的处理都极其暴力，但是因为所有的处理都是在a或者b的一维序列上进行的，所以暴力也是n²，如果脑子里只有那个矩阵的话怎么都不可能n²，因为他是个二维的。。
写错的地方的话是x可能会比pb[m]大，这时候只需要取到这个最大值就可以了。

继续阅读“[比赛][CF][预处理][问题本身的性质] codeforces 1060C Maximum Subrectangle”

发布于

[图论][欧拉路径][特判] codeforces 1038E Maximum Matching

http://codeforces.com/contest/1038/problem/E

“这题有点难受”系列。之所以能这么O(n)做完全是有且仅有4个点，玄学。

其实也不是很难受，主要是最后一组测试(test 117)让我意识到原来的处理方法对于那种特殊情况都不适用，然后感觉在这时候只能用n²算法才能解决。。。想了很久反正是，最后终于发现当（奇点数==4&&删去最小边会使得4个点不联通）这种情况只有两种，一种是三个点连成环然后剩下一个挂在外面，另一种是1到2和3到4有1条边，而2到3有两条，所以只要把这两种情况特殊判断一下就还是O(n)的算法了。。

正经地说：把1234看成4个点，n个block相当于边，题目意思就是找出一条最长的路使得每条路都只能走一次，无向图只能走一次，很显然的欧拉路径的操作。但是要分很多情况讨论。

首先分连通分量有几个的时候，当有2，3，4个的时候就是找到这几个连通分量中的最大值，因为这时候每个联通分量都一定是有欧拉路径的，3的时候可能比较难证明，但是可以通过4个点组成的图奇点只有024三种可能推出来。

然后当只有一个连通分量也就是四个点都联通的时候，讨论奇点数量，前面已经说过奇点数量只可能是024，当是02的时候直接全选因为一定有欧拉路径，当是4的时候再分类讨论：找权值最小的那条边，看他是不是去掉后会使得多出来一个连通分量，说是多出来一个联通分量其实只有可能是多出来一个孤立的点，因为其他情况都与（4个点都是奇点）这个条件相矛盾，所以删除这条边如果能使得原图不连通那么一定是分成了一个3个点一个1个点，这里面又有两种具体的情况，也就是之前说的，一种只有一个桥另一种有两个桥，如果不是这两种情况那么直接取全部的边然后删除掉最小权值边，如果是这两种情况则单独特判即可。。需要注意的是这两种情况需要循环一遍所有的边来确定最大值，因为删除的可能是其他的边也可能是桥。

继续阅读“[图论][欧拉路径][特判] codeforces 1038E Maximum Matching”