algorithm

树状数组小结

  退役好久了,惭愧的是一直没搞过树状数组和线段树,以前都是队友搞的,最近刷codeforeces被树状数组卡了好几次,遂决定怒刷树状数组。 0.算法   本来想写写长篇的算法过程,从如何建树到如何维护更新,结果发现这篇博客写的很赞了,我也就不写了,就写写个人对算法的理解以及刷的题目吧。   树状数组的优点就在于维护了一个前序和树,算法的核心就是『前序和』,碰到的各种题目也都是将各种模型转换为前序和,然后再进行查找和插入操作。   其时间复杂度如下:查找和插入/更新都是O(log MaxVal),其中MaxVal表示树的最大下标,非常适合插入频繁的操作。以下read(x)表示查找x的前序和,update(x, p)表示更新x下标对应的数组的数值为p,以下BIT为表示树状数组的简称。   模板…

Read more

codeforces round 324 div2解题报告

  好久没刷题了,前几天做google笔试生疏了很多,还是需要刷刷题,保持头脑灵活。不过codeforces题目一般都在晚上,真心没精力熬夜,只能改天起来再搞。这次是几天前的比赛。 A.Olesya and Rodion 简单题 B.Kolya and Tanya 简单题 C.Marina and Vasya   题意:给定两个字符串s1, s2,给定t,问是否存在一个相同长度的字符串与s1, s2各有t个字符不一致(位置不变)。   思路:判断s1和s2存在几个相同字符(相同位置),记为nr。记t=n-t,意味着找出n-t个一样的字符即可。则若不满足t - nr > (n - nr) / 2则不存在,反之存在。若t<=nr则这几个相同字符之内选t个即可,否则再把不一样的字符里面选t-nr个变为一样。  &e…

Read more