May 31
东华比赛总结 By Felix021 @ 70km??

首先批一下主办方。。。整个比赛过程都好挫,包括比赛的衣服、证书、没有队牌、不发餐券、让参赛选手站在赛场外面等、打印很麻烦、工作人员不太负责、发的点心是很挫的饼干而且还是比赛快结束了才发下来(以及水)、比赛结束后就散了,证书也不知道怎么着、题目非常囧。。。。。。(400米的报名费阿,相当相当地不值得)

然后批一下自己吧。。。整个比赛过程也好挫,纠结在一道最后才有一只队伍出的数学题目上,WA了5次最后还是没过。。。严重失误,嗯。

正式过程是这样的,首先是练习赛,A+B不说了,接下来一道很麻烦的模拟题,写了100多行的代码调了半天还没调对头就结束了- -|| 不过新版本的PC^2做的很不错阿,可以直接compile & run & test,题目也直接显示在侧边,用起来很方便。

12点开始正式比赛,10道题目,我看ABCD,jieyu看EFG,yihong看HIJ。A题是求生成树的数量,yihong和jieyu都看过那篇论文,但是忘了具体怎么做。B是一个SB题,看到有队伍AC了,马上写,提交,AC。C题是一个计算几何,给出一个圆的半径和三角形的三条边,求二者可能交叉的最大面积,这题只有6提交,0AC。D题是一个概率论的题目,数学盲飘过。。E题也很囧,给你一个n,要求用加减乘除最后能组合出多少种不同的算式,0提交。F题就是我们一直纠结的那道数学题了,因式分解(x^n-1),我和yihong想得非常深了,已经几乎完全确定没有问题了,但是最后还是WA了,非常无语。G题是一个简单的模拟,暴力一下就行了,jieyu写的,WA了一次很郁闷,我看了下他的代码,发现是边界条件写错了,改了两个地方,AC。H题比较像是线段树的题目,但是在具体实现上感觉又很困难,我写了一点写不下去了(其实根本就不该写,另一个失误),最后的rank显示这题是84提交0AC。I题是另一个数学题,要求[a,b]之间所有数字化成最小底数后的幂的和,数据量太大,没有想法。最后J题,算是计算几何吧:求钟表指针的重心从time1到time2经过的路程;这描述一看就觉得太TM复杂了,这是怎样一个弧线,算个毛阿。于是就一直没去想,但是3个小时左右的时候收到一个说明,每一秒内的运动按直线算----其实这样的话这提就比较简单了,最后AC率超过50%,不过当时一直在想F,所以没有去看那题,又一个大失误。

于是最后只出2题,Rank35,按照10%,20%,30%的比例,108支队伍,我们应该就是铜牌开始的那几个了,sigh。

总的来说这次比赛结果不太好,有两个原因:
1。偏题:题目都靠近计算几何、数学题,看不到经典的DP和图论,于是我们三个都挂了。
2。决策失误,以上详细说明了,很遗憾,否则我们至少应该能出3题。
May 29
前天在火车上想到的一点东西。

1。命令模式
定义一个抽象类(或者接口@Java)为所有类型的下落物件,包含一些方法诸如旋转,下落,左右移动等,使得具体的开发过程中只需要根据该抽象类编码,实现了解耦,也就可以更方便地添加各种类型的下落物件。

2。工厂模式
使用工厂模式来(随机地)生成下落物件,那么在主程序中就完全和具体的下落物件解耦了。

3。是否需要单件模式
如果说把容纳所有小方块的面板设计为一个class,那么它确实只能生成一个;但是似乎程序中不至于出现要实例化它两次的情况。
对于下落物件,在每次操作过程中确实只有一个,但是有些扩展设计可以显示出下一个下落物件,所以单件模式恐怕不好使。
是不是有一句话说,如果过度使用单件模式,那么程序就是有问题的?

4。一些其他的东西。
图形的实现。
我还是不喜欢用图形库,要去搞懂怎么用图形库显示一个东西,我实在没兴趣。
但是如果用字符实现的话,可能会因为刷屏导致很闪- -||
此外,怎么捕获控制台下的按键?这个一直没去研究过。。。虽然用tc很简单,但是程序写起来会很挫。。。
May 27
突然想写了,就写了一个。
因为调试需要,自己写了一个stack,继承vector实现(如果是继承自通用stack类的话那就是个类适配器了哦^_^)

