YoungForest's blog

发表于 更新于 分类于 Disqus：
Cherries Mesh Minimum spanning tree. 尤其要注意Union-find的实现中，find要采用path compression的方法才能实现O(1). 否则会超时。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include #include using namespace std;
阅读全文 »

发表于 更新于 分类于 Disqus：
RankNameScoreFinish TimeQ1 (3)Q2 (4)Q3 (5)Q4 (6)106 / 1901YoungForest181:01:130:05:460:27:130:35:341:01:13本周参加 字节跳动的夏令营，周六开幕，所以本次的双周赛是在五星级酒店的床上完成的。好不舒服，比赛结果也还能看下去。 由于第二天上午要参加夏令营的课程，所以周赛就鸽掉了。不过下午的kick start round E还是参加了，翘掉了夏令营的课程。谁让我非常想去谷歌呢？ 双周赛题目不难，感觉像是其他OJ上类似的beginner定位。 1165. Single-Row Keyboar
阅读全文 »

发表于 更新于 分类于 Disqus：
RankNameScoreFinish TimeQ1 (3)Q2 (4)Q3 (5)Q4 (7)476 / 5091YoungForest191:31:130:03:520:09:231:16:13 20:50:16 1本次比赛效果同样不佳，排名在400+。直接原因是第3题的搜索剪枝花费了太长时间，没有一步到位。根本原因是最近2周好不容易放假在家，放松了练习，刷题基本停止了，自然手上的功夫就荒废了。真应了那句“业精于勤荒于嬉”呀。上周的排名同样很差。 1160. Find Words That Can Be Formed by Characters 常规的字母计数问题，用hashmap存储
阅读全文 »

发表于 更新于 分类于 Disqus：
RankNameScoreFinish TimeQ1 (4)Q2 (5)Q3 (6)Q4 (9)476 / 5091YoungForest151:00:140:10:210:42:141:00:14null惭愧的排名又落到400+了。最后一题有半个小时可以解决，一直试图用线段树来做。像kick start round D一样，沉迷于线段树而翻车。获得的教训是，不要纠结与区间问题一定要用线段树做，常常还有其他更简单的做法。 1154. Day of the Year 判断闰年，累加之前月份的日子。 时间复杂度: O(1), 空间复杂度: O(1). 1 2 3 4 5 6 7 8 9 10
阅读全文 »

发表于 更新于 分类于 Disqus：
RankNameScoreFinish TimeQ1 (4)Q2 (5)Q3 (6)Q4 (8)77 / 5319YoungForest230:56:450:09:510:24:020:41:200:56:45本次比赛是我时隔3个月再次进入前100名，也是连续2次进入前200名，还是有些小开心的。算是一扫上周kick start 翻车的阴郁。 事实上，由于评测机的问题，我比赛刚结束时看到的排名是56名。后来官方有重新评测了最后一题，有些人的提交就可以过了，也没有罚时了。 本次比赛也是质量蛮高，题目不是很难，但考察的知识点很全面，难度分布也比较合理。 1144. Decrease Eleme
阅读全文 »

发表于 更新于 分类于 Disqus：
RankNameScoreFinish TimeQ1 (2)Q2 (5)Q3 (7)Q4 (7)175 / 4906YoungForest211:14:320:08:18 10:27:17 10:41:321:04:32昨天做了Biweekly contest，今天做了常规赛和 下午的Google Kick D. 连续3场比赛，周末很充实。 1137. N-th Tribonacci Number 和 Fibonacci 类似。相同的解法应该都可以用在这里。 我采用了实现起来最方便的解法。 时间复杂度: O(N), 空间复杂度: O(N). 1 2 3 4 5 6 7 8 9 10 1
阅读全文 »

发表于 更新于 分类于 Disqus：
排名: 765 / 1866. X or What 本题是找规律的题目，考察最xor的熟悉程度。事实上，我曾经很接近于正确解法了。但一头心思钻到 interval 题目用线段树求解的经验上，试图寻找节点记录什么信息。结果越走越偏。 总结起来规律是这样的: 题目中给了xor-even的定义。 我们根据xor的性质有： * odd xor odd -> even * odd xor even -> odd * even xor even -> even 想要最后xor-even，interval中的odd必须是偶数个。一个非常直接的思路就出来了。统计odd的数量，如果是偶数，那么最
阅读全文 »

发表于 更新于 分类于 Disqus：
RankNameScoreFinish TimeQ1 (3)Q2 (3)Q3 (5)Q4 (7)98 / 1634YoungForest180:35:230:11:010:10:530:22:400:35:23距离上次参加biweekly contest已经2个月了，编号也从1直接跳到5了。 本次contest十分简单，都是算法里的经典的题目，属于必会的。我做完4题后还有近1个小时。 1133. Largest Unique Number 签到题。遍历一遍数组，然后计数。然后从大向小找符合要求的数。 时间复杂度: O(N log N), 空间复杂度: O(N). 1 2 3 4 5 6
阅读全文 »

发表于 更新于 分类于 Disqus：
赛后补的题解。 题目链接 主要参考的是 旷神 直播的解法，和官方 Analysis的解法。 Wiggle Walk 比较容易想到的是暴力解法。模拟整个命令执行过程，标记每个格子是否之前走过。 时间复杂度: O(N ^ 2). 虽然实际上凑巧可以AC，但比较冒险。理论上会在大的测试集上TLE。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 5
阅读全文 »

发表于 更新于 分类于 Disqus：
赛后补的题解。 题目链接 Building Palindromes 给定长度为N的一个字符串，和Q个Query。每个query是一个range，可以得到字串。判断子串重新排列后是否回文。因为可以任意重排，所以子串中字符的顺序不重要，重要的是每个字符出现的频数。频数为奇数的字符数目为0或1，即可重排为回文串。 因为N和Q的规模较大，10^5。平方算法会超时。这里借用前缀和的思路，快速计算子串字符频数。 时间复杂度为线性。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 3
阅读全文 »
0%