WTommy的无悔青春

今天又进行了一门重要考试，是本学期最后一门关于数学的考试--离散数学，面队如此难的考题，我甘拜下风，答的我是一点脾气都没有哈！~估计凶多吉少了。。。

剩下的科对我都是不是很难了~。。。数据结构由于参加程序比赛已经基本掌握。。计算机组成原理剩下5，6天看看就OK了~一想马上就要暑假啦，暑假要集训呢，一想就是满脸的期盼。。呵呵！

目前已经在ZOJ上做了296道题目了~

从三个月前初次接触程序到现在已经有100天左右了，回望自己的进步，简直可以用“飞速”形容！！

但是离参加比赛的水平，自己认为还差很多很多~。。。

这100天里，我是从一个连输入输出有的时候都搞不明白的C user一点一点的进步。。。从最基础的C语言语法开始学习，数据结构，算法。。回头看看还真是辛苦！！曾经多少个梦里都在想题，多少个夜里失眠，自己受过的苦只有自己知道！~

但如今已经有了很大的进步，我很有可能会代表我最尊敬的大学去参加。。为荣誉而战，也为自己大学里的理想而战。。。

目前的我只想着如何提高自己水平，至于ZOJ上做题的数量也只是个摆设罢了，鬼知道有多少题是你自己亲手做出来的，forum,google。。。。这些手段。。。对于以后的发展来说，算法才是最关键的！

希望提醒所有参加ACM比赛的兄弟们：

To be a real ACMer is  hardworking on Algorithm and Data Structures , not comparing the number of the questions you have solved on the Online Judge....

努力努力在努力。。。

偶大一新鸟，第一次实验楼上课，课间大便。见一厕所门挂带男字门帘，急掀帘而入。不料遇一女生小解完，正用面巾纸擦拭下身液体。由于小猫是CN，立马呆立当场，只觉有股热血由脚底板直冲头顶，将大便都顶了回去。女生漂亮与否并未得见，只见乌黑一片。

　　那女生一看至少大3大4学姐，经验丰富。不慌不忙的将面巾甩进纸篓，徐徐提上牛仔裤。以过来人的口吻对偶说：大一新生吧，那面才是男厕，我们经常挂错帘子来消遣的。偶急忙退出，已大汗淋漓。

　　偶出来后，心跳加速，久不能平静。懵懂中走进挂着女字门帘的男厕所内。找坑，解裤，蹲下，办事。脑里还一直回味刚刚的偶遇。

　　方便过后，偶打扫完战场站起来刚抓住裤腰准备提裤子，旁光一扫，右坑位一女生正侧眼看我。其裤子也正褪到一半，正用手揭NK 上的卫生J。仔细一看，却是同班MM， 她也正在愣愣的看着我。

　　俄而，偶俩同时反应过来，急忙一起提裤子。MM粉白，小巧玲珑，偶实非故意注视其下体，但见红与黑相连，心潮澎湃不能自已。

　　MM脸刹时通红，而后偶俩发生了令我至今暴寒不已的对话。偶以猫格担保： 以下为对话实录，决未经过任何人为添加或修改。

　　MM：“来上厕所啊？”（天知道她为什么会问出这么一句话）

　　偶：“啊，恩那。今天有点坏肚子了。你也来了？”（偶当时真的说话没经过大脑，一点思维都没有了，偶对天发誓，偶可是问她来上厕所了，可不是问她月J来没来。）

　　MM：啊！（脸更红了）到了这儿就水土不服，真倒霉，提前好几天就来了。（看来MM的思维也很混乱并不比我强多少）

　　偶：……（无语，实在是找不到话回答了）

　　终于，在这当口，偶俩都把裤子提上了。MM脸色回复了点正常，偶思维也转过点来了。偶俩异口同声的说：“你走错厕所了吧？”说完这话，MM定定的看着我，坦白讲，眼睛很大，也很好看。

　　MM：“女厕所啊，挂的帘子上不是写着么？”（口气变的强硬起来，意思是一大学生还不认识男女厕所么？看样子，偶要是找不到走错的证据，MM很可能以为我是故意进来偷看而当我成色狼的。）