代码如下:
May 27
话说今晚用visio 2007画张图,看那两本书看得我是死去活来啊(就是说半途睡着了一次)
一本是《深入理解Linux内核》,一本是《深入理解Linux虚拟内存管理》,书名都差不多,内容也差不多郁闷。

最后理出来这些东西凑进了图里:
init_tast, double circular linked list, process descriptor, mm_struct, pgd, pt, page ...

点击在新窗口中浏览此图片
May 25
前些天在《Head First设计模式》上看到了这一原则。
书上的例子非常好,鸭子的飞行行为和嘎嘎叫的行为确实可以从父类继承得到
但是如果出现橡皮鸭子,它不会叫也不会飞,如果要把它归类为鸭子,那么代码就有得写了(更详细内容参见该书)。

今天突然想起另外一个问题,某天看到一句话:Java采用接口,避免了多继承带来的问题。
于是去Google了一下多继承存在的问题,然后就发现,除了继承带来的冗余数据和方法之外,另一个大问题就是钻石问题。
@ 2009-05-26 下面举的例子有点问题,详情参见篇后sandy的评论
话说端午节快到了,该是吃粽子的时候了——
我们知道米饭和豆沙都是(继承)食品,然后我们用米饭包住豆沙放在锅里蒸一下,我们就得到了(派生)粽子。
这样的结构是:
    食品
    /     \
米饭   豆沙
    \     /
     粽子
这是一个菱形,于是被成为钻石问题:如果食品里有一个成员 "好吃程度",那么粽子的"好吃程度"是继承自哪一个呢?
在C++这个支持多继承的语言里面,如果直接使用
粽子 粽子a;
cout << 粽子a.好吃程度 << endl;

然后就会发现编译器(g++)报错:对成员"好吃程度"的请求有歧义(ambiguous)。
不过好在有3个解决方式:
1。重新定义一个好吃程度覆盖米饭和豆沙的好吃程度。
2。指明是哪个父类的好吃程度:例如  粽子a.米饭::好吃程度  或者  粽子a.豆沙::好吃程度
3。使用虚拟继承(虚基类),详情请STFW。

于是我突然想到其实这里如果使用"多用组合,少用继承"的设计原则(很像解决方法2),那么问题就解决拉:
class 粽子: public 食品{
private:
    米饭 米饭a;
    豆沙 豆沙a;
public:
    粽子(){
        好吃程度 = (米饭a.好吃程度 + 豆沙a.好吃程度) / 2; //其实我觉得豆沙a的权值应该大些=.=
    }
};

当然这只是一个很初步的想法,代码也非常不严谨,谨以此抛砖引玉,欢迎交流。
May 25

用gcc/g++编译winsock程序 不指定

felix021 @ 2009-5-25 02:12 [IT » 网络] 评论(5) , 引用(0) , 阅读(10742) | Via 本站原创
开始学习winsock(应付网络程序设计的大作业)
在网上搜"winsock 入门",然后都是一堆很ooxx的东西,反正你看了就是不知道怎么写程序就是了。

试着写下一些代码,却发现出现一堆类似
引用
undefined reference to `socket@12'
undefined reference to `htons@4'
这样的错误。

Google了一下,众说纷纭啊,有说extern "C"的,有说少lib路径的
最后在CSDN的论坛上发现有个人遇到这个问题,贴了个程序,后面别人给的建议有效了:
#include<iostream>
#include<windows.h>
#include<winsock.h>
using namespace std;

int main()   {
    WSADATA wsaData;
    WSAStartup(MAKEWORD(1,1),&wsaData);
    cout<<"hello"<<endl;
    int sockfd = socket(AF_INET, SOCK_STREAM, 0);
    sockaddr_in host;
    int port = htons(8080);
}

编译:
C:\code\> g++ a.cpp -lwsock32
加上libwsock32的库即可。。。汗。
May 25

国软比赛总结 不指定

