This blog has been shut down permanently.

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  13 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks

#

     摘要: 最开始用了很原始的数据初始化方法,多谢dskit指点,现在已经改正为哈希字典了。因为在创建新节点的时候浪费时间比较严重,所以如果改成用向量会更好一些。 #include<stdio.h>#include<stdlib.h>int map[25]= {2, 2, 2, 3, 3, 3, 4,&n...  阅读全文
posted @ 2009-11-11 00:44 iZ 阅读(1844) | 评论 (4)编辑 收藏

1.输入输出

ACM和TopCoder不同,TopCoder只用让参赛者写一个class,而ACM需要参赛者完成整个console程序.在TopCoder中,输入输出是通过parameter传递的,不用过多考虑,在ACM中,却需要自己编写.

(1).只有一组输入时,这种情况不用我说了,都会,但是通常也不会有这么水的题

(2).固定组数的输入,可以利用一个计数器和while语句完成,

01 #include <iostream>
02
03 int main(void){
04     int n;
05     scanf("%d", &n);
06     while (n--){
07         //...
08     }
09     //...
10     return 0;
11 }

(3).测试数据结尾有标志字符(例如最后一组输入后给一个0),这个只用加一个if语句判断读入的数据是什么,是结束标志跳出就ok了.也不多说了

(4).题目没有告诉你有多少组数据,这个通常是最令新手疑惑的,这种情况,一般用文件结束标志EOF判断

01 #include <iostream>
02
03 int main(void){
04     int n;
05     while (scanf("%d", &n) != EOF){
06     //...
07     }
08     //...
09     return 0;
10 }

其实这里也可以用c++的cin输入流判断,例如

01 #include <iostream>
02
03 using namespace std;
04
05 int main(void){
06     int n;
07     while (cin>>n){
08     //...
09     }
10     //...
11     return 0;
12 }

但是这样不是特别好,为什么?下面会说.

对于输出,最好采用的接收一组数据,处理一组数据,把结果保存在一个缓冲数组中,待所有输入结束后,再一起输出,而不是待接收完所有输入后,再处理,再输出,这样会消耗更多的memory,而且会更慢.

2.关于效率

第一,上面的所有例子,均采用的c标准I/O,为什么不用c++的cin,cout呢?是有原因的,经实践,在大规模输入输出下,cin,cout效率远远低于scanf()和printf(),原因据我估计应该是以为scanf(),printf()是汇编写的(这点可以从这两个函数均可以接受任意多组parameter(s)看出,c/c++函数是不具备这样的性质的),而cin,cout均是直接c/c++写的流操作,本来c/c++就比汇编慢,还引入流,所以自然比scanf(),printf()慢了.因此,在输入输出数据量很小的情况下,出于方便的原因,可以采用cin,cout,而在输入输出数据量比较大的情况下用scanf(),printf()比较保险,避免超时.

第二.ACM中,除了c/c++,一般还支持java等语言,但是由于java是解释执行的,效率十分低下,为此,一般的JudgeOnline都把java的time limit设置为题目给定值(也就是c/c++的time limit)的三倍,而且给每一组输入再额外提供150ms.即使是这样,java遇上复杂或者高精度计算的题目,还是很容易超时,因为效率有时候还远远未到c/c++的1/3.因此,一般来说,除了个别java极其有利的情况(例如字符串处理),不建议使用java.

3.关于所得结果的解释

下面是一般JudgeOnline系统所有可能产生的结果,如果对返回的结果不明,看看解释吧

Waiting: Your program is being judged or waiting to be judged.

Accepted (AC): Congratulations! Your program has produced the correct output!

Presentation Error (PE): Your program's output format is not exactly the same as required by the problem, although the output is correct. This usually means the existence of omitted or extra blank characters (white spaces, tab characters and/or new line characters) between any two non-blank characters, and/or blank lines (a line consisting of only blank characters) between any two non-blank lines. Trailing blank characters at the end of each line and trailing blank lines at the of output are not considered format errors. Check the output for spaces, blank lines, etc. against the problem's output specification.

Wrong Answer (WA): Your program does not produce the correct output. Special judge programs will possibly return Wrong Answer in place of Presentation Error for simplicity and robustness.

Runtime Error (RE): Your program has failed during the execution. Possible causes include illegal file access, stack overflow, out of range in pointer reference, floating point exception, division by zero and many others. Programs that stay not responding for a long time (not consuming CPU cycles) may also be considered to have encountered runtime errors.

