做 ACM 的那些人应该也都知道传说中的“疯狂提交找错法”吧。就是如果你题目没有过的话，提交的罚时是不会在最后的分数里面扣掉的。当然是希望在尽量少的次数内过掉，但是情急之下，疯狂提交也是一个办法，不管怎么算它都是有好处的：

• 如果最后题目 AC (Accept) 了，虽然罚时会让排名下降，但是不管罚时多少，多做出一道题的总比少做出一道题目的排名要靠前。
• 如果题目没有 AC ，也并没有什么损失。

但是疯狂提交也必须要能“找错”，否则就没有什么意义了。今天我也非常疯狂地爽了一把，并且最后成功找到问题，把题目 AC 了。

其实我平时并不做 ACM ，因为我对存算法不太在行，而且我也特别讨厌 ACM 这种纯黑箱的形式，只告诉你正确或者错误，而得不到一点调试信息。但是仔细想想其实现实世界很多地方是这样的，比如许多商业软件，没有提供源代码，出错以后你也只能是茫然，再比如自己发布软件的时候，甚至连“对”或者“错”这样的单纯的结果都没有，你只能尽可能地去遇见和避免各种 Bug 和错误。所以其实做 ACM 的题目应当还是一个相当不错的锻炼吧。

但是数值分析这门课的几个作业是 ACM 形式的判题系统，所以还得去做。这次的题目并不难，就是代数方程求根，算法也在书上都讲过了。然而做出来的程序无论如何都是 Wrong Answer 。这四五天的空余时间几乎都在做这个题目，唉，做得郁闷到极点，怎么就能不对呢？我尝试了各种各样的方法，牛顿法、改进的牛顿法、二分法、Steffensen 方法，还把它们结合起来，修改各种优化参数……总之就是过不了。

最后我静下来仔细想了一下，如果测试数据里面的数据非常大的话，用 double 进行计算必定会溢出，那样肯定算不出结果来，但是我看到题目的状态显示有人确实通过了，所以测试数据应该不会特别大。不过令我郁闷的是我在使用二分法的时候竟然 TLE (Time Limit Exceeded) 了，那除非是一个很大的区间啊！

最后我决定用疯狂提交找错法了。我要探测测试数据！但是 OJ (Online Judger) 给出的结果种类非常少，包括 WA (Wrong Answer) 、TLE 和 Runtime Error SIGSEGV 等，根本不能从中得出测试数据，然而我们可以对测试数据（包括整个运行环境中的任何状态）进行一个 bool 测试并得到结果：结果就由 WA 和 SIGSEGV 两种状态来区分。于是我写了一个 helper 函数：

void fire_seg_fault(){ int *ip = 0; *ip = 0;}

原理很简单，就是要产生一个运行时错误， abort 函数不允许调用，除以零似乎也被忽略掉了，不过对 NULL 指针解引用是绝对会造成运行时错误的。然后在代码里面就可以对测试数据进行探测了，比如：

if (n > 1000) fire_seg_fault();

提交，然后根据结果是 WA (或者 TLE) 还是 SIGSEGV 来判断 n 的范围。然后逐次缩小范围，对于整数来说总是可以在比较可观的次数之内得到一个准确的值。对于浮点数来说，其实计算机里面的浮点数也不会是无限位的，所以从理论上来说也可以通过逐步缩小范围得到“精确”的值（也就是它给定的值）。

经过我疯狂探测，得出了测试数据的规模：

