YoungForest's blog

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

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

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

排名: 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的数量，如果是偶数，那么最

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

赛后补的题解。 题目链接 主要参考的是 旷神 直播的解法，和官方 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

赛后补的题解。 题目链接 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

今天由于高中同学xl来北京找我聊，和hcq一起吃了午饭和晚饭，并聊了一下午。上午的contest只匆匆做了签到题。第二题因为粗心，写错了red变化的时机，也没有时间调试。后2题干脆没有看。 晚上回来9点才把题目补完，第二题的bug也调出来了。 不过时间上应该是超时了。 排名1800+。 总体来讲，本次题目虽然不难，但是需要花时间思考才能做出来的。这样的题目也是我喜欢的。通过自己的思考，作出一道并不是一眼看上去就知道解答的题目，是很爽的。快感可比超神和三杀。 5130. Number of Equivalent Domino Pairs 既然domino可以通过旋转相等，我们就把他们归一化

与博客不同，一本书相对内容更为完成，更为体系。博客相比之下就零散的多。不过优秀的系列博客也常常被改编成书。 如果你想分享规模更大，成体系的知识的话，写本小书是个很好的选择。 本文介绍一个工具GitBook，可以用Markdown写书，放在GitHub上，生成网页版和PDF版本的书籍。相较传统的Latex，更简单方便。适合当代程序员。 本文参考的资料主要来源于官网，相较之下，重点更突出，可以快速地 初始化、撰写、发布 一本书。 Install gitbook command line tool: 1 npm install gitbook-cli -g Create a book:

今年仍然是在学校度过了自己23岁的生日。下午和舍友出去看了电影《狮子王》，晚上去 城南旧事 吃了“北京菜。算是庆祝了自己的生日吧。祝我生日快乐。 自从18岁之后离开家，独自来到帝都读书。过生日就不再像在家里那么热闹和有人情味了。在外地漂泊，虽说还有同学或朋友祝你生日快乐，亲近的还会陪伴我一起过生日，但家人的温暖却再也没有了。大家来来往往，身边的人也基本只能陪伴一段时间。每每此时，都会怀念小时候。 最近北京的天气特别热，不由的心情烦躁。持续性混吃等死，间断性踌躇满志。经常思考些所谓的人生意义，努力的价值，自己的目标。 我本人可以说是胸无大志，从小读过不少书，尤其是历史书。早早地就明白了自己与王