博文
PKU题目分类,开始写解题报告(2008-05-31 10:09:00)
摘要：PKU题目分类,开始写解题报告
对于思路的扩展以及应用都是具有好处的
初期:
一.基本算法:
(1)枚举. (poj1753,poj2965)
(2)贪心(poj1328,poj2109,poj2586)
(3)递归和分治法.
(4)递推.
(5)构造法.(poj3295)
(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.图算法:
(1)图的深度优先遍历和广度优先遍历.
(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓扑排序 (poj1094)
(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)
(6)最大流的增广路算法(KM算法). (poj1459,poj3436)
三.数据结构.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)
(3)简单并查集的应用.
(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼树(poj3253)
(6)堆
(7)trie树(静态建树、动态建树) (poj2513)
四.简单搜索
(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.动态规划
(1)背包问题. (poj1837,poj1276)......
死亡——谁能告诉我活着的理由(2008-05-31 00:57:00)
摘要：ps:书本上读到的一篇文章，一辈子的问题，你能解答吗？
在17岁那年，我读过一句格言，好像是：“如果你把每一天都当成你生命里的最后一天，你将在某一天发现原来一切皆在掌握之中。”这个话从我读到之日起，就对我产生了深远的影响。在过去的这些年里，我每天早晨都对这镜子问自己：“如果今天是我生命中的最后一天，我还愿意做我今天本来应该坐的事情吗？”当一连好多天答案都是否定的时候，我就知道做出改变的时候到了。
因为所有的事情面对死亡的时候，都将因消云散，只留下真正重要的东西。在我所知道的各种方法中，提醒自己即将死去时避免掉入畏惧失去这个陷阱的最好方法。人赤条条地来，赤条条地走，没有理由不听从你内心的呼唤。
……
这是我最接近死亡的一次，在经历了这次与死神擦肩而过的体验之后，死亡对我来说只是一项有效的判断工具，相对一个纯粹顿理性概念，我能够更肯定地告诉你一下事实：没人想死；即使想去天堂的人，也是希望能活着进去。
你们还是新生代，但不久的将来你们也将逐渐老去，被送出人生的舞台。很抱歉说得这么富有戏剧性，但生命就是如此。你们的时间有限，所以不要把时间浪费在别人的生活里。不要被条条框框束缚，否则你就生活在他人思考的结果里。不要让他人发观点所发出的噪音淹没你内心的声音。最为重要的是，要有遵从你内心和直觉的勇气，它们可能已知道你其实想成为一个什么样的人。其他事物都是次要的。
在一本非常棒的杂志《全球目录》的最后一期的封底有一张清晨乡间公路的照片，如果你喜欢搭车旅行的话，经常会碰到这种小路。在照片的下面有一行字：物有所不足，智有所不明。这是他们停刊的告别留言。我总是以此自律。现在，在你们毕业开始新生活的时候，我把这句话送给你们。 ......
不再爱你(2008-05-31 00:54:00)
摘要：ps:考研的时候写的，刚回顾了下，感觉还是蛮有趣的就搬出来了。
我已经忍无可忍了，每一次的信任和忍受换来的却是更大的折磨和伤害，我只恨自己为什么没能更早的离开。你总是以作弄我为乐，一会这样，一会那样，把我支得团团转，你说这是为了锻炼我的应变能力。你还十分的自以为是，即使是错误的理论，在你，却能演绎的头头是道，蛊惑大众。
我更恨自己，为什么不能擦亮双眼，当初那么多候选者在我面前，论外貌，论知识，哪一个比你差了，而我却偏偏挑了你。为什么！？被你那虚假的外表迷惑？我知道，是我太急了，在没真正看清楚你的真面目前就匆匆做出选择。是我的错，我不应该抱着这种态度了。可是，自从那次决定之后，我待你如何你应当知道。为什么还要如此对我，不是都说一份付出一份回报吗？为什么我看到的全是失望呢？
今天我做出这个决定——我要把你彻底的抛弃，不，是彻底的毁灭！不但如此，我还要把你的丑闻公布于世，让大家都知道你的真实嘴脸。哈哈：)这是你应得的惩罚。也许你们会说我这么做太残忍了，然而比起你对我的伤害那只是九牛一毛，沧海半粒。你不仁，我不义！！！
随着一个优美的曲线，《聚焦2008考研数学十年真题全方位解码》飞向了火海。而我——一个08考研人，从此获得了新生！......
爆笑——CS才是王道(2008-05-28 18:39:00)
摘要：PS:转自飘渺水云间,纯属娱乐。
1
我一直深爱著一个女孩
虽然女孩也深爱著我
不过由于他老爸 对于我个人有点意见
一直帮他安排对象
这点让我非常困扰
有天 他爸在他家设下晚宴托我女友跟我说今天务必赏光
我心理知道 其中必定有诈
甚至招来难堪羞辱..
但是为了深爱的女友 我义无反顾的去了
到了他家
开们的是一个高高壮壮的帅哥
说他帅真的一点都不夸张
他只穿一件黑色背心 露出扎实的肌肉
干 还我微笑的时候故意抖动了两下奶子
我入座后 未来的岳父 跟我介绍那个男的
他跟我说 呵呵 人家他是小敏的青梅竹马
刚从美国加州柏克力分校拿到硕士学位回国
可说是 青年才俊阿
我一脸沉默 他老爸得理不饶人开头就劈问我
小子 你多高?
我: 我只有170...
哈哈 靠 我看你是少了号称两个字吧
人家mike 身高一米九 体格又棒
我女儿若嫁给他不知道有多么幸福喔
这时候我看了看小敏的眼神
他眼神中似乎替我们的未来感到忧心
我知到岳父是故意找我来给我难堪的...
我越发沉默
你动产不动产加起来多多少?
我: 我有一间两楼的平房 存款两万多吧
哈哈 一间破房子 一点点钞票
人家mike在欧洲有一座自己的城堡 你这个穷小子
可悲..
妈的 我再也受不了这种羞辱正想站起来起身离开
小敏拉了拉我的衣角 .. 眼中含泪求我不要走
不要轻易放弃他..
这时候 ......
记一场电话面试(2008-05-25 23:21:00)
摘要：面试持续了51分钟，一开始是简单聊些简历上的项目，接着提出了下面的四个问题：
1，给定一颗树，他的节点只有指向儿子的指针，没有指向父亲的指针，问给定任意两个结点A,B，求他们的最短路径？
此题不难，一时紧张，卡在那里不知如何下手，但是我还是坚持跟他耗着先:-)——可以直接当作图用dijkstra算法。对曰：没有父节点的指针，无法向上走。这话激活了我的思维，最短路径不就是离A,B最近的公共父节点到A，B的路径嘛。那么问题已经转换成了寻找公共父节点，因为A,B无法向上走，所以，问题又转换成找到从根结点到A,B的那两条路径(树中，根结点到任意一结点的路径是唯一的!),然后寻找其公共父节点。
那么如何搜索呢，我当初的想法是，不知道A,B节点的具体位置，宽搜相当与是一层一层往下找，平均最优。
对曰：那在叶子节点岂非十分耗时？我说没办法，平均考虑。对曰：为什么不先做个简单的判断，如果在叶子结点就直接深度？这话又激活了我的思维，于是我说可以综合考虑两种搜索算法，先可以尝试性的从A,B往下走，看看离根的距离，然后再与整棵树的层数做个比较，看离哪边近作相应的算法选择！此题结束》
2，写一个内存拷贝函数void memoryCopy(byte *source,byte *dest,int len)从source指针开始复制len个字节到dest指针处，问设计此函数会碰到那些问题。
开始进入状态了，我在纸上一画，便答曰，如果两个内存区存在交叉区域，会出现数据丢失的情况。例子如下：
复制[1,10] ==> [6,15],首先[1,5]复制到[6,10]把原来的数据给填充掉了。原来[6,10]上的数据已经永久丢失...解决策略如果首尾相接，倒序复制，that's all。
3，用c语言模拟多态
我没能嚣张太久，因为马上就碰到了这个问题，他是先让我描述下c跟ｊａｖａ的区别，然后蹦出这个题目。
一时傻眼，因为无从下手。对曰：来个具体例子吧：B类和C类继承A类，他们都有个方法叫fun(),现在只有A类的引用，但如果该实例实际上是B，C类则，调用B,C类的fun()函数。
。。。
几经周折，给出......
pku3508 一个有趣的小学算术题(2008-05-22 09:39:00)
摘要： 题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=3508
/*
一开始想用1n 2n到9n直接看能否整除11，结果TLE。
很纳闷，看别人才89ms，纸上一画才发现不就是小学算术题吗?
a b c 0
+ a b c
---------- (a>0)
3 5 3
*/
#include <stdio.h>
#include <string.h>
#define MAXSIZE 1000000
char h1[MAXSIZE+2],h2[MAXSIZE+2];
int len;
int main()
{
int i,jin;
int t=0;
while(1)
{
scanf("%s",h1+1);
len = strlen(h1+1);
if(len==1 && h1[1]=='0')
break;
for(i=1;i<=len;i++)
h1[i] -= '0';
h2[len+1] = 0;
for(jin=0,i=len;i>=1;i--)
{
h2[i] = h1[i] - h2[i+1] - jin;
if(h2[i]<0)
{
h2[i] += 10;
jin = 1;
}
else
jin = 0;
}
if(h2[1]==0)
printf("%d. IMPOSSIBLE\n",++t);
else
{
printf("%d. ",++t);
for(i=1;i<=len;i++)
printf("%d",h2[i]);
printf("\n");
}
}
return 0;
}
......
pku1351 动规——记忆化搜索(2008-05-22 09:35:00)
摘要：题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1351
/**********pku1351************
* 动规——记忆化搜索
* a[n][p][k][u]
* n: 统计了几个slot
* p: 当前取道那些值 按位存储p=7(0111)表示已经取到1,2,3
* k: 最后一个值
* u: 是否满足条件1
* 注意答案会超过32位整数
******************************/
#include <stdio.h>
#include <memory.h>
__int64 a[20][16][5][2];
int flag[5] = {0,1,2,4,8};
void init()
{
int i;
memset(a,-1,sizeof(a));
for(i=0;i<=15;i++)
{
a[1][i][1][1] = a[1][i][2][1] = a[1][i][3][1] = a[1][i][4][1] = 0;
a[1][i][1][0] = a[1][i][2][0] = a[1][i][3][0] = a[1][i][4][0] = 0;
}
a[1][1][1][0] = 1;
a[1][2][2][0] = 1;
a[1][4][3][0] = 1;
a[1][8][4][0] = 1;
}
__int64 ado(int n,int p,int k,int u)
{
int t;
if(n<=0) return 0;
if(a[n][p][k][u]!=-1) return a[n][p][k][u];
a[n][p][k][u] = 0;
if((p&flag[k])==0) return 0; /*p不包含k，直接返回0*/
t = p&~flag[k];
if(u==0)
{
if(k==1)
{
a[n][p][k][u] += ado(n-1,p,1,0) + ado(n-1,p,2,0) + ado(......
别把考研当回事(08考研者经验)(2008-05-22 09:30:00)
摘要：
别把考研当回事
——写给所有正准备参加考研的莘莘学子们
其实考研是自己一个体验的过程，成功是不能复制的，经验也只能是经验。
别太把考研当回事，让一切顺其自然，坚持到底，明天的你们不会输给今天的我们。
考完研就想写篇文章纪念这段特殊的日子，不过太lazy，一直没写。现在一切已经尘埃落定，新一年的考研准备似乎又已经悄悄开始，所以写篇文章介绍点经验吧。
像以往考完研后的每一天一样，日子过的悠闲而平静，不用担心还有一大堆复习资料没有看，也不用担心饭后散步会浪费大好的学习时光。昨天，我正准备关了电脑去吃晚饭，看到有个群消息在闪动就双击了一下。这是浙大考研的群，有人说初试成绩已经可以查询了，而且还留了链接。“通知不是说是10号出成绩的吗？”，怀着忐忑的心点了进去，结果真的是浙大研究生入学招生网上的查分系统。这下紧张了，向来的洒脱一瞬间被洒脱的丢掉，决定命运的时刻到了。心里微微发抖，拿出准考证号，输入姓名，确认，成绩弹出的一刹那，心里猛的一纠。仔细一看，没错392(政治77 英语66 数学122 专业127)!!!再看姓名，真的，这是我的成绩，我哇的一声站了起来 (比预测高了50多分)…
1. 写给犹豫中的人(个人意见，仅供参考)
虽然以前也有过考研的想法，但直到大三下我还是倾向于工作的，那时想学计算机的当然以工作经验，动手能力为主，而且三年的工作经验是相当厉害的。后来我的好兄弟的一通电话改变了我的想法“现在出去工作，差点2,3k,好点4,5k，工资涨涨，混混，一辈子就这么过去，没太大意思。学计算机，应该把技术学精，闯出点名声，做出点自己的东西来！！！”。也许最后一句话吸引了我，当初就这么定下了考研大计。另外还有句话，比较牛“先不用犹豫，把研考上了，读不读到时候再说”。
考研的人大致可以分以下几类吧：
1、 真正对学术非常感兴趣，一心想做研究的
2、 喜欢通过读研提升自己的实力，找份好的工作（有一些好的研发部门是不招本科的）
3、 通过考研换掉原来不太适合自己的专业
4、 喜欢校园的生活，不想太早去社会
5、 家人的逼迫等等非自愿情况
我想1、2两种人是社会真正需要的研究生，鼓励考研，第3种比较难说，第4种勉强，第5种就不多说了，太悲......