• 一共有 14 组测试数据。
• 有 a > b 的情况。(真过分，ACM 就经常有这种情况啊，说“a and b are the two end-points of the given interval”，故意不说 a 比 b 小，然后又在示例测试中把所有的例子都写成 a 比 b 小，让你产生错觉，却又在测试数据里面来个 a 比 b 大，如果不小心误以为 a 一定比 b 小的就要郁闷了）
• a 的取值范围为 -100 到 1 。
• b 的取值范围为 -0.5? 到 3 。
• eps 如题目中描述的一样，一直都是 0.00005 。

出乎我的意料竟然测试数据的规模这么小的。可是竟然在二分法的时候会 TLE ，这就让我不解了。接着我继续用探针探测出 TLE 出在第三组测试数据上。第三组数据 n 是 5 ，并不大，所以我决定把第三组的参数全部探测出来，当然并不是特别轻松的活，我都想用脚本来写个“探测机”了。不过总算数据并不变态，最后还是被我探测出来了：

a == -4b == 2n == 5c[5] == 1c[4] == 4.6c[3] == -1.94c[2] == 0.296c[1] == -0.0199c[0] == 0.0005

这下为什么会 TLE 就明了了，画出函数图形如下所示：

我在判断结束条件的时候用了如下语句：

if (fp == 0 || (GOOD_ENOUGH(b-a, eps) && GOOD_ENOUGH(fp, eps)))

其中 GOOD_ENOUGH 是一个用于判断绝对值的宏。总之就是函数值 fp 在给定的区间 (-4,2) 里面的函数值永远都达不到给定的精度 (eps) ，所以就在那里死循环了。去掉那个判断得出的结果会飞掉，因为我在这里犯了一个很严重的错误：左右两边函数值的符号是一样的，不能用二分法。

但是我是在牛顿法失败的情况下才会去用二分法。牛顿法为什么会失败呢？实际上，在给定的区间之内根本没有实根，只有 4 个虚根，唯一的实根是 -5 左右的那个，但是那个是在区间之外的，可是几乎所有的收敛序列都直接收敛到那里去了，但是是在给定的区间之外的，无疑要被丢弃。

可是这样的话题目不是有问题吗？题目中说过：

It is guaranteed that a unique real number r exists in the given interval such that p(r) = 0.

在给定的区间之内明明没有根嘛，不过单从图形上来看的话，还是很接近零的。最后我将牛顿法的初始值选取密度加大了，总算得到一个看上去像样点的解，算出来的函数值是 0.0045 ，唉，这和零相比应该还有很大的差距吧，可是我把程序提交上去之后竟然 AC 了！不过让我觉得好像是有些碰运气的感觉啊。

不过毕竟是郁闷了几天的题目了，总算是通过了。发现自己在做这样的题目的时候经常都是考虑得太过复杂了。但是如果数学功底再扎实一些，从理论上来仔细分析一下的话，也许不会出现这种类似于“侥幸”通过的尴尬情况了吧。

* NetBeans
   NetBeans 是由Sun建立的開放原始碼的軟體開發工具，是一个开放框架，可扩展的开发平台，可以用于Java，C語言/C++等的开发，本身是一个开发平台，可以通过扩展插件来扩展功能，現在最新的穩定版本是Netbeans 6.1。在 NetBeans Platform 平台中，應用軟體是用一系列的軟體模組(modular software components)建構出來。而這些模組是一個jar檔(Java archive file)它包含了一組Java程式的類別而它們實作全依據依 NetBeans 定義了的...

* Eclipse
   Eclipse是著名的跨平台的自由集成开发环境（IDE）。最初主要用来Java语言开发，但是目前亦有人通过插件使其作为其他计算机语言比如C++和Python的开发工具。 Eclipse的本身只是一个框架平台，但是众多插件的支持使得Eclipse拥有其他功能相对固定的IDE软件很难具有的灵活性。许多软件开发商以Eclipse为框架开发自己的IDE。 Eclipse最初是由IBM公司开发的替代商业软件Visual Age for Java的下一代IDE开发环境，2001年11月贡献给开...

* J2EE
   这是SUN公司推出的J2EE SDK，是J2EE的参考实现，是实现J2EE最全的开发工具包，不过最好只在开发中使用。 J2EE JavaDoc: http://www.oschina.net/uploads/doc/j2ee_5.0.03/index.html J2EE，Java2平台企业版（Java 2 Platform Enterprise Edition）， 是Sun公司为企业级应用推出的标准平台(Platform)。Java平台共分为三个主要版本Java EE、Java SE和Java ME。 Sun公司在1998年发表JDK1.2版本的时候， 使用了新名称Java 2 Plat...

* IntelliJ IDEA
   屡获殊荣的Java开发环境，不过在现在Eclipse横行的世道，只剩下一些铁杆粉丝还在坚持使用此开发环境。

* JavaCC
   JavaCC(Java Compiler Compiler) 是一个用JAVA开发的最受欢迎的语法分析生成器。这个分析生成器工具可以读取上下文无关且有着特殊意义的语法并把它转换成可以识别且匹配该语法的 JAVA程序。它还提供JJTree等工具来帮助我们建立语法树。JavaCC plug-in：一个用于辅助JavaCC应用程序开发的Eclipse插件．

* Groovy
   Groovy是一种基于JVM的敏捷开发语言，它结合了Python、Ruby和Smalltalk的许多强大的特性。 Groovy已在WebWork2中的应用。它可以被编译为标准的Java Bytecode。

* EasyEclipse
   EasyEclipse这是一个把EclipseIDE与一些关键的开源插件分类打包在一起.以使得Eclipse更易于下载,安装,使用.

* SUN JDK
   SUN 公司的Java开发工具包，原汁原味的。 JDK 6.0 文档：http://www.oschina.net/uploads/doc/j2se/index.html JDK 6.0 JavaDoc：http://www.oschina.net/uploads/doc/j2se/api/index.html Java是由Sun Microsystems公司于1995年5月推出的Java程序设计语言（以下简称Java语言）和Java平台的总称。用Java实现的 HotJava浏览器（支持Java applet）显示了Java的魅力：跨平台、动态的Web、Internet计算。从此，Java被广泛接受并推动...

* ProGuard
   是一个免费的 Java类文件的压缩，优化，混肴器。它删除没有用的类，字段，方法与属性。使字节码最大程度地优化，使用简短且无意义的名字来重命名类、字段和方法 。eclipse已经把Proguard集成在一起了。

* jEdit
   jedit 是一个用java 编写的源码开放的文本编辑器。有很多有用的特性，包括语法加亮显示，括号匹配，表达式搜索，多个文件搜索和替换，定义键盘宏等等。jedit 的插件结构非常完善。在日本相当受欢迎!

* ANTLR
   ANTLR(ANother Tool for Language Recognition)它是Java开发的词法分析工具，它可以接受词文法语言描述,并能产生识别这些语言的语句的程序。作为翻译程序的一部分,你可以使用简单的操作符和动作来参数化你的文法，使之告诉ANTLR怎样去创建抽象语法树(AST)和怎样产生输出。ANTLR知道怎样去生成识别程序，语言包括 Java，C++，C#. Hibernate就是采用ANTLR来编译HQL查询语言的。...

* JBuilder
   JBuilder 2008 ，The Open, Fully Supported Java IDE，是一种Borland软件公司出品的Java集成编程环境，有不同功能程度的多个版本。甲骨文公司（Oracle）内部用的软件 JDeveloper是JBuilder补充改写的。 JBuilder的主要竞争者包括IBM的Websphere，JetBrains的IntelliJ IDEA，BEA Systems和Eclipse。 2005年5月，Borland 公司宣布下一个版本的 JBuilder 将会以 Eclipse 为基础。 ...

* Jython
   Jython 是Python的纯Java实现。她无缝地结合了Java类与Python，使用户能以Python语言的语法编写在Java虚拟机上运行的软件。它的特点有：与相似的Java程序相比，Jython极大的的减少了编程代码量。Jython同时拥有解释器和编译器，使其无需编译就可以测试程序代码。 Jython 是一种完整的语言，而不是一个Java翻译器或仅仅是一个Python编译器，它是一个Python语言在Java中的完全实现。 Jython也有很多从CPython中继承的模块库。最有...

* JFlex
   JFlex是一个Java的词法/语法分析生成器。

* OpenJDK
   an open-source implementation of the Java Platform, Standard Edition, and related projects.

* Cube-J
   Cube- J是一个开源轻量级Java IDE。Cube-J的特性包括：语法高亮显示，代码自动缩进、自动加括弧、显示行号、加亮显示一行代码、提供编译功能、文件浏览、类结构大纲、控制台、浮动窗口框架（Docking Framework）、代码自动完成、多种外观/皮肤。Cube-J既可以以桌面应用程序方式运行也可以以Applet方式运行。

* Midinux SDK
   11 月21日，在北京嘉里中心，中科红旗发布了Midinux SDK。此次发布的SDK，是为MID Linux 开发商、爱好者所提供的，为MID开发应用软件的工具集，它为MID软件产业再次注入了强大的力量。此前，已经有众多的ISV基于Midinux SDK开发了大量高价值的应用，为MID市场提供了至关重要的组成部分。 Midinux SDK整合了Midinux所有的应用环境，支持库和头文件，包括了GTK，Clutter，EFL等架构、示例程序。SDK支持 C/C++，Python，Java等开发语...

* Beanshell
   Beanshell 是用Java写成的，一个小型的、免费的、可以下载的、嵌入式的Java源代码解释器，具有对象脚本语言特性。BeanShell执行标准Java语句和表达式，另外包括一些脚本命令和语法。它将脚本化对象看作简单闭包方法（simple method closure）来支持，就如同在Perl和JavaScript中的一样。　它具有以下的一些特点：使用Java反射API以提供Java语句和表达式的实时解释执行；可以透明地访问任何Java对象和API；可以在命令行模式、控...

* RetroGuard
   RetroGuard是不错的Java混淆器，在JBuilder7的企业版中也带了这个混淆器。而yGuard 是RetroGuard的一个升级版本自带一个ANT任务

* Jcoder
   Premiumsoft 发布了Jcoder Java IDE 1.0的Windows版本是一个轻量级的Java IDE编辑器。为Java和Web的开发人员提供全面的设施，提高开发，编译和运行Java程序的效率。Jcoder的特点是直观的界面和构成源代码的编辑器，编译器，项目管理，调试器，代码编辑和代码完成的功能。

* JavaGuard
   JavaGuard是一个通用的字节码模糊器，旨在容易地适合你的规则建造和测试进程，保证你的有价值的代码更安全，使其不易被反编译以及其它形式的反向处理。

* JODE
   JODE 包含一个Java混淆器与一个Java优化器。通过一个脚本文件可以控制Class文件的多种优化方式。它支持以下操作：1.能够把 Class,method,field 和local names 重命成简略的，模糊的或者特定名字的或者依照一个转换表.2.除去debugging 信息.3.除去"坏死的"代码(classes, fields, methods).4.优化局部变量的分配

* CAP
   CAP（Code Analysis Plugin）是一个非常便利的Eclipse插件，它可以解析Java包/类依存关系，同时给出图形报表。 CAP的特征与主要功能 Ecplise插件（3.0＋）图形报表 Java包以及类之间的依存关系分析验证框架结构的健壮性提高Java代码代码的封装性，保证框架结构品质，包的构造结构，代码的可重用性，可维护性等等 在线安装URL：http://cap.xore.de/update ...

* BEA JRockit
   BEA的Java开发工具，据说性能非常好！

* tIDE
   tIDE 是一个非常小，快速，强大，易于使用的Java IDE。整个程序只有1M左右，无需安装。tIDE完全采用Java开发，需要JRE6或更高的运行环境，但可以用于开发JDK5，1.4甚至是1.2的应用程序。tIDE支持通过插件来扩展/增强其功能，当前提供的扩展工具包括：Bug查找工具（findbugs，PMD，Lint4J，JLint），代码修饰工具（AStyle，CheckStyle），分析工具（jad），代码混淆工具（ProGuard）。此外tIDE还提供一个工具用于从现有的 Eclipse...

* IBM JDK
   IBM 的 Java开发工具，WebSphere 必须使用此开发工具才能运行

* Apache Harmony
   Apache Harmony是Apache软件基金会的Java SE项目。 这个项目的目标是营造一个大型的、健康的社区，这个社区由那些对运行是平台感兴趣的人组成。他们的任务是完成： 一个兼容的、独立的Java SE 5 JDK的实现，并根据Apache License v2发布；一个由社区开发的模块化的运行时（包括java虚拟机和类库）体系结构。 该项目期望支持尽可能多的不同平台。一个特定的平台是否被支持，主要取决于参与者能在这个平台上定期运行测试、报告...

* IKVM.NET
   IKVM.NET 的是开源的基于.NET CLR 的Java虚拟机。基于.NET的Java虚拟机意味着我们可以让Java程序跑在.NET上，可以通过虚拟机这个中介让Java程序和.NET应用程序一起协同工作。更难能可贵的是，IKVM同时支持微软的.NET Framework 和 Mono。IKVM的技术特性包括： 1.可以静态和动态（运行时）把Java的字节代码转换为.NET 的IL形式； 2.包括了一个Java的标准库，这个标准库已经静态编译成了.NET IL的形式； 3.提供力JNI 接口，可以让J...

* jdec
   jdec是一个Java反编译器。它能够把出现在一个.class文件中的字节码还原成Java源代码，反编译的结果几乎与原始Java文件相同。它还自带一个利用swing开发的用户操作界面。

* UCDetector
   这是一个Eclipse的插件，用来检测Java中的无用代码。

* SJPT
   SJPT是一个分析工具包支持包括自顶向下(LL(1))和自底向上(LR(0), SLR(1), LR(1) and LALR(1))。该工具包同时支持为所有自底向上的分析法生成Java剖析器。

* J
   J is a text editor written entirely in Java and distributed under the GNU General Public License.

* jarg
   The jarg makes smaller a jar file in whitch java classes are stored

* DrJava
   这是一个免费的、轻量型的开放源码 Java IDE，具有集成的读-计算-打印（read-eval-print）循环、调试器和 JUnit 支持。

* JBoss Developer Studio
   红帽公司的 JBoss Developer Studio 是一款基于Eclipse的捆绑了开源工具软件和运行时间软件的集成开发环境（IDE）。 这款产品包括了JBoss Enterprise Middleware和Exadel公司的技术，可以提供一个循环的应用开发环境。名为Red Hat Developer Studio的测试版产品是在8月份推出的，从那时到现在它已经被下载了5万多次。 红帽公司产品营销经理Bryan Che说：“它整合了许多功能强大的富网络设计工具和AJAX应用软件。它还包括...

* Rhino
   Rhino是用纯Java写成的JavaScript的开放源代码实现。它最常被用于嵌入Java应用程序，以便为终端用户提供脚本的能力。

* BlueJ
   BlueJ is an integrated Java environment specifically designed for introductory teaching.

* Jikes
   Jikes 是由IBM 开发出来的一个开放源码的Java编译器。它具有非常快速的编译速度和高度兼容性。

* SableCC
   SableCC是一个用来生成编译器和分析器的面向对象的框架。这个框架是基于两个基本的设计决策：首先是利用面向对象技术自动构建精确的典型的抽象语法树。第二，这个框架使用经过扩展的Visitor访问者模式来生成tree-walker类。

* FreeCC
   FreeCC (前身是 KawaDD) 是一个Java开发的语法、词法解析器生成器

* GCJ
   GCJ（GNU Compiler for the Java Programming Language, GCJ）是多元的，高效的，具有前瞻性的java编译器。它可以编译java源代码，将java字节码转换成本地机器代码。目前支持的java版本最高 1.5，最新的1.6还不支持。 为什么要用GCJ？速度不是唯一的理由。他强大的分析工具，作为服务器开发的利器。他产生于JVM蜗牛时代，但今天的JVM已经不可同日而语了。...

* Grammatica
   Grammatica是一个C#和Java的语法剖析器生成器(Parser Generator或叫作编译器的编译器:Compiler Complier) 。它相对于其它一些类似的工具如yacc和ANTLR有了更好的改进。这是因为Grammatica： 1.创建了更好的注释和易读的源代码. 2.拥有错误自动恢复并能够详述错误信息. 3.支持语法/词法测试与调试.

* Rats!
   Rats! 是一个用来生成解析类似C语言的语法分析器，生成的解析器是Java语言的。

* CUP
   一个LALR(Lookahead Left to Right Parsing)语法/词法分析生成器.

* Chaperon
   Chaperon是一个可以把有结构的Text转换成XML.它包括一个强大的LALR(1)解析器来解析Text和一个可以用来创建XML文档的Tree builder。

* Excelsior JET
   Excelsior JET是一款有提前编译技术的Java虚拟机增强工具（非开源）。提前编译器可以将您的类文件和jars文件转化成高度优化的二进制可执行文件，能够在 Intel x86平台的Microsoft Windows和 Linux系统中运行。同传统 JVM（Java虚拟机）中运行的原始类文件相比，这些经过优化的可执行文件具有更快的运行速度。另外，您的应用程序将会得到更好的保护，以防被篡改或窃取代码 ...

* JPackage
   FC4 的发行说明中建议用户尽量避免直接使用 Sun 提供的 Java RPM，并提供了从 JPackage.org 构建 Java 的途径。 The JPackage Project has two primary goals: To provide a coherent set of Java software packages for Linux, satisfying all quality requirements of other applications. To establish an efficient and robust policy for Java software packaging and installation. ...

* runcc
   runcc是一种在运行时生成parsers和lexers的语法分析生成器。它自带一个Java和XML分析器的例子。

* JTopas
   JTopas 这个开源项目提供了一个很小，容易使用的用来分析特殊Text数据的Java类包。这些数据可以是来自包含一些注释的简单配置文件，HTML，XML，RTF stream，和来自其程序语言的源代码等。有时需要解释所有的Text数据，而有时只需解释其中重要的部分。

* Beaver
   Beaver是一个LALR(1) 语法分析生成器。它读取一些上下文无关的语法并把它转换成一个利用该语法描述的语言分析器（一个Java类）。

* java2tcl
   java2tcl 用来将Java代码转换成TCL代码。

* JBrownie
   JBrownie is a companion tool for Java developers preferring to use plain text editors for writing programs over a resource hungry IDE. The downside of this is that the Java compiler has to be started manually, which may seriously slow down work. JBrownie addresses this problem by monitoring the source tree and automatically recompiling any modified Java source files on the fly. ...

* Antiplate
   Antiplate 是一个用来创建通用 Java 项目结构的Ant 脚本，它创建了项目目录、属性文件、编译脚本以及通用的设置和编译目录。

*补充一个
   JCreator Pro
这个是一个轻量级的JAVA开发工具
目前版本5（我正在使用4.5）

别人博客上看到这样一篇文章：

喜欢C，没有理由，追求短代码~~我想没有一门语言可以达到这样的效果~~本来已经很精简的程序在熟练的程序员手上能够缩减到原长度的1/4，而且功能没有任何差别~
两段完全一样的代码~~
#include <stdio.h>
void main()
{
int k[]={100,50,10,5,2,1},n,m,i,j,t;
while(scanf("%d",&n))
{
if(n==0) break;
t=0;
for(i=0;i<n;++i)
{
scanf("%d",&m);
for(j=0;j<6;++j)
while(m>=k[j])
++t,m-=k[j];
}
printf("%d\n",t);
}
}
缩减后：我爱C语言丶__唯美
main()
{
int k[]={100,50,10,5,2,1},n,m,i,t,s;
for(;scanf("%d",&n),n;printf("%d\n",t))
for(t=i=0;i<6*n;t+=s=m/k[i%6],m-=s*k[i++%6])
scanf(i%6?"":"%d",&m);
}

这就是C的魅力所在~我爱C语言~~

我觉得这是一个误区，优秀的代码在节省空间的情况下不应以牺牲运行效率和可读性为代价，上面的代码，原来的代码看了就知道用途（最少第四版人民币的数量），可是看了下面那段代码，你几遍能读懂它的意思？

我觉得写代码应该在可读性（易于别人阅读、管理）和时间效率（速度）上找到平衡，代码长度应该被忽略，毕竟看似短的代码编译之后未必很短短：

（Dev c++ 4.9.9.2）

上面的代码19970 b

下面的代码18946 b

两者都占用硬盘都是 20480 b

怎样才算熟练掌握数据结构、常用算法

不可能都完全记住那么多的算法.
常用算法,拿过来就可以写出来
不常用的,拿起书来,看10分钟,就能理解算法(因为以前记过).
对以前没有记过的算法,就不好说了,难的可能要研究好几天.
这样就可以了.

应该熟练掌握的常用的算法应该有:
各种排序算法（插入排序、冒泡排序、选择排序，快速排序，堆排序，归并排序）
线性表(一般的线性表,栈,队列)的插入和删除
二叉树的遍历（前序，中序，后序）
图的遍历（深度优先，广度优先）
二分法查找，排序二叉树，Hash查找（处理冲突的方法）。

分析一个东西,你可以用不同的眼光去看待,有很多时候,就跟自己生活一样,觉得小时候看待问题很幼稚,现在看问题全面了,而且方式不一样了,为什么,就是成长吧,就跟这个一样的,你对算法,比如写一个程序,可能直接写很简单,可是可以有一些有趣的方式,比如通过什么样来表达,怎么样更高效..等等吧

对于大学里把基本的专业课学扎实就ok，如：数据结构，离散，操作系统等。碰到一些基本的数据结构和算法，如查找排序要根据原理马上能写出相应的代码就行了，我个人是这样理解的，对于更深层次的东西，也是建立在自己熟练的基础之上的吧

转一个搞ACM需要的掌握的算法.
要注意,ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.
适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,
发挥自己的长处,这才是重要的.


第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，
因为太常用，所以要练到写时不用想，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*算法，最小耗散优先.


相关的知识

图论

路径问题
        0/1边权最短路径
        BFS
        非负边权最短路径（Dijkstra）
            可以用Dijkstra解决问题的特征
        负边权最短路径
        Bellman-Ford
            Bellman-Ford的Yen-氏优化
            差分约束系统
        Floyd
            广义路径问题
            传递闭包
            极小极大距离 / 极大极小距离
        Euler Path / Tour
            圈套圈算法
            混合图的 Euler Path / Tour
        Hamilton Path / Tour
            特殊图的Hamilton Path / Tour 构造

    生成树问题
        最小生成树
        第k小生成树
        最优比率生成树
        0/1分数规划
        度限制生成树

    连通性问题
        强大的DFS算法
        无向图连通性
            割点
            割边
            二连通分支
            有向图连通性
            强连通分支
            2-SAT
            最小点基

    有向无环图
        拓扑排序
            有向无环图与动态规划的关系

    二分图匹配问题
        一般图问题与二分图问题的转换思路
        最大匹配
            有向图的最小路径覆盖
            0 / 1矩阵的最小覆盖
        完备匹配
        最优匹配
        稳定婚姻

    网络流问题
        网络流模型的简单特征和与线性规划的关系
        最大流最小割定理
        最大流问题
            有上下界的最大流问题
                循环流
        最小费用最大流 / 最大费用最大流

    弦图的性质和判定


组合数学

    解决组合数学问题时常用的思想
        逼近
        递推 / 动态规划
    概率问题
        Polya定理


计算几何 / 解析几何

    计算几何的核心：叉积 / 面积
    解析几何的主力：复数

    基本形
        点
        直线，线段
        多边形

    凸多边形 / 凸包
        凸包算法的引进，卷包裹法

    Graham扫描法
        水平序的引进，共线凸包的补丁

    完美凸包算法

    相关判定
        两直线相交
        两线段相交
        点在任意多边形内的判定
        点在凸多边形内的判定

    经典问题
        最小外接圆
            近似O(n)的最小外接圆算法
        点集直径
            旋转卡壳，对踵点
        多边形的三角剖分


数学 / 数论

最大公约数
        Euclid算法
            扩展的Euclid算法
                同余方程 / 二元一次不定方程
                同余方程组

    线性方程组
        高斯消元法
            解mod 2域上的线性方程组
        整系数方程组的精确解法

    矩阵
        行列式的计算
            利用矩阵乘法快速计算递推关系

    分数
        分数树
        连分数逼近

    数论计算
        求N的约数个数
        求phi(N)
        求约数和
        快速数论变换
        ……

    素数问题
        概率判素算法
        概率因子分解


数据结构

    组织结构
        二叉堆
        左偏树
        二项树
        胜者树
        跳跃表
        样式图标
        斜堆
        reap

    统计结构
        树状数组
        虚二叉树
        线段树
            矩形面积并
            圆形面积并

    关系结构
        Hash表
        并查集
            路径压缩思想的应用

    STL中的数据结构
        vector
        deque
        set / map


动态规划 / 记忆化搜索

动态规划和记忆化搜索在思考方式上的区别

    最长子序列系列问题
        最长不下降子序列
        最长公共子序列
        最长公共不下降子序列

    一类NP问题的动态规划解法

    树型动态规划

    背包问题

    动态规划的优化
        四边形不等式
        函数的凸凹性
        状态设计
        规划方向


线性规划

常用思想

    二分          最小表示法

串

    KMP                              Trie结构
    后缀树/后缀数组            LCA/RMQ
    有限状态自动机理论

排序
    选择/冒泡        快速排序        堆排序            归并排序
    基数排序        拓扑排序        排序网络


中级:
一.基本算法:
    (1)C++的标准模版库的应用. (poj3096,poj3007)
    (2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
二.图算法:
    (1)差分约束系统的建立和求解. (poj1201,poj2983)
    (2)最小费用最大流(poj2516,poj2516,poj2195)
    (3)双连通分量(poj2942)
    (4)强连通分支及其缩点.(poj2186)
    (5)图的割边和割点(poj3352)
    (6)最小割模型、网络流规约(poj3308, )
三.数据结构.
    (1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)
    (2)静态二叉检索树. (poj2482,poj2352)
    (3)树状树组(poj1195,poj3321)
    (4)RMQ. (poj3264,poj3368)
    (5)并查集的高级应用. (poj1703,2492)
    (6)KMP算法. (poj1961,poj2406)
四.搜索
    (1)最优化剪枝和可行性剪枝
    (2)搜索的技巧和优化 (poj3411,poj1724)
    (3)记忆化搜索(poj3373,poj1691)
    
五.动态规划
    (1)较为复杂的动态规划(如动态规划解特别的施行商问题等)
        (poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
    (2)记录状态的动态规划. (POJ3254,poj2411,poj1185)
    (3)树型动态规划(poj2057,poj1947,poj2486,poj3140)
六.数学
    (1)组合数学:
        1.容斥原理.
        2.抽屉原理.
        3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
        4.递推关系和母函数.
      
    (2)数学.
        1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
        2.概率问题. (poj3071,poj3440)
        3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
    (3)计算方法.
        1.0/1分数规划. (poj2976)
        2.三分法求解单峰(单谷)的极值.
        3.矩阵法(poj3150,poj3422,poj3070)
        4.迭代逼近(poj3301)
    (4)随机化算法(poj3318,poj2454)
    (5)杂题.
        (poj1870,poj3296,poj3286,poj1095)
七.计算几何学.
        (1)坐标离散化.
        (2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).
            (poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
        (3)多边形的内核(半平面交)(poj3130,poj3335)
        (4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)


高级:
一.基本算法要求:
      (1)代码快速写成,精简但不失风格
          (poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
      (2)保证正确性和高效性. poj3434
二.图算法:
      (1)度限制最小生成树和第K最短路. (poj1639)
      (2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
        (poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
      (3)最优比率生成树. (poj2728)
      (4)最小树形图(poj3164)
      (5)次小生成树.
      (6)无向图、有向图的最小环  
三.数据结构.
      (1)trie图的建立和应用. (poj2778)
      (2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法
          (RMQ+dfs)).(poj1330)
      (3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的
          目的). (poj2823)
      (4)左偏树(可合并堆).
      (5)后缀树(非常有用的数据结构,也是赛区考题的热点).
        (poj3415,poj3294)
四.搜索
      (1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
      (2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
      (3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)
五.动态规划
      (1)需要用数据结构优化的动态规划.
        (poj2754,poj3378,poj3017)
      (2)四边形不等式理论.
      (3)较难的状态DP(poj3133)
六.数学
      (1)组合数学.
        1.MoBius反演(poj2888,poj2154)
        2.偏序关系理论.
      (2)博奕论.
        1.极大极小过程(poj3317,poj1085)
        2.Nim问题.
七.计算几何学.
      (1)半平面求交(poj3384,poj2540)
      (2)可视图的建立(poj2966)
      (3)点集最小圆覆盖.
      (4)对踵点(poj2079)
      八.综合题.
      (poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

初期:
一.基本算法:
    (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)
    (2)型如下表的简单DP(可参考lrj的书 page149):
      1.E[j]=opt (poj3267,poj1836,poj1260,poj2533)
      2.E[i,j]=opt (最长公共子序列)  
        (poj3176,poj1080,poj1159)
      3.C[i,j]=w[i,j]+opt.(最优二分检索树问题)
六.数学
    (1)组合数学:
        1.加法原理和乘法原理.
        2.排列组合.
        3.递推关系.
          (POJ3252,poj1850,poj1019,poj1942)
    (2)数论.
        1.素数与整除问题
        2.进制位.
        3.同余模运算.
          (poj2635, poj3292,poj1845,poj2115)
    (3)计算方法.
        1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.
    (1)几何公式.
    (2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)
    (3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
        (poj1408,poj1584)
    (4)凸包. (poj2187,poj1113)

http://poj.org/problem?id=2407

Description

Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.
Input

就是求小于n且与n互质的数的个数

这题使用到欧拉函数：
对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。

φ函数的值
　　通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。
　　若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
　　欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
　　特殊性质：当n为奇数时，φ(2n)=φ(n), 证明于上述类似。

证明略

举例：
　　ψ（１０）＝１０×（１－１/２）×（１－１/５）＝４；
　　ψ（３０）＝３０×（１－１/２）×（１－１/３）×（１－１/５）＝８；
　　ψ（４９）＝４９×（１－１/７）＝４２。

我的代码：
#include<cstdio>
#include<iostream>
using namespace std;
#include<cmath>
int num[100000];
int f_Euler(int s,int a)//返回欧拉数的个数，s是数组num里数据的个数，a是原来输入数据，即n
{
double ans=a;
int i;
for(i=1;i<=s;i++)
{
   ans*=(1-1.0/num[i]);
}
return (int)(ans+0.1);
}
int main()
{
num[0]=1;//无用
int a,b,s,i,max,t;
while(scanf("%d",&a)&& a)
{
   t=a;
   s=0;
   //以下为分解质因数
   max=sqrt(double(a))+1;
   if(a%2==0){
    while(a%2==0){
     a=a/2;
    }
    num[++s]=2;
   }
   for(int i=3;i<=max;i+=2)
   {
    if(a%i==0){
     while(a%i==0){
      a=a/i;
     }
     num[++s]=i;
    }
   }
   if(a!=1)num[++s]=a;//分解最后剩下的数（可能大于sqrt(n)）
   printf("%d\n",f_Euler(s,t));
   memset(num,0,sizeof(int)*s);
}
return 0;
}

poj上一个优化的代码：
while(scanf("%d",&n),n != 0){
        if(n == 1){
            printf("0\n"); continue;
        }
        ans = n;
        for(int i = 2;i*i <= n;++i){
            if( n % i == 0 ){
                ans = ans - ans/i;//见注释
                while(n%i == 0){
                    n /= i;
                }
            }
        }
        // n is prime itself
        if(n != 1) ans = ans - ans / n;
        printf("%d\n",ans);
    }
注释：
ans = ans - ans/i其实就是
欧拉定理ans*=(1-1.0/num[i]);的简化版，深入理解欧拉函数后就知道是：ans/i是小于等于ans被i整除的数的个数..

附：
2-100欧拉函数表（供测试用）
　　n φ(n)
　　2 1
　　3 2
　　4 2
　　5 4
　　6 2
　　7 6
　　8 4
　　9 6
　　10 4
　　11 10
　　12 4
　　13 12
　　14 6
　　15 8
　　16 8
　　17 16
　　18 6
　　19 18
　　20 8
　　21 12
　　22 10
　　23 22
　　24 8
　　25 20
　　26 12
　　27 18
　　28 12
　　29 28
　　30 8
　　31 30
　　32 16
　　33 20
　　34 16
　　35 24
　　36 12
　　37 36
　　38 18
　　39 24
　　40 16
　　41 40
　　42 12
　　43 42
　　44 20
　　45 24
　　46 22
　　47 46
　　48 16
　　49 42
　　50 20
　　51 32
　　52 24
　　53 52
　　54 18
　　55 40
　　56 24
　　57 36
　　58 28
　　59 58
　　60 16
　　61 60
　　62 30
　　63 36
　　64 32
　　65 48
　　66 20
　　67 66
　　68 32
　　69 44
　　70 24
　　71 70
　　72 24
　　73 72
　　74 36
　　75 40
　　76 36
　　77 60
　　78 24
　　79 78
　　80 32
　　81 54
　　82 40
　　83 82
　　84 24
　　85 64
　　86 42
　　87 56
　　88 40
　　89 88
　　90 24
　　91 72
　　92 44
　　93 60
　　94 46
　　95 72
　　96 32
　　97 96
　　98 42
　　99 60
　　100 40