| WXYZ 的个人资料WXYZ的异人馆照片日志列表 |  工具  帮助 |
|
2月27日 大二下学期开学 一开学，马上就觉得忙起来。这次感觉明显不同的是，很多事都要分组。开学才两天，我就在三个不同的组里面。一个英语小组，4个人，都同班的，但就不怎么熟了。毛邓三还得分个组做研究，竟然二十个人一个组，觉得太多人了，真的好多，我都不知道中间应该怎样分配人手和协调了。
还有个组队，这个就重要了。三人小队，参加ZSUCPC。先杀预选，预选相信绝对没问题，肯定能入围省赛了。省赛就是个大考验了，因为我希望能在省赛中得到前8，直接进入4+2，不要途经补选阶段了。贴个时间表备忘一下：
3月17日～3月19日（星期一~星期三）
接受报名，采用网上报名的方式
报名网址为：http://202.116.77.69/zsucpc2008/（反正网址你们进不去，哈哈）
暂定接受130支队报名 3月30日 星期日
13:00-17:00 ZSUCPC’2008预选赛
5月2日 星期五
13:00-14:00 竞赛准备会
14:30-16:30 试机（试机过程中进行报到、注册等工作）
5月3日 星期六
10:00-15:00 GDCPC’2008 & ZSUCPC’2008
17:30-18:30 闭幕式暨颁奖大会
5月31日 星期六
13:00-17:00 中山大学2008年集训队第二轮选拔赛（补选赛）（这个最好可以不用参加了）
努力往上杀吧，这就是个机会。现在正处于准备阶段，我们队还没有个队名，也没有正式在一起体会下同队的感觉，配合是很重要的。不知道赛前是否还有个练习赛的，如果有的话就好了。准备阶段要准备什么，我自己也不知道，虽然说去年参加过了，但是当时是临时组的队，在报名截止的最后一天报的名，什么准备也没有。还记得当时到预选赛赛场，我们队只有支笔，有个打稿簿，有本《面向对象程序设计》，也就是当时的C++课本，没有其它了。在那里发现第一样缺乏的东西是英汉字典，平时做题遇到的不懂的单词直接用百度查，到场才记得上不了百度。幸好坐在我们旁边的三个师姐（她们组当时好疯狂，比赛过了4题，起码我当时没听过这么强的女组，后来好像还查到了她们其中一个人的blog，描述的比赛场景就是我们的旁边的真实场景，现在把网址忘了）热心的借我们字典，才得以度过题意关，最后才终于过了两题。所以，这次第一要准备的，应该是英汉词典，虽然现在发现很多时候就算不懂某些单词，反正看懂大意和Input和Output，再参照下样例，照样过题，但是为了确保万无一失，还是带上吧。然后准备的应该是，各种模版。我还不得不同意，模版还是重要的，一个好的模版在比赛中可以省下不少时间，并且不容易出错，从准度和速度上都得到提高，何乐而不为呢？其它准备事项暂时没想到，还得经过小组讨论吧。
那么为了在这方面多花时间，那么在正课的学习过程中，就得大幅度提高效率了，何况这个学期的课还明显从数量和难度上都增加了。这样的话就是充分利用好每节课的上课时间了，力争在上课时把应该做的都做了，课后除了作业外就不用再特意去补了。而其它的分组，看着办吧，反正死不了人，反正我也能相信自己。
而除了以上这些，出去玩应该基本上是没有时间了。以前一直坚持的，总是去华师本校区吃饭的行动，可能无法继续执行或者减少执行了，毕竟要有所放弃才能在另一些方面有收获。平时或者个几月去打个Q这样的活动，应该还是可以的。至于五月，应该几天的时间还是有的吧。
最后，祝自己在这个学期变得更加好吧，也祝我们队能直接杀入4+2吧。 2月22日 PKU2452 -- Sticks Problem 第一次写解题报告，这题有幸了，PKU2452 -- Sticks Problem。并不是因为这题有多难，而是觉得这题有趣，并且这几天心情有点不好，总是想写点什么缓解下情绪，但描写自己的心情对于我来说太难以完成了，就转而写解报告。
这题大概意思是给出一列两两互不相同的正数，求出这数列中的两个数Si和Sj，且Si<Sj，i<j，使得这两个数之间的所以数，即Sk，i<k<j，都有Si<Sk<Sj，使得j-i最大。
一看到这题，最大5万数据量，6秒时间，这个就有点吓人了，不会有什么恐怖的做法吧。首先，我想到的是一次扫描，在扫描过程中，用一变量a保存小数，即Si，用b保存大数，即Sj，当遇到一个数比b大时，就算出此时位置与a的距离；若比a小，则令a等于此数，并且b置0。这样的方法来求出最大距离。很快就写出来这样一个程序，试试样例，也并无问题，就快快提交上去。结果返回一个Wrong Answer，这也并非意想不到，果然一个时限6秒的题并不是随便200个字节就能水过的。后来发现，对于1，5，2，3，4这组数据，按照我这种做法出来的结果是1，而正确答案应该是一看就知道的2，也就是说我错了。
只好另想办法吧。从本来的想法开始，发现出现错误的原因是后来的2因为介于1和5之间而没有保存下来，而忽略了2，3，4这段，假若把这数列分成两段，1，5是其中一段，2，3，4是其中一段，这就能得出结果了。有什么好方法呢？我想到用数组保存其中一段为最小值1，最大值5，的数列，而另一个为最小值2，最大值4的段，这样就能解决了。就是说当读到一个数时，判断下这个数是否比当前所记录的段中的最大值要大，是的话，就会形成一个新的更长的段，如果不是，则另开新段，把这个数记为最小值，最大值设为和最小值相等，这样就肯定对的。
现在问题算是初步解决了。但是还有个严重的问题，就是时限，如果每读入一个数，都与每个记录段作比较的话，这样会达到O(n^2)的，对于这题规模绝对过不了。这样就开始着手想优化。利用上面的例子，记录一段为{1，5}，另一段为{2，4}，联想下是不是可以像最长上升子序列那样用二分把复杂度降为O(nlogn)呢？假设现在读到一个6，则可以把{1，5}段扩长为{1，6}，{2，4}段也扩长为{2，6}，但2出现在1后，所以{1，6}段肯定比{2，6}段长，而{2，6}段也没必要保留，因为如果读到在{2，6}段中间的数，中间因为出现一个6，对于条件不成立；若读到大于6的数，则可以扩展{2，6}段时{1，6}段同样可以扩展。而当只读了1，5时，存在段{1，5}后，若读到一个3，需要另开新段{3，3}，此时若读到6，则依上扩展成段{1，6}，并舍弃{3，3}段；若读到一个4，则{1，5}段不可扩展，只能把{3，3}段扩成{3，4}段；若读到一个2，则需要另开新段{2，2}，同时由于{3，3}段后面出现了比最小值更小的数，这段不再保留，只剩下{1，5}和{2，2}。通过简单的例子，大概可以看出保存的最小值是递增的，而保存的最大值是递减的，同时由于当修改某段后，此段以外的段不用修改，因此可以保持很好的性质，可以用二分完成，每输入一个数，先查找最大值，若小于所有的最大值，则需要添加新段，再来查找最小值。这样就可以成功地求出最长距离的满足题目要求的段了。
写好代码，其实也不长，就1k左右，提交上去，果然获得一个Accepted，216ms，这都让我忘了这题时限为6s了。看看discuss，有人说暴力也可过，可能是数据比较弱吧。如果说这是一个水题，则我不算是水过的吧，毕竟都是有所收获的，起码对利用二分的方法更深了一步。
写解题报告报还是很过瘾的，以后有时间再写写吧。 2月6日 祝贺一下 发现很久没写了，差不多有个月了，原因很简单，肚里没墨了，吐不出来了。不过，高兴的事总是有的，又差不多新年了，我又总报喜不报忧，虽然忧的也很多，例如天气之类的啦，不过都没关系。
首先是新年快乐，新年每年都差不多，反而我想新年安静点，不要搞太多花哨的东西，好累的其实，在家过个好年就够了。
然后，对于上学期的期末考试，本来没多大把握的。现在上网查查吧，结果出乎意料。出来了几样，抛开那个存在主义不说，图论竟然是满分，绝对的出乎我意料，怎么总得犯得错误吧，结果还是满分……还是同样吃惊的是物理，居然还有个96，竟然还是个全班第一，想不通啊想不通，平时课堂回答得不算好吧，好几次都是口哑哑的，考试之前还在玩苍之涛，总计物理复习时间就4个小时吧，居然可以吓死我。算了，反正是好事。
还有一件，秘密。实现完成再说吧。 |
|
|