felix021 @ 2009-5-25 01:58 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(5938) | Via 本站原创
很纠结地最后可以参加这个比赛了,但是这个比赛只能两个人参加,于是BFS只能拆散了。
Sandy和Boluor组队,然后我另外去找了Eire组成新队,队名70km  :D

12点左右就到了机房,结果LCY说对外通知是12:30入场>_<|| 郁闷。
然后随便找一台机器测试了一会儿,到大约12点40的时候被安排坐到team30的位置(可是我们是team51=.=)
花了一点时间把vimrc先大致敲了一点进去,和eire讲了一点vim的基本操作,敲了一个model.cpp

1点多一点点开始比赛,8道题目,可是国软这次这么小气,两个人才一份题目,orz。
于是把题目拆开,Felix负责ABCD,Eire负责EFGH。
还好是中文,看完比较快,Eire说后面四道题目貌似没有直接可以写的
然后我看到B是一个简单的BFS,C是一个更简单的模拟水题
于是直接上去敲C,结果很快就WA了,检查了一下,发现一个小错误,Submit,又WA,超郁闷。

打印代码一边检查,然后Eire看H题,我和他讨论了一下,刚开始想到记忆化搜索
但是发现不对,没有高精肯定要溢出,高精效率又太低。
于是列出一个不太严谨的式子:如果把n拆成x份,那么最后的结果是x^(n/x)(忽略小数)
然后大致证明了3是最划算的(我居然忘了怎么求导T_T 还好Eire还记得。。。)
然后又大致觉得如果是4就应该拆成2 * 2
于是顺着这个不严格证明得出的思路写代码。

其间Felix改了一下C题,又WA,检查代码发现多了一个测试的printf T_T,注释,提交,AC@35min
一个简单的C题被我搞出3个WA。。。罪人啊。。。。

很快Eire根据那个"证明"结果写出了代码,提交,1AC@42。振奋。

然后Felix看B题的BFS应该很简单,虽然Eire有点担心,但是还是毅然决然地开题
写完以后测试发现不太对,打印代码一边晾去,由Eire开始写他想得已经差不多的G题
其间Eire又转去细想,而Felix在打印的代码上面发现了几处错误
改正以后样例基本OK了,然后是最后一个不对
自己看了一下样例,发现是样例错了,于是问judge。
结果被告知出题人kid正在地大回途中,waiting。。。

于是Eire继续G题,由于roman 2 arabic的函数写得很好,然后用一个struct+stable_sort,1AC@114min
这个时候开始网络变得非常垃圾,点一个Refresh就能把PC^2卡死,超郁闷。

还好等了不是太久kid回来了,原来是他把6写成5了,不好改题目,于是就把数据改了。
然后提交之,发现TLE了,超囧。
检查了一下,发现在BFS的循环里面有错,队尾指针在某个情况下不会改变(以前没遇到过),于是很囧地进入死循环TLE
修改了以后检查了一遍,又发现一些其他的错误,一并改之,提交,WA@130+min T_T
很郁闷很郁闷地继续检查,大概160min发现原来是存名字的map在每一个case之前没有clear,超囧。
又提交一次,还是WA!郁闷啊郁闷啊郁闷。
纠结了很久,大概30min以后问了maner是不是最后一个case后面不需要再加\n
maner说,大概是。。。于是改之,提交,终于AC@196min...

剩下的四道题目和Eire讨论了一下:
A题是一个枚举+二维DP的问题,Felix能想出这个框架,但是实在是不会写DP,无奈放弃
D题状似计算几何,但是细看其实不然。Felix也想出了应用容斥原理的算法基本框架,就是不会写T_T
E题可见边——Eire很后悔地说没有带上图形学的书。。。
F题奇怪的比赛——完全没有思路,嗯。

此时70km@Rank2,仅次于momo+feli。
但是后面好几个队伍都出了3题甚至4题,估计很快就能超过我们,郁闷
更郁闷的是LCY同志宣布:由于比赛过程中网络状况比较差,比赛延长半个小时
于是我深情地拉着LCY的手说:我恨你T_T

由于最后一个半小时都没有题目可以做,于是Eire在5点多一些就先跑路了
Felix非常无聊地水了一下D题,毫无意外地TLE,于是也不再继续写了。。。。

