Update your browser to view this website correctly. Update my browser now
给定一棵树，从树中任意结点出发，遍历m个结点，最少需要结果多少个结点，结点可以重复走。 思路：找树中最长的链，也就是树的“直径”，假设为d，如果m小于等于d，则输出m就可以了；如果m大于d，则输出d+(m-d)*2，这是因为最长链上的分支路径需要走2遍（一来一回）。那么，直径也就是最长链怎么求？先从任意一个叶子节点x出发，找到最长的路径，假设路径结尾是y节点；再以y为根，找出最长的路径，这条路径就是树的最长路径。两次dfs可以搞定了。 代码： #include <iostream> #include <vector> using namespace std; vector<int> vis; vector<vector<int>> tree; pair&l…
退役好久了，惭愧的是一直没搞过树状数组和线段树，以前都是队友搞的，最近刷codeforeces被树状数组卡了好几次，遂决定怒刷树状数组。 0.算法 本来想写写长篇的算法过程，从如何建树到如何维护更新，结果发现这篇博客写的很赞了，我也就不写了，就写写个人对算法的理解以及刷的题目吧。 树状数组的优点就在于维护了一个前序和树，算法的核心就是『前序和』，碰到的各种题目也都是将各种模型转换为前序和，然后再进行查找和插入操作。 其时间复杂度如下：查找和插入/更新都是O(log MaxVal)，其中MaxVal表示树的最大下标，非常适合插入频繁的操作。以下read(x)表示查找x的前序和，update(x, p)表示更新x下标对应的数组的数值为p，以下BIT为表示树状数组的简称。 模板…
好久没刷题了，前几天做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…
