SGU阶段总结(10题)

  SGU600+的前10个题(114-163之间)。   虽然已经是600+,但这10个题仍然以水题为主,总的来说,1AC率有所上升(1000+的16个题只有2个1AC的),但有的题目上犯的错误远远超过1000+的16个题。   所犯严重错误:124看错题意,133两次看错题意。   编码速度仍然有待提高,昨天看到一个说他2分钟写过了一个水题,实在汗颜,我现在2分钟内连输入输出都写不完。但速度应该以质量为基础,所以仍然要以提高编码质量为主。   对算法的掌握仍然没有恢复到NOI之前的水平,以至出现多重背包写了错误的贪心法,判断点与多边形的关系需要临时查书的窘境。

SGU 163 程序

  ACM ICPC 2002-2003 NEERC, Northern Subregion,居然考这种题…… //AC #include using namespace std; inline long power(const long a,const long b) { long t=1; for (long i(0);i>n>>p; for (long i(0);i>a; t=power(a,p); if (t>0) c+=t; } cout

关于编译器合成的构造函数

  昨天做SGU134时遇到了类类型对象没有被初始化的问题,于是引起对编译器合成的默认构造函数的猜测,后来在瀚海星云得到解答如下: 发信人: windywinter(WindyWinter), 信区: CPlusPlus 标 题: 问一个有关默认构造函数的问题 发信站: 瀚海星云 (2007年04月02日18:47:12 星期一), 站内信件 WWWPOST 有如下类: struct vertex { bool visited; long assonum,noc; edge *link; //edge is anthor class }; 那么编译器会合成什么样的构造函数? 与 vertex():visited(0),assonum(0),noc(0),link(0){}; 有区别吗? 我实验了 int main() { vertex vertexes[10000]; return 0; } MS让编译器自己合成构造函数的话,vertexes是没有经过初始化的,而自己写构造函数 则正常初始化。 — My Blog: http://turingdream.com ※ 来源:·瀚海星云 bbs.ustc.edu.cn·[FROM: 221.238.147.227] 发信人: jlw(STILL FANTASY), […]

SGU 154 解题手记

  这题与已经离我们而去的TJU上的一个题很像,那是要求N!末尾有多少个0,答案就是$$\frac{N}{5}+\frac{N}{5^2}+\frac{N}{5^3}+\dots $$。如果把N!拆成质因数相乘,只有2*5才会出现0,而2的个数远多于5,所以只要统计N以下的数中质因数5的总数就可以了。   而这个题目,就变成了解$$\frac{N}{5}+\frac{N}{5^2}+\frac{N}{5^3}+\dots=Q$$。   解法1:二分枚举N。N不会超过5*10^8,虽然比较大,但仍然可以接受。另外,N肯定是5的倍数,这就不用解释了。   解法2:已知$$5^{k_1}! $$末尾有$$q_1$$个0,$$5^{k_2}! $$末尾有$$q_2$$个0,证明$$(5^{k_{1}}+5^{k_{2}})! $$的末尾有$$q_1+q_2$$个0。   $$[\frac{{5^{k_{1}}+5^{k_{1}}}}{5}] +[\frac{{5^{k_{1}}+5^{k_{1}}}}{25}]+\dots =[\frac{5^{k_{1}}}{5}] +[\frac{5^{k_{1}}}{25}]+\dots+[\frac{5^{k_{2}}}{5}] +[\frac{5^{k_{2}}}{25}]+\dots=q_1+q_2$$,得证。   设$$k_1 \ge k_2 \ge k_3 \ge k_4 \ge \dots \ge k_p$$,且不存在$$k_i=k_{i+1}=k_{i+2}=k_{i+3}=k_{i+4}$$,将N写成$$5^{k_{1}}+5^{k_{2}}+5^{k_{3}}+\dots$$的形式,则N!末尾0的个数为$$\frac{5^{k_{1}}-1}{4}+\frac{5^{k_{2}}-1}{4}+\frac{5^{k_{2}}-1}{4}+\dots$$。   可以逐个将k解出。之所以要求不能有5个一样的k,是因为如果有5个一样的k,就不能套用上面的那个等式了(去掉[]再加上[]的时候会出现不等)。如果某个Q导致出现了5个一样的k,那就是无解的。   Submit 1: WA on 3。不知道怎么错的,看不出来。晕……题目认为当Q=0时N=1而不是N=0。   Submit 2: WA on 1。特殊判断写错地方了……   Submit 3: AC。 //AC #include using namespace std; const long power5[13]={1,5,25,125,625,3125,15625,78125,390625,1953125,9765625,48828125,244140625}; int main() { long n(0),q,c(1),k(12); bool same; cin>>q; if […]

SGU 152 解题手记

  题目要求是:向上取整向下取整都可以,自拟。所以这题不会有No Solution的。但注意别把百分比是整数的也“取整”。求百分比不要用实数,用整数做。   Submit 1: AC。 //AC #include using namespace std; int main() { bool round[10000]={0}; long per[10000]={0}; long n,c(100),z(0); scanf(“%ld”,&n); for (int i(0);i

SGU 144 解题手记

SGU144 解题手记
  题意:两个人决定在某个时间段内碰面(X点-Y点),他们没有确定准确的时间,只说一个人先到后,最多等另一个人Z分钟,现在求他们可以碰面的概率。
  这种问题matrix67曾有过专题讲解。方法…

SGU 134 解题后记

  这题有人归为树型DP,我看不像,至少没有决策枚举的过程,完全是个“树型递推”。稀疏图用邻接表存,然后DFS一下就变成树了。   Submit 1: WA on 1。实在没找到什么地方错了。   (重装系统时不小心把这题的解题手记和程序弄丢了,只好重写,以上内容是根据回忆写的,不保证准确)   Submit 2: RTE on 13。重写程序后,第一个点直接过了,因没有以前的程序,查不出为什么那个程序WA on 1了。但RTE也够奇怪的,查了一遍程序,没有发现有数组越界或者指针指向非法地址的问题。生成大数据测试。发现在n>15000时出现了RTE,而且是指针指向非法地址!一句一句的查发现,如下写法:(main()中) vertex vertexes[16000]; 数组的有些成员没有初始化!怀疑根本没有调用构造函数。   Submit 3: AC。   接受滕老师意见,仔细查为什么没有调用构造函数。当我自己写构造函数,而不让编译器合成时,没有出现对象没有初始化的现象。这就怪了,难道合成的构造函数与我写的构造函数有什么区别吗? //AC #include #include using namespace std; struct vertex; struct edge { vertex *u; edge *next; }; struct vertex { bool visited; long assonum,noc; edge *link; vertex():visited(0),assonum(0),noc(0),link(0){}; }; long n; edge *rc; void dfs(vertex *v) […]

计算机科学与技术学习反思录

************************************************************ * 转载自 http://blog.csdn.net/dreamingk/ * 原文地址 http://www.frontfree.net/view/article_746.html * 虽然本文涉嫌抄袭,但文章见解深刻,值得一看 ************************************************************ 计算机科学与技术学习反思录 北京工业大学 曾毅   计算机科学与技术这一门科学深深的吸引着我们这些同学们,上计算机系已经有近三年了,自己也做了一些思考,我一直认为计算机科学与技术这门专业,在本科阶段是不可能切分成计算机科学和计算机技术的,因为计算机科学需要相当多的实践,而实践需要技术;每一个人(包括非计算机专业),掌握简单的计算机技术都很容易(包括程序设计),但计算机专业的优势就在于,我们掌握许多其他专业并不“深究”的东西,例如,算法,体系结构,等等。非计算机专业的人可以很容易地做一个芯片,写一段程序,但他们做不出计算机专业能够做出来的大型系统。(与司徒彦南兄的谈话)今天我想专门谈一谈计算机科学,并将重点放在计算理论上。 计算机理论的一个核心问题——从数学谈起:   记得当年大一入学,每周六课时高等数学,天天作业不断(那时是六日工作制)。颇有些同学惊呼走错了门:咱们这到底念的是什么系?不错,你没走错门,这就是计算机科学与技术系。我国计算机科学系里的传统是培养做学术研究,尤其是理论研究的人(方向不见得有问题,但是做得不是那么尽如人意)。而计算机的理论研究,说到底了,如网络安全,图形图像学,视频音频处理,哪个方向都与数学有着很大的关系,虽然也许是正统数学家眼里非主流的数学。这里我还想阐明我的一个观点:我们都知道,数学是从实际生活当中抽象出来的理论,人们之所以要将实际抽象成理论,目的就在于想用抽象出来的理论去更好的指导实践,有些数学研究工作者喜欢用一些现存的理论知识去推导若干条推论,殊不知其一:问题考虑不全很可能是个错误的推论,其二:他的推论在现实生活中找不到原型,不能指导实践。严格的说,我并不是一个理想主义者,政治课上学的理论联系实际一直是指导我学习科学文化知识的航标(至少我认为搞计算机科学与技术的应当本着这个方向)。   其实我们计算机系学数学光学高等数学是不够的(典型的工科院校一般都开的是高等数学),我们应该像数学系一样学一下数学分析(清华计算机系开的好像就是数学分析),数学分析这门科学,咱们学计算机的人对它有很复杂的感情。在于它是偏向于证明型的数学课程,这对我们培养良好的分析能力极有帮助。我的软件工程学导师北工大数理学院的王仪华先生就曾经教导过我们,数学系的学生到软件企业中大多作软件设计与分析工作,而计算机系的学生做程序员的居多,原因就在于数学系的学生分析推理能力,从所受训练的角度上要远远在我们之上。当年出现的怪现象是:计算机系学生的高中数学基础在全校数一数二(希望没有冒犯其它系的同学),教学课时数也仅次于数学系,但学完之后的效果却不尽如人意。难道都是学生不努力吗,我看未见得,方向错了也说不一定,其中原因何在,发人深思。   我个人的浅见是:计算机系的学生,对数学的要求固然跟数学系不同,跟物理类差别则更大。通常非数学专业的所谓“高等数学”,无非是把数学分析中较困难的理论部分删去,强调套用公式计算而已。而对计算机系来说,数学分析里用处最大的恰恰是被删去的理论部分。说得难听一点,对计算机系学生而言,追求算来算去的所谓“工程数学”已经彻底地走进了误区。记上一堆曲面积分的公式,难道就能算懂了数学?那倒不如现用现查,何必费事记呢?再不然直接用Mathematics或是Matalab好了。   我在系里最爱做的事情就是给学弟学妹们推荐参考书。中文的数学分析书,一般都认为以北大张筑生老师的《数学分析新讲》为最好。万一你的数学实在太好,那就去看菲赫金哥尔茨的《微积分学教程》好了–但我认为没什么必要,毕竟你不想转到数学系去。吉米多维奇的《数学分析习题集》也基本上是计算型的东东。书的名气很大,倒不见得适合我们,还是那句话,重要的是数学思想的建立,生活在信息社会里我们求的是高效,计算这玩意还是留给计算机吧。不过现在多用的似乎是复旦大学的《数学分析》也是很好的教材。   中国的所谓高等代数,就等于线性代数加上一点多项式理论。我以为这有好的一面,因为可以让学生较早感觉到代数是一种结构,而非一堆矩阵翻来覆去。这里不得不提南京大学林成森、盛松柏两位老师编的《高等代数》,感觉相当舒服。此书相当全面地包含了关于多项式和线性代数的基本初等结果,同时还提供了一些有用的又比较深刻的内容,如Sturm序列,Shermon-Morrison公式,广义逆矩阵等等。可以说,作为本科生如能吃透此书,就可以算高手。国内较好的高等代数教材还有清华计算机系用的那本,清华出版社出版,书店里多多,一看就知道。从抽象代数的观点来看,高等代数里的结果不过是代数系统性质的一些例子而已。莫宗坚先生的《代数学》里,对此进行了深刻的讨论。然而莫先生的书实在深得很,作为本科生恐怕难以接受,不妨等到自己以后成熟了一些再读。   正如上面所论述的,计算机系的学生学习高等数学:知其然更要知其所以然。你学习的目的应该是:将抽象的理论再应用于实践,不但要掌握题目的解题方法,更要掌握解题思想,对于定理的学习:不是简单的应用,而是掌握证明过程即掌握定理的由来,训练自己的推理能力。只有这样才达到了学习这门科学的目的,同时也缩小了我们与数学系的同学之间思维上的差距。   概率论与数理统计这门课很重要,可惜大多数院校讲授这门课都会少些东西。少了的东西现在看至少有随机过程。到毕业还没有听说过Markov过程,此乃计算机系学生的耻辱。没有随机过程,你怎么分析网络和分布式系统?怎么设计随机化算法和协议?据说清华计算机系开有“随机数学”,早就是必修课。另外,离散概率论对计算机系学生来说有特殊的重要性。而我们国家工程数学讲的都是连续概率。现在,美国已经有些学校开设了单纯的“离散概率论”课程,干脆把连续概率删去,把离散概率讲深些。我们不一定要这么做,但应该更加强调离散概率是没有疑问的。这个工作我看还是尽早的做为好。   计算方法学(有些学校也称为数学分析学)是最后一门由数理学院给我们开的课。一般学生对这门课的重视程度有限,以为没什么用。不就是照套公式嘛!其实,做图形图像可离不开它,密码学搞深了也离不开它。而且,在很多科学工程中的应用计算,都以数值的为主。这门课有两个极端的讲法:一个是古典的“数值分析”,完全讲数学原理和算法;另一个是现在日趋流行的“科学与工程计算”,干脆教学生用软件包编程。我个人认为,计算机系的学生一定要认识清楚我们计算机系的学生为什么要学这门课,我是很偏向于学好理论后用计算机实现的,最好使用C语言或C++编程实现。向这个方向努力的书籍还是挺多的,这里推荐大家高等教育出版社(CHEP)和施普林格出版社(Springer)联合出版的《计算方法》(Computational Methods),华中理工大学数学系写的(现华中科技大学),这方面华科大做的工作在国内应算是比较多的,而个人认为以这本最好,至少程序设计方面涉及了:任意数学函数的求值,方程求根,线性方程组求解,插值方法,数值积分,场微分方程数值求解。李庆扬的那本则理论性过强,与实际应用结合得不太紧。   每个学校本系里都会开一门离散数学,涉及集合论,图论,和抽象代数,数理逻辑。不过,这么多内容挤在离散数学一门课里,是否时间太紧了点?另外,计算机系学生不懂组合和数论,也是巨大的缺陷。要做理论,不懂组合或者数论吃亏可就太大了。从理想的状态来看,最好分开六门课:集合,逻辑,图论,组合,代数,数论。这个当然不现实,因为没那么多课时。也许将来可以开三门课:集合与逻辑,图论与组合,代数与数论。(这方面我们学校已经着手开始做了。)不管课怎么开,学生总一样要学。下面分别谈谈上面的三组内容。   古典集合论,北师大出过一本《基础集合论》不错。   数理逻辑,中科院软件所陆钟万教授的《面向计算机科学的数理逻辑》就不错。现在可以找到陆钟万教授的讲课录像,http://www.cas.ac.cn/html/Dir/2001/11/06/3391.htm自己去看看吧。总的来说,学集合/逻辑起手不难,普通高中生都能看懂。但越往后越感觉深不可测。   学完以上各书之后,如果你还有精力兴趣进一步深究,那么可以试一下GTM系列中的"Introduction to Axiomatic Set Theory"和"A Course of Mathematical Logic"。这两本都有世界图书出版社的引进版。你如果能搞定这两本,可以说在逻辑方面真正入了门,也就不用再浪费时间听我瞎侃了。   据说全中国最多只有三十个人懂图论。此言不虚。图论这东东,技巧性太强,几乎每个问题都有一个独特的方法,让人头痛。不过这也正是它魅力所在:只要你有创造性,它就能给你成就感。我的导师说,图论里面随便揪一块东西就可以写篇论文。大家可以体会里面内容之深广了吧!国内的图论书中,王树禾老师的《图论及其算法》非常成功。一方面,其内容在国内教材里算非常全面的。另一方面,其对算法的强调非常适合计算机系(本来就是科大计算机系教材)。有了这本书为主,再参考几本翻译的,如Bondy & Murty的《图论及其应用》,人民邮电出版社翻译的《图论和电路网络》等等,就马马虎虎,对本科生足够了。再进一步,世界图书引进有GTM系列的"Modern Graph Theory"。此书确实经典!国内好象还有一家出版了个翻译版。不过,学到这个层次,还是读原版好。搞定这本书,也标志着图论入了门。   离散数学方面我们北京工业大学实验学院有个世界级的专家,叫邵学才,复旦大学概率论毕业的,教过高等数学,线性代数,概率论,最后转向离散数学,出版著作无数,论文集新加坡有一本,堪称经典,大家想学离散数学的真谛不妨找来看看。这老师的课我专门去听过,极为经典。不过你要从他的不经意的话中去挖掘精髓。在同他的交谈当中我又深刻地发现一个问题,虽说邵先生写书无数,但依他自己的说法每本都差不多,我实在觉得诧异,他说主要是有大纲的限制,不便多写。这就难怪了,很少听说国外写书还要依据个什么大纲(就算有,内容也宽泛的多),不敢越雷池半步,这样不是看谁的都一样了。外版的书好就好在这里,最新的科技成果里面都有论述,别的先不说,至少是“紧跟时代的理论知识”。   组合感觉没有太适合的国产书。还是读Graham和Knuth等人合著的经典《具体数学》吧,西安电子科技大学出版社有翻译版。   抽象代数,国内经典为莫宗坚先生的“代数学”。此书是北大数学系教材,深得好评。然而对本科生来说,此书未免太深。可以先学习一些其它的教材,然后再回头来看“代数学”。国际上的经典可就多了,GTM系列里就有一大堆。推荐一本谈不上经典,但却最简单的,最容易学的:http://www.math.miami.edu/~ec/book/这本"Introduction to Linear and Abstract Algebra"非常通俗易懂,而且把抽象代数和线性代数结合起来,对初学者来说非常理想,我校比较牛的同学都有收藏。   数论方面,国内有经典而且以困难著称的《初等数论》(潘氏兄弟著,北大版)。再追溯一点,还有更加经典(可以算世界级)并且更加困难的《数论导引》(华罗庚先生的名著,科学版,九章书店重印,繁体的,看起来可能比较困难)。把基础的几章搞定一个大概,对本科生来讲足够了。但这只是初等数论。本科毕业后要学计算数论,你必须看英文的书,如Bach的"Introduction to Algorithmic Number Theory"。   计算机科学理论的根本,在于算法。现在很多系里给本科生开设算法设计与分析,确实非常正确。环顾西方世界,大约没有一个三流以上计算机系不把算法作为必修的。算法教材目前公认以Corman等著的"Introduction […]