——

最后非常意外地70km还是留在Rank2的位置。究其原因,主要有这么几点:

首先,因为从地大回来的队伍不仅推迟一个小时才开始做题,而且都太累了——毕竟写了一天的代码啊,此乃侥幸。

其次,做题策略把握得比较好——
  a) 看题,我们把所有的题目都快速扫过去,没有一看到简单的就急于做出来,
      因此在整个比赛的过程中基本上是按照从简单到难的顺序做出来,这个还是比较划算的
  b) 比赛的过程中时间安排得好。一旦觉得自己会陷入僵局的时候就打印代码换人写
      事实上确实是,在纸上看代码很容易找到代码的错误,并且往往一次能找出不止个一并改好
  c) 把自己的想法适当地和队友讨论,这样能让自己明确自己的思路,找到自己可能存在的问题,
      同时如果自己存在问题,也可以借助队友的局外人身份找出(旁观者清啊!)

再次,河蟹的队伍气氛也很重要。整个比赛过程中非常开心,无论是卡题还是AC还是WA还是TLE(其实后两个结果都是Felix的贡献T_T),都可以笑得很happy,一点沉重的气氛都没有,我觉得这对队伍比赛时的状态有非常积极的作用,让我想起的去年暑假集训的Matrix76队,气氛一向都是非常河蟹。

此外,发现自己的基础还有很大一部分不扎实,主要体现在:
1. 简单的DP不会写.....
2. 容斥原理不会写.....
3. 算法流程没有完全想清楚就开始码字.....
4. 一个BFS能写出好几个错误,边写编改.....
5. 居然能挂在初始化上面,无语啊无语啊无语。。。

以上,OVER,特别感谢队友Eire同学,嗯。
May 24

软考,RP之。 不指定

felix021 @ 2009-5-24 00:36 [IT » 其他] 评论(1) , 引用(0) , 阅读(6326) | Via 本站原创
虽然在报名截止之前匆匆交了120,还花了50多买了一本教程,但是后来一直没有抽时间好好复习,以至于说过n次不想考了。
昨晚在看了半晚上《李彦宏的百度世界》以后,终于毅然决然地捧起了《软件设计师教程》——毕竟花了50多,不看完太浪费了。
于是花了大概三四个小时翻完了。
然后打开玉哥发到班群邮件里面的那个历年试题.chm,看了2006年5月的题目(因为有答案),3点,睡觉

早上7点30撑起眼皮爬起床,8点20在华师门口和璐希、佳璐汇合,然后佳璐带路到9301去。好困。
8点45左右入场,9点开考。
监考的似乎相当业余,不检查是否有枪手,发卷子和答题卡也很随意,导致我差点被忽略掉。。
题目其实都蛮简单,大约1个小时多一点做完,涂答题卡,检查是否涂错,然后大概点了一下
大概有十几题是不确定是否能作对的,大概有50~55题是比较有把握的,因此估分是55~60。
p.s. 总共75题,每题1分,据说一般45就算过。
交卷,10:15。
监考人问:草稿纸呢?
答:你们有发么?
监考人:...

10:30回到宿舍,然后打开那个chm,把05年下半年的下午题也看了一遍。
12点出去吃个午饭,回来睡午觉。1点07被电话吵醒,郁闷。继续眯,1点20起床。然后走到考场。

下午的题目更简单了。
前三题是DFD,数据库,UML,虽然对UML不熟,但是瞎蒙总能蒙不少分数的。
第四题是伪代码描述FLOYD的填空,超简单。
第5,6,7分别是C/C++/JAVA的填空,三选一。
第5题是用C写的二叉树非递归中序遍历,很简单,直接做了。
检查一遍,交卷,15:00。
估摸着应该也是在55~60分把。
p.s. 总共答出5题,每题15分,一般也是45算过。

看来软考是混过去了。
回想一下觉得其实考题不难,大部分都是平时课程的内容,综合到一块而已。
分页: 46/103 第一页 上页 41 42 43 44 45 46 47 48 49 50 下页 最后页 [ 显示模式: 摘要 | 列表 ]