推荐时间到了,从Noip结束后一直在学习C语言,来推荐下了..
有点基础的呢,就去看那本<The C Program Language>(C程序设计语言),听了Douban上的某些评论,买了那本英文原版的,可以接受,后来又去上海图书馆把翻译版的借了回来,要是只论理解难易度,果然英文的好.
就是有一点,这是关于K&R C的教材,和AnsiC还是有些细微不同的.
然后就是<C陷阱与缺陷>和<C专家编程>.这里面把一些容易忽略的细节整理了一下,还是满值得一读的.其中所写的K&RC和ANSIC的不同点刚好可以补充前一本书.
再然后呢,就多切题吧.....
感觉与Pascal相比,其中指针的作用更加明显了,和系统底层的联系从这里也可以体现出来.
Bless.
大多数是水.....部分感觉比较有特点的加*..不定期更新
线性动态规划
VOJ1355 车队过桥问题 f[i]表示前i部通过最短时间,预处理t[i,j]表示i到j的最慢速度,w[i]表示前i部车的重量和,f[i]:=min(f[k]+l/t[k+1,i])
VOJ1292 火车票 f[i]:=min(f[k]+cost(k,i))
*VOJ1474 雷曼兔(csapc) 排序后类似Lis
VOJ1571 笨笨的导弹攻击 最长上升下降混合子序列...orz
*VOJ1696 爱国者的周期 同上 判断周期用 (f[j]-1)mod(t*2)<t
VOJ1421 更换轮胎 f[i,j]表示第i圈用j种车胎所需最短时间,另开l[i]表示第i圈的最短时间用的车胎号码
*Open09ski 滑雪 f[i,j] 表示于i时间j能力所能得到最多滑雪数 f[i,j]:=max(f[i-1,j],f[i-d[g[i]],j]+1(j>=c[k]),f[i-l[k],0](0为i-l[k]时最大达到))g[i] 表示能力为i时 所能滑的最优轨道号码
VOJ1331 看球的巴士 f[i]:=min(f[j]+1)(abs(s[i]-s[j])<=d)or(abs(s[i]-s[j])=i-j) f[0]=0 f[1]=1
Cai0715-1 一起去打cs f[i,j]:=min(f[i-1,j]+b[i],f[i-1,j-a[i]]) 状态 完成i-1件作业耗甲j时间时,所需乙最短时间 决策 第i件交给谁做
VOJ1118 统计字符串 预处理g[i,j] i-j间字符串个数
*VOJ1037 搭建双塔 f[i-1,j] 不放 f[i-1,j+h[i]] 放到矮塔仍为矮塔 f[i-1,h[i]-j]+j 放到矮塔变成高塔 f[i-1,j-h[i]]+h[i] 放到高塔
背包问题
VOJ1625 精卫填海(HOI) 01背包
VOJ1418 公司聚会 倒推01背包 f[p[i],j]:=max(f[p[i],j],f[p[i],j-k]+f[i,k]),最后判断职人1号是否更优.
VOJ1544 GF 裸两维背包
VOJ1392 拼拼图的小杉 伪01背包 f[i,j]表示前i件物品选j件,所需最小集合数,g[i,j]表示最后一个集合已填充容量
VOJ1198 最佳课题选择 f[i,j] 前i种论文完成j件所需最短时间 f[i,j]:=min(f[i-1,k]+a[i]*(j-k)^b[i]) 0<=k<=j (分组背包也可做)
*VOJ1313 金明的预算方案 有依赖背包->分组背包
树形动态规划
*VOJ1180 选课 基础树形.f[k,t]:=max(f[r[k],t],max(f[l[k],t-1-i]+f[r[k],i]+s[k])) (i=1..t-1)
区间动态规划
*VOJ1242 邮局问题 f[i,j] 1到i的村庄,修j个邮局的最小距离,预处理d[i,j],表示于i,j中点修建的距离和,f[i,j]:=min(f[k,j-1]+d[k+1,i])
*VOJ1347 乘积最大 f[i,j]:=max(f[k,j-1]*s[k+1,i])
VOJ1218 数字游戏 预处理s数组后同乘积最大 f[i,j]:=max(f[k,j-1]*s[k+1,i])
多进程动态规划
VOJ1493 传纸条 f[i,j,k]第i步,A的x位置于j,B的x位置为k的最大值
*VOJ1143 三取方格数 同上,四维,第一维可用循环数组消去.
*VOJ1014 旅行商简化 f[i,j]:=min(f[j,j-1]+s[j-1,i],f[i,j-1]+s[j-1,j]) (i>=j) f[i,j]=f[j,i] 避免跳过路程,必须从近的一点j进行扩展
VOJ1680 距离 字符串距离 f[i,j]:=min(f[i-1,j-1]+d[i,j],f[i-1,j]+k,f[i,j-1]+k)
VOJ1111 水果店 总长度-最长公共子序列
状态压缩
*VOJ1424 炮兵阵地 把每一行状态用二进制存储于一个longint中,预处理每一行可能摆放,存于p[i,j],由于一行只与前两行有关,
f[i,j,k]:=max(f[i-1,k,t]+addnum(p[i,j])) f[i,j,k] 表示到第i行,第i行摆放为p[i,j],第i-1行为p[i-1,k] 时的最多炮兵数
Matrix67-0817 多米诺 类似上一题,状态压缩每一行状态,70分
递推
VOJ1232 核电站问题 连续N个东西,不能选连续m个的选法总数
VOJ1408 古韵之乞巧 f[i,k+1]:=f[i,k+1]+f[j,k] 以s[i]结尾的长为k+1的方案数
记忆化搜索
VOJ1547 逆转，然后再见 诡异的记忆化搜索..
VOJ1011 滑雪 同上
很久没更新啦...很不好..写几句..
10.1开始正式准备NOIp..先把初赛题做完....不能免修的怨念啊....只能干这个了....>_<
话说...前13届的题目居然翻出一本去年打印的...一个字没写...囧..我是说我一个字没写...恶趣味...
继续怨念.怨念下月考.......
话说..逐渐宅化中....
Luckystar Clannad K-On 凉宫 凉宫酱 鹤屋 零使......
囧掉....Clannad游戏不错..真的....
暑假之后收了一只铁三角CM-3,一只罗技LS-1......
不错是不错....有点小贵了....
给移动硬盘上了个ubuntu,很方便..
对了...OSU!很好玩....有空去磨损鼠标去.....
air&kanon就等1=后(要是有的话)再玩了~
加油了..有点小期待~
不就四道题么...
~(*^__^*)~
吐槽怨念文结束..继续背单词去~下面呢..大牛们就帮忙看下吧=.= Read the rest of this entry »
去烟台兜了一圈,主要是听课,但是呢...很明显,我不会一直呆在宿舍的..
一共出去玩了3次,市区的一些比较好看的地方都去兜了兜吧~
海边,烟台山,十字街教堂,广仁路.
日全食是错过了,但还有偏食看,观测条件相当好,云都看不到几片,就是没装备,拿了个曝光胶卷加上透明胶带,做了个滤光镜,上课前做的..WJD看着我笑了好久..囧
效果还可以.只是能拍,能看的等级,后来又用Gimp滤掉了一点红色,比较满意了
感觉烟台的节奏很缓慢,上课安排很不合理,经常空出来半个小时一个小时,集中在一起都可以去蓬莱玩一圈了>_<
本来还想最后一天去芝罘岛玩一圈,但天气不是很好,再加上寝室人都走光了,行李没地方放,无聊地去了一家上岛咖啡,还没有无线网络,伤心啊..
那天RP差,飞机还误点,到家晚了4个多钟头..机场的移动Wlan很方便,早知道下午也呆那里了..
照片用的是GooglePicasa相册,自己想办法吧~或者想看的话留言也行,其实认识我的,校内上也有不完整未修图版~^^
照片还算比较正常,loli出现次数不算很多..- -
特别赞一下去烟台山那天的天气,天很蓝~
In your life, there will at least one time that you forget yourself for someone, asking for no result, no company, no ownership nor love.^^......
动态规划
你追一个MM的时候，需要对该MM身边的各闺中密友都好，这样你追MM这个问题就分解为对其MM朋友的问题，只有把这些问题都解决了，最终你才能追到MM。
该方法适用于聪明的MM，懂得“看一个人，不是看他如何对你，而是看他如何对他人。”的道理，并且对付这样的MM总能得到最优解。
该方法的缺点是开销较大，因为每个子问题都要好好对待。。。。
--------------------------------------------------------------------
贪心法
你追一个MM的时候，从相识到相知，每次都采用最aggressive的方式，进攻进攻再进攻！从不采用迂回战术或是欲擒故纵之法！目标是以最快的速度确立两人关系。
该法优点是代价小，速度快，但缺点是不是每次都能得到最优解。。。。。
--------------------------------------------------------------------
回溯算法
追一个MM，但也许你还是情窦初开的新手，不知道如何才能讨得MM的欢心，于是你只好一条路一条路的试，MM不开心了，你就回溯回去换另一种方式。当然其间你也许会从某些途径得到一些经验，能够判断哪些路径不好，会剪枝（这就是分支估界了）。你也可以随机选择一些路径来实施，说不定能立杆见影（这就是回溯的优化了）但总的来说，你都需要一场持久战。。。。
该算法一般也能得到最优解，因为大多数MM会感动滴！！但其缺点是开销大！除非你是非要谈一场恋爱不可，否则不推荐使用。特别是你可能还有许多其他的事情要做，比如学习，比如事业。。。。 Read the rest of this entry »
RP，是人品的缩写，在民间广为流传，被不少人视作真理，也有很多人将之视作迷信。
真的很早就了解到RP在信息学竞赛中举足轻重的作用了，加上前两天由于爆RP考试爆零，星际被虐，交OJ莫名其妙unac……一切的一切，让我不得不把RP的理论系统篆写于书，以供参考，防止大家重蹈我的覆辙。
众所周知，在信息学竞赛中，除去算法数据结构使用，程序编写调试能力之外，排在第三的对比赛有至关重要作用的便是RP了。RP高的人即使不知道算法也能用随机，贪心，搜索等RP算法得到无比多的RP分数；相反，没RP的人，有时知道正确算法也写出了正确程序，也往往会因为缺少RP而无法得分。
这样看来，系统研究RP的积累于损失，以及量化地分析它对比赛的结果的影响就显得十分重要了。
但是，目前国内外系统研究RP的论文和书籍都还很缺乏，也有很多优秀的OIer认识到了RP的重要性，但又因种种原因没能从事RP方面的研究，导致很多OIer因为对RP不了解而出现发挥失常，与奖牌失之交臂，为了让这种悲剧不再发生，我们有必要仔细研究RP。
RP是大家耳熟能详的一个词汇和概念，改革开放以来，随着市场经济的深入，竞争日益激烈，大家都在寻找在各自领域取胜的有效方法，人们考虑各种因素来提高自己成功的概率。
江湖难测，谁是强者，谁争一统武林的资格！
在这样的大背景下，便自然而然地产生了RP的概念，起初这个概念还是依附在其他因素上的一个附属品，但是当人们真正认识到它的影响时，才发现它是一个独立的体系。由于各地各文献内容对RP的定义都很模糊，也不够统一，因此笔者在此一学术的角度，客观的方式给出RP的严格定义：
RP：在一定时间和空间范围内独立于可见因素之外以不确定方式左右客观事物变化方式甚至规律的无形物质。 Read the rest of this entry »
