POJ 1328 Radar Installation 贪心
version 1
从右到左排序,每次都尽可能的选打击范围内最右边的点安装雷达(由于浮点,所以不要一棒子打死的判断是大是小,给出一个精度范围,一开始范围给打了就WA),拿这个雷达去覆盖其他点,最后雷达总数一定是最少的
1 | /* |
version 2
找到以每个岛为圆心的圆与x轴左右交点形成一个区间,按左端点关键字升序排序后,用右端点去覆盖之后的点(如果遇到更小的右端点应该把目前的点更新),遇到不能覆盖的就雷达数目+1
1 | /* |
version 1
从右到左排序,每次都尽可能的选打击范围内最右边的点安装雷达(由于浮点,所以不要一棒子打死的判断是大是小,给出一个精度范围,一开始范围给打了就WA),拿这个雷达去覆盖其他点,最后雷达总数一定是最少的
1 | /* |
version 2
找到以每个岛为圆心的圆与x轴左右交点形成一个区间,按左端点关键字升序排序后,用右端点去覆盖之后的点(如果遇到更小的右端点应该把目前的点更新),遇到不能覆盖的就雷达数目+1
1 | /* |
一开始用的DFS,无限TLE,贴丑代码
1 | //version 1 TLE |
之后冥思苦想了好久,两个序列,开始没有想到变形的LCS(最长公共子序列),只是试着写状态转移方程,最后就写成了那个dp[i][j] = max(dp[i-1][j-1] `,dp[i-1][j]`````,dp[i][j-1])的样子,这时一看才明白这是LCS思想,但是一开始确实是瞎写的,可能碰巧了吧=。=,最后注意这种情况:dp[0][x],当一个序列之前都用0补上的话,在循环过程中是没办法得到结果的,只能预先处理,切记!
1 | /* |
Prim 最小生成树模板,直接上代码
1 | /* |
一些事情,看开了一些事情,不算看开吧,只是在事实面前不想做反抗也做不出反抗罢了。
今天下午两点到五点,理工配楼二层信息学院ACM大赛,ACMore_txj,ACMore_znc,ACMore_yld,共12道题,三个小时做出四道题,两道一直WA,没过,二等奖。一等奖五道题目。哎,即使不是正规的ACM/ICPC题目,还是感觉到自己太弱了,真的太弱了。仰仗学了不少模板就以为可以变厉害了,其实不是,ACM的题目更多的还是需要思维而不是记忆的,正如ACM朴神说的:“现在ACM模板题目已经不多了,更多的是多种算法思想混杂在一起需要自己去组织”。真的不能再沉迷在POJ排名上了,现实说明你仍然是以前那个蒟蒻,你的实力并没有提高多少,无非就是见得多一点,仅此而已。至于怎么真正提升自己,我不知道,我真的不知道,得过且过?还是由算法研究转向应用呢?真的想要动摇了,毕竟不是ACM队的,又何必?
刚刚过掉一道题,这题是上学期接触编程不久后做出来的,但是刚刚在做的时候却一直WA,脑海里一直想着当初是怎么1A的,尽量去揭开那时的记忆拿到算法,但是总想不出来,过了好久还是没过,只能打开以前的文件夹看了一下以前的做法,我现在的做法和那时几乎相同,但是有一步比较关键的没想到。也许是看不起那时的自己,认为那时能A的题目现在一定能A,但是事实说明,目前好像有点自信心过于膨胀了。POJ上连续刷了半个学期的题目,一口气看了很多算法和数据结构,就认为自己已经变牛了,可事实说明,你还是当初那个什么都不懂的你。圣人尚自谦,何况你还不是圣人,何况这一行有那么多的惊才绝艳的天才妖孽,你凭什么飘飘然?脚踏实地才是王道,学院ACM队的大牛现在仍是我不可企及的目标,何况还有国家队的大神呢?
好了,清醒一下,后天就是学院举行的程序设计大赛,争取拿个好成绩吧。
字典树,就是一种最大限度的利用单词的公共前缀高效查询单词(但不止是单词,所有有前缀的都可以类似进行查找)的数据结构。节点定义如下:
1 | struct node |
建树和查询都非常方便,删除操作并不常用,比较偷懒的方法就是找到待删除单词的最后一个字母所在节点,把isWord标记置为false即可。代码就不给出了。
需要注意的是,在实际建树过程中,如果动态分配空间无论是new还是malloc都会很慢,一般都会TLE的,所以代码都是静态实现,即先分配一定的空间,需要用新节点时就从空间里拿。
例题:
一、POJ 2503 Babelfish
1 | /* |
二、POJ 3630、Phone List
1 | /* |
作者: JACK ALTMAN 来源: 36氪
1 | 人们对机会的估值过高,这是我在下棋的时候学到的一点。你其实只需要一个好的选择就行,没必要同时去追求 A、B、C、D |
是让你的选择尽可能开放,还是全心全意抓住一个选择,专心做好一件事情——可以说这两者之间的权衡,是我们生活中经常会碰到的。我们自打上学起,就一直被教育不要去做那些可能会断了某条路的决定。
这种让未来保持开放,让自己未来拥有更多选择和出路也是可以理解的。握在手中的成功机会越多,你的未来也就会越成功,不是吗?
不细想可能会觉得保持开放的确很好,但我认为事情并非看上去那么简单,原因如下:
我时常会将这个权衡同创业公司连系起来思考。在创立一家公司时,创始人也会面临这个权衡,究竟是让未来更加多元,更开放,同时追求好几个选择,还是专注的做好其中一个。而通常,最好的创业公司都会选定一个,然后寻找一切方法让它成为现实。自然,也有很多创业公司他们并不清楚未来的路,他们相信手中握有的诸多好的选择中,总有一两个能行得通。
记住,在某一个水平上,你一次只能做好一件事情。能够拿到你最想去的学校和公司的 Offer,比拿到在你 Reference 排名中名列 2-5 位的 Offer 要好。而在一件事情上能够做到 99%,也比在 2 件事情上都能做到 90%,或者 3 件事情上做到 80% 要强很多。
如果你可以在不失专注的情况下够获得一些机会,那就抓住它们。这里我并不是宣扬你得故意同机会保持距离。我要做的就是让人们开始重视专注,因为同 Peter Thiel 一样,我也认为人们普遍高估了机会的价值。
用STL的queue实现BFS,最基础的题目了,不多说上代码
1 |
|
二叉树的重要的遍历序列有三种:先序遍历,中序遍历,后序遍历。其中中序遍历可以由其他两种遍历序列定位的根来划分出左右两棵子树,所以已知的两种遍历序列中必须有中序遍历。
示意图(先序+中序->后序)
对于先序遍历序列,树根一定是第一个元素(后序遍历的根则是最后一个),知道树根后在中序遍历中找到树根,则根前面的就是左子树,后面的就是右子树,再递归的对左右子树执行上述操作直到序列为空,输出序列就是另一种序列。对于求先序序列,每次都是找到树根就输出,而求后序序列时是先递归处理完左右子树后再输出根。
代码:
输入中序和后序,求先序
输入:
DBKFIAHEJCG
DKIFBHJEGCA
输出:
ABDFKICEHJG
1 |
|
输入中序和先序,求后序
输入:
DBKFIAHEJCG
ABDFKICEHJG
输出:
DKIFBHJEGCA
1 |
|