• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 閱讀(1868) | 評論 (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 閱讀(1840) | 評論 (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 閱讀(424) | 評論 (1)編輯 收藏

            僅列出標題
            共2頁: 1 2 
            久久成人影院精品777| yy6080久久| av无码久久久久不卡免费网站| 精品熟女少妇a∨免费久久| 久久亚洲精品人成综合网| 一本大道久久a久久精品综合| 国内精品久久久久久麻豆| 久久无码人妻精品一区二区三区| 久久av免费天堂小草播放| 久久国内免费视频| 久久国产一片免费观看| 久久精品欧美日韩精品| 久久久精品人妻一区二区三区蜜桃| 青青青国产精品国产精品久久久久 | 国产成人无码精品久久久性色| 青青热久久综合网伊人| 国产精品久久新婚兰兰| 久久精品www| 蜜臀久久99精品久久久久久小说| 国产伊人久久| 久久综合九色综合精品| 久久精品亚洲中文字幕无码麻豆| 久久久久国产精品三级网| 久久免费精品视频| aaa级精品久久久国产片| 久久超碰97人人做人人爱| 亚洲国产精品综合久久一线 | 久久精品国产国产精品四凭| 99久久er这里只有精品18| 国产成人久久精品一区二区三区| 欧美午夜A∨大片久久| 久久九九免费高清视频| 99久久这里只有精品| 久久r热这里有精品视频| 久久狠狠高潮亚洲精品 | 国产成人香蕉久久久久| 99久久精品国产一区二区蜜芽 | 久久青青国产| 日韩精品无码久久一区二区三| 99久久亚洲综合精品成人| 国产精品狼人久久久久影院|