[算法笔记 3] Codeforces - 1139 D. Steps to One

如何求出 1-n 每个数的全部因子?
在继续往下阅读之前,请先想一想,如果给定一个 $n,n\leq100000$,让你求出 1~n 的全部因子,你需要如何实现?要编写多少行代码?复杂度如何?

可能会这么考虑,如果对于每个数 $x$,枚举 1~n 逐一判断每个数是否是 $x$ 的因子,复杂度为 $\mathcal {O}(n^2)$,显然是不可接受的,即使枚举到 $\sqrt n$,复杂度也有 $\mathcal {O}(n \sqrt n)$,依然太大,有没有更好的办法?

阅读更多

[算法笔记 2] 动态规划

关于动态规划的一些新感悟。
自从这学期学校开设了算法课之后,受到算法课老师的鼓励我突然又有了写算法题的动力。特别是老师第一节课重新回顾的动态规划算法,使我对动态规划有了一些新的理解。

其实之前我一直对动态规划有一种说不出来的敬而远之地感受。我最早接触动态规划算法可以追溯到高中的时候了,那个时候去少年宫学各种算法 (顺便和小伙伴们愉快的玩耍),记得学到最短路径的 dijkstra 算法,当时学了之后不由感叹,哇!还能想出这样的算法,也太强了吧!这怎么想得出来嘛!所以从那个时候起我每次知道某道题要用动态规划去求解时总会不由自主地头大。因此其实很长一段时间以来,我的动态规划的水平仅仅停留在最粗浅的三角形路径最大问题上 (就是那个很 naive 的给一个三角形让你求一条路径使得从左上角到右上角权值和最大)。

阅读更多

最近完成的一些算法题

一个多月没写博客了,赶紧填个坑。

kickstart
离上一篇博客居然已经过去一个多月啦,看来研究生还是要比本科忙多了,每天都有事情要做。最近呢,就是参加了昨天的 Google Kickstart Round G 2018,本来顺利做完了 2.5 题,做完的时候有 60 名左右,结果有个大数据犯了一个低级错误,结果一个大数据挂了,最后只有 100 多名!啊!好气啊!看了一下题解,发现方法和我自己实现的方法差挺多的,所以想简单讲一下我的算法。

阅读更多