　　偶巨崩溃，一日内俩次被女生指责走错厕所，这要是传出去我这大学也就不用念了。可是又不能跟MM解释是刚才走进那个厕所被女生赶了出来，所以才进这个厕所的。偶觉得自己的脑子里面也像有一驼大便，憋的慌。

　　终于天无绝人之路，被偶抓到了极为有利的证据证明偶的清白。偶对MM说了偶都不能不拜服自己的一句话：“男厕所啊，我问过的，帘子挂差了而已。再说你们 女生应该用不着这个小便池的吧？”说罢，偶得意的指了指厕所里面的小便池。

　　果然此话具有极大杀伤力，MM的脸一下红的更胜刚才。头都垂下去了，嘟囔道：“真是不好意思，打扰你了。可是我得换一下那个东西了，你能不能帮我在门口看一下啊？我刚才看见咱班班长进那个厕所了，我没法进去换呀？！”

Cartesian树（笛卡儿树）是一种特殊的堆，它根据一个长度为n的数组A建立。它的根是A的最小元素位置，而左子树和右子树分别为A[1...i-1]和A[i+1...n]的笛卡儿树。

例如：数组A为 5 4 6 2 7 9 8 1 3 10

则这棵Cartesian树为:


由上图可以看出，A[1]...A[n]为这棵树的中序遍历。

那么，如何建立Cartesian树呢？

根据他的定义，按照顺序来找最小值，但是这种算法的最坏情况下的复杂度是O(n^2)的。

现在来介绍一种复杂度为O(n)的算法。


Cartesian树的建立算法：

首先，先从A[1]开始建立，以后每次加一个数，就修改Cartesian数，不难发现，这个数一定在这棵树的最右边的路径上。而且一定没有右孩子（应为数组为树的中序遍历），所以，只沿着最右路径自底向上把各个节点p和A做比较，如果p>A，那么比较p的父亲与A，如果A>p的父亲，那么A为p的父亲的右孩子，而p则改为A的左孩子。因为每个节点最多进入和退出最右路径各一次，所以，均摊时间复杂度为O(n)。

参目： Sgu 155 Cartesian Tree

由于各种原因告别了Starcraft好久拉！昨天参加天大对南开的对抗赛，原本也想出场，但是一想还是以后多加练习后再表演吧。。。省得给天大丢人啦~~

昨天的比赛南开真是不重视，害得我们天大50多个SC fans等了两个多小时，唉。。。不过看到天大传说中的职业选手fish的精彩表演，可以第一视角的哦。。~~真爽，发现星际原来是这么打的。

人家的意识，人家的判断，人家的大局观，简直就是神一样的人物（纯属个人崇拜）呵呵~

决定今后编程编累的时候也玩玩这经久不衰的经典计时战略游戏~

嘎嘎。。。

一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm主要是考算法的，

主要时间是花在思考算法上，不是花在写程序与debug上。  
下面给个计划你练练：  
第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，

因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打

出来.  
1.最短路(Floyd、Dijstra,BellmanFord)  
2.最小生成树(先写个prim,kruscal要用并查集，不好写)  
3.大数（高精度）加减乘除  
4.二分查找. (代码可在五行以内)  
5.叉乘、判线段相交、然后写个凸包.  
6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)  
7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.  
8. 调用系统的qsort, 技巧很多，慢慢掌握.  
9. 任意进制间的转换
第二阶段：练习复杂一点，但也较常用的算法。  
如：  
1. 二分图匹配（匈牙利），最小路径覆盖  
2. 网络流，最小费用流。  
3. 线段树.  
4. 并查集。  
5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp  
6.博弈类算法。博弈树，二进制法等。  
7.最大团，最大独立集。  
8.判断点在多边形内。  
9. 差分约束系统.  
10. 双向广度搜索、A*算法，最小耗散优先.

暑假将至，回家基本没戏。。。。还得多多练习啊，为了那一次ACM比赛，值得！！