Time Limit Exceed (TLE): The total time your program has run for has exceeded the limit.

Each problem has two time limits - TOTAL TIME LIMIT and CASE TIME LIMIT. The former is the total time allowed for your program to deal with all input files. And the latter is the total time allowed for your program to deal with a single input file. Exceeding either one will lead to Time Limit Exceed. If you get Time Limit Exceed but find that your program has run for less time than is limited, your program must have exceeded that CASE TIME LIMIT.

Problems without a special demand on the time limit for a single input file will have its case time limit is trivially set as the same as its total time limit and the phrase "Case Time Limit" will not show up under the problem title.

Memory Limit Exceed (MLE): The maximum amount of memory that your program has used has exceeded the limit.

Output Limit Exceed (OLE): Your program has produced too much output. Currently the limit is twice the size of the file containing the expected output. The most common cause of this result is that your programs falls into an infinite loop containing some output operations.

Compile Error (CE): The compiler fails to compile your program. Warning messages are not considered errors. Click on the judge's reply to see the warning and error messages produced by the compiler.

No such problem: Either you have submitted with a non-existent problem id or the problem is currently unavailable (probably reserved for upcoming contests).

System Error: The judge cannot run your program. One example is that your program requires much more memory than hardware limitation.

Validate Error: The special judge program fails in checking your output, which means it may contain some bugs. If you get this result, please contact the administrator. (Of course, this also means your output is probably wrong).

posted @ 2009-11-11 00:43 iZ 阅读(1820) | 评论 (11)编辑 收藏

要看的书:

<算法导论>
<算法艺术与信息学竞赛>
<图论的算法与程序设计>
<国际大学生程序设计竞赛例题解>
<基本算法>
<骗分导论>
<国际大学生程序设计竞赛例题解(一)>-<数论、计算几何、搜索算法专集>
<国际大学生程序设计竞赛例题解(三)>-<图论、动态规划算法、综合题专集>

学习规划:

一、第一阶段(11月13日 – 12月4日)主要完成的算法:
1、基本数据结构:
        线性表、链表(尤其双向链表和循环链表)、栈、二叉树
2、加减乘除四则运算的高精度算法
3、了解算法思想:DP、贪心、二分
4、查找与排序: 
        二分查找、二叉排序数、qsort函数、归并排序、HASH
5、图论基础算法: 
        DFS、BFS、MST(Prim)、Dijkstra、Floyd 、拓扑排序、割点
6、数学知识:初等数论(整除、同余)

二、第二阶段(12月25日 – 2月1日)主要完成的算法:
1、高级数据结构: 
        堆、并查集及路径压缩(Kruskal)、线段树
2、图论高级算法: 
        二分图匹配(匈牙利算法)、网络流、最小费用流、最大团、最大独立集、中国邮路问题、找Hamilton圈、寻找欧拉回路、着色问题、连通性判定、传递闭包和差分约束系统
3、博弈算法:博弈树、寻找必败类算法
4、计算几何: 
        判断线段相交、判断点是否在多边形内、凸包、矩形的交与并、两直线相交问题、已知三点求圆心
5、高级数学知识:(组合数学、具体数学中为主) 
        Fibonacci、Catalan数的应用、差分序列和Stirling数、Burnside定理和置换群、容斥原理、概率问题、生成排列数
6、高级搜索技巧: 
        双向BFS、A*算法(启发式搜索)、最小消耗优先、变深度优先搜索

三、三个算法思想的具体训练内容:


1)、DP 重中之重 (准备拿出3天做DP一种类型)
要解决的经典例题: 
       1、 最长不下降子序列(Longest Increasing Subsequence) 
       2、 最长公共子序列 (Longest Common Subsequence) 
       3、 矩阵链乘法 (Matrix Multiplication) 
       4、0-1背包 
       5、凸多边形的最优三角划分 
       6、多边形游戏 ---- 三角大战

2)、Greedy 贪心算法 高效优选算法
要解决的经典问题: 
       1、0-1背包 
       2、MST(Prim、Kruskal) 
       3、Dijkstra 
       4、Huffman Tree Code(霍夫曼编码)

3)、二分法
要解决的经典问题: 
       1、 归并排序算法求逆序数 (Inversion Number) 
       2、 最近点对 
       3、 几种常见算法的二分查找优化:LIS (最长不下降子序列)

posted @ 2009-11-11 00:40 iZ 阅读(404) | 评论 (1)编辑 收藏

仅列出标题
共2页: 1 2