CSP初賽知識點復習

CSP-J/S第一輪（初賽）知識點精講NOIP（全國青少年信息學奧林匹克競賽）于2019年取消。取而代之的是由CCF推出的非專業(yè)級軟件能力認證，也就是現(xiàn)在的CSP?J/S。CSP非專業(yè)級認證的第一輪（也就是NOIP初賽）常常使某些大神對基礎(chǔ)知識不太了解無緣復賽...所以今天學習下初賽知識點。信息學史及基本知識一、信息學及計算機史計算機的頂級獎項：圖靈獎、馮·諾依曼獎圖靈獎：由ACM（美國計算機協(xié)會）設(shè)立于1966年。是“計算機界的諾貝爾獎”。馮·諾依曼獎：由IEEE設(shè)立。對信息科學做出突出貢獻的大神：圖靈（所以才有個獎），馮·諾伊曼中國獲圖靈獎的大神：姚期智（清華就有姚班，就是以他的名字命名的）世界第一臺電子計算機：埃尼阿克（ENIACENIAC），于1946年2月14日在美國賓夕法尼亞大學誕生。又被叫做電子管計算機。二、關(guān)于編程編程語言：分兩類：面向?qū)ο蠛兔嫦蜻^程。高級語言和低級語言的區(qū)別：高級語言需要編譯運行，常數(shù)較大，運行速度慢。而低級語言常數(shù)極小，運行速度快。此外，高級語言更容易移植。常見低級語言：匯編面向?qū)ο蟮母呒壵Z言：C++，Java，EIFFEL，Simula67等。面向過程的高級語言：C，F(xiàn)ortran語言。遞歸編程：遞歸是指一種通過重復將問題分解為同類的子問題而解決問題的方法。遞歸式方法可以被用于解決很多的計算機科學問題。簡單來講，就是“自身調(diào)用自身”（在函數(shù)中）。P類/NP類/NPC類問題：1、P類問題：如果一個問題能找到一個在多項式時間內(nèi)解決它的算法，那么這個問題就是P問題。2、NP類問題：注意：NP問題不是非P類問題，而是在多項式時間內(nèi)驗證一個解的問題?；蛘?，我們可以將其理解為在多項式時間內(nèi)猜出一個解的問題。3、NPC類問題：定義如下：如果一個問題是NP問題，而且所有的NP問題都可以約化到它。那么它就是NPC類問題。再來介紹一下關(guān)于約化的定義：如果一個問題A可以約化為問題B，含義就是這個問題A可以用問題B的解法來解決。三、關(guān)于計算機先上張大圖：重要設(shè)備：硬件組成：控制器(Control):是整個計算機的中樞神經(jīng)，其功能是對程序規(guī)定的控制信息進行解釋，根據(jù)其要求進行控制，調(diào)度程序、數(shù)據(jù)、地址，協(xié)調(diào)計算機各部分工作及內(nèi)存與外設(shè)的訪問等。運算器(Datapath):運算器的功能是對數(shù)據(jù)進行各種算術(shù)運算和邏輯運算，即對數(shù)據(jù)進行加工處理。存儲器(Memory):存儲器的功能是存儲程序、數(shù)據(jù)和各種信號、命令等信息，并在需要時提供這些信息。輸入設(shè)備(Inputsystem):輸入設(shè)備是計算機的重要組成部分，輸入設(shè)備與輸出設(shè)備合稱為外部設(shè)備，簡稱外設(shè)，輸入設(shè)備的作用是將程序、原始數(shù)據(jù)、文字、字符、控制命令或現(xiàn)場采集的數(shù)據(jù)等信息輸入到計算機。常見的輸入設(shè)備有鍵盤、鼠標器、光電輸入機、磁帶機、磁盤機、光盤機等。輸出設(shè)備(Outputsystem):輸出設(shè)備與輸入設(shè)備同樣是計算機的重要組成部分，它把外算機的中間結(jié)果或最后結(jié)果、機內(nèi)的各種數(shù)據(jù)符號及文字或各種控制信號等信息輸出出來。微機常用的輸出設(shè)備有顯示終端CRT、打印機、激光印字機、繪圖儀及磁帶、光盤機等。CPU及存儲：CPU（中央處理器）=運算器+控制器+寄存器運算器=算術(shù)邏輯運算單元（ALU）及浮點運算單元（FPU）存儲器=內(nèi)存儲器+外存儲器BIOS是英文"BasicInputOutputSystem"的縮略語，直譯過來后中文名稱就是"基本輸入輸出系統(tǒng)"。其實，它是一組固化到計算機內(nèi)主板上一個ROM芯片上的程序，它保存著計算機最重要的基本輸入輸出的程序、系統(tǒng)設(shè)置信息、開機后自檢程序和系統(tǒng)自啟動程序。其主要功能是為計算機提供最底層的、最直接的硬件設(shè)置和控制。隨機存儲器RAM的“隨機”指“隨時訪問”所以，我們記下來以下知識點：斷電后可以保存數(shù)據(jù)：硬盤，ROM斷電后不可以保存數(shù)據(jù)：顯存（顯卡內(nèi)存），RAM，CPU計算機各存儲單位及進位關(guān)系：計算機的存儲單位有以下幾種：TB/GB/MB/KB/B他們之間的進位關(guān)系為1024（這應(yīng)該是常識，沒打過比賽還沒玩過手機么？）特殊地，1B=8(bit)，這里的bit是二進制下的一位內(nèi)存。進制及進制轉(zhuǎn)化十進制轉(zhuǎn)任意進制將十進制轉(zhuǎn)換成N進制，只需把十進制數(shù)每次除N求余數(shù)，然后把余數(shù)逆序?qū)懗鰜??？床欢涂磮D：這是二進制的圖，其他進制就類比推一下就可以了。如果這個看不懂的話就不要參加初賽了，50塊錢買點啥不好...任意進制轉(zhuǎn)十進制簡單說就是：按位轉(zhuǎn)，第i位的數(shù)字乘以要轉(zhuǎn)換的進制的n?1次冪即可。還是上圖：任意進制互相轉(zhuǎn)化這里考慮用十進制做中轉(zhuǎn)，先把A進制轉(zhuǎn)十進制，再把十進制轉(zhuǎn)B進制。關(guān)于小數(shù)的進制轉(zhuǎn)換十進制轉(zhuǎn)任意進制的小數(shù)不進行除法運算，而進行乘法運算后取整，取整后從前向后排列。任意進制轉(zhuǎn)十進制的小數(shù)只需要乘上負指數(shù)，最后算出來即可。各進制的字母表達H(Hexadecimal)——16進制D(Decimal)——10進制O(Octonary)——8進制B(Binary)——2進制二進制的相關(guān)知識二進制是計算機進行計算所使用的工具，自然也是非常?？嫉囊c。二進制的相關(guān)知識有許多，甚至算法中的位運算也是二進制的相關(guān)內(nèi)容，但為了過第一輪初賽，我們只介紹一些理論知識。關(guān)于位運算的相關(guān)知識請有興趣的同學自己學習。1、原碼顧名思義，原碼就是十進制數(shù)直接轉(zhuǎn)換成二進制之后直接形成的二進制編碼。2、補碼正數(shù)的補碼是本身，負數(shù)的補碼是其反碼加一。3、反碼顧名思義：正數(shù)的反碼是本身，負數(shù)的反碼是其除符號位之外的所有位按位取反的結(jié)果。附：ASCII碼ASCII碼的正規(guī)名稱是：美國信息交換標準代碼，是基于拉丁字母的一套電腦編碼系統(tǒng)。是最通用的信息交換標準。一共定義了128個字符。這里不賦ASCII碼的轉(zhuǎn)換表。只給出幾種比較常用的轉(zhuǎn)換：字符0→48大寫字母A→65小寫字母a→97空格→32換行→13位運算位運算不僅在初賽中是一個知識點分類，在復賽（即真正的程序設(shè)計與運用）的時候也有很大的一個應(yīng)用。而且，位運算的相關(guān)知識是計算機運算的靈魂，更是每個程序猿應(yīng)該理解的一種基本操作。關(guān)于位運算的相關(guān)知識，本蒟蒻在另一篇專門的博客中詳細的講解。常用的位運算技巧為了應(yīng)對初賽的筆試題，建議讀者在閱讀完這篇博客之后至少應(yīng)該掌握：各種位運算的運算法則以及位運算優(yōu)先級。另外，對于位運算的優(yōu)先級，本蒟蒻在后面的邏輯運算部分還會有詳細的解析。邏輯運算邏輯運算邏輯運算一共有三種，每種都有兩種寫法：邏輯非：！或┐邏輯與：&&或∧邏輯或：||或∨邏輯運算的優(yōu)先級非>>與>>或位運算+邏輯運算的優(yōu)先級邏輯非（！，┐）=按位反（~）>位移運算（<<,>>）>不等號（>=,<=）>等號（==,!=）>按位與（&）>按位異或（^）>按位或（|）>邏輯與（&&，∧）>邏輯或（||，∨）邏輯表達式由邏輯運算復合而成，只有兩種結(jié)果：true和false，在C/C++中，返回的值以0表示假，以1表示真。條件表達式條件表達式的基本形式如下：<表達式1>？<表達式2>：<表達式3>其表達意義是：如果表達式1成立，則執(zhí)行表達式2，否則執(zhí)行表達式3。其實也等價于if?elseif?else條件語句。例如下：#defineMin(a,b)a<b?a:b注意：如果條件表達式有多個進行復合，那么在執(zhí)行的時候需要從由往左依次判斷最后得出一個結(jié)果。即：右結(jié)合性。比如：<表達式1>？<表達式2>：<表達式3>？<表達式4>：<表達式5>那么，在執(zhí)行的時候是從3開始判斷是否為真，然后執(zhí)行某一個表達式，依次向上回溯。圖論理論知識基本概念完全圖：任意兩點都有邊相連，我們很容易推出來，一張完全圖的邊數(shù)為（n為節(jié)點個數(shù)）n×(n?1)2連通圖：顧名思義，連通圖就是連通的圖，即任意兩點都能直接或間接到達，這就區(qū)別于完全圖必須直接用邊到達的定義。樹：emm...直觀來講，就是一張長得像樹的圖。定義是任意兩點之間的簡單路徑有且只有一條。樹是一棵連通且無環(huán)的圖。它的邊數(shù)是n?1。二叉樹的遍歷二叉樹有不同的遍歷方式，一般來講，我們將其分成三類：先序遍歷（也叫先根遍歷）、中序遍歷（中根遍歷）以及后序遍歷（后根遍歷）。先序遍歷：遍歷方式如下：根—左兒子—右兒子中序遍歷：遍歷方式如下：左兒子—根—右兒子后序遍歷：遍歷方式如下：左兒子—右兒子—根我們用一張圖來理解一下這幾種遍歷方式。這張圖的先序遍歷：1245367中序遍歷：4251637后序遍歷：4526731一個推論：先序遍歷+中序遍歷=一棵確定的二叉樹后序遍歷+中序遍歷=一棵確定的二叉樹先序遍歷+后序遍歷=啥也不是特殊二叉樹及其性質(zhì)完全二叉樹：只有最后一層不是滿的，且最后一層的所有節(jié)點均集中在左側(cè)。圖例如下：滿二叉樹：節(jié)點個數(shù)已滿。圖例如下：特殊二叉樹的性質(zhì)：1、對于一棵完全二叉樹來講，它的葉子節(jié)點為n，則節(jié)點總數(shù)為2×n?1。此結(jié)論可逆。2、對于一棵滿二叉樹來講，它的層數(shù)（深度）為k，則它的節(jié)點總數(shù)為2k?1。此結(jié)論可逆。拓撲排序本蒟蒻有一篇專門講拓撲排序的講解：拓撲排序詳解簡單數(shù)據(jù)結(jié)構(gòu)基本理論1、棧想象一個桶，你從上面往里扔磚，然后你想把某一塊磚拿出來，你需要先拿出來你后扔進去的磚。這就是棧。棧的基本原則是：后進先出來一發(fā)圖示？附：前、中、后綴表達式一篇專門的博客：淺談前、中、后綴表達式2、隊列想象你在排隊買票，這個隊伍中的人都非常有素質(zhì)，都自覺排隊而且不會提前離開隊伍。這樣就只能從隊首買完票再離開，從隊尾進入隊伍。隊列的基本原則是：先進先出。再來一發(fā)圖示：3、鏈表鏈表分兩種：單向鏈表和雙向鏈表。關(guān)于鏈表，我有一篇專門講解的博客。有興趣的讀者請戳：鏈表詳解4、字符串字符串子串的概念：字符串是一串字符（廢話），它的子串被定義為：字符串中任意個連續(xù)的字符組成的子序列。字符串子串個數(shù)的計算公式：n×(n+1)2+1（就是字符串長度等差數(shù)列）如果是非空子串，就把那個一減去即可（子串個數(shù)的公式加一就是考慮空子串的情況）。時空復雜度的計算時間復雜度：漸進時間復雜度用符號O

表示。一個程序的語句執(zhí)行次數(shù)可以用一個代數(shù)式表示，那么我們?nèi)∵@個代數(shù)式的最高次項且忽略此項系數(shù)作為時間復雜度。如果一個程序的語句執(zhí)行次數(shù)為

2n3+3n2+n+7，那么這個程序的漸進時間復雜度為O(n3)。計算非遞歸程序的時間復雜度：簡單粗暴，數(shù)循環(huán)。常數(shù)：常數(shù)即為我們忽略掉的OO中最高次項的系數(shù)與低次項所帶來的時間消耗?？臻g復雜度：類比時間復雜度?？撮_空間開了多大。計算空間占用量：根據(jù)我們以上說過的計算機存儲單位的知識：一個int占用的內(nèi)存是4B，所以我們把開的int乘上4，再除以1024就是KB，同理，再除1024就是MB。公式：n為元素個數(shù)，M為最終答案（以MB為單位）M=4n1024×1024PS:一般來講，比賽中所給的256MB內(nèi)存可以開6×107個int類型的變量。另外，大數(shù)組必須開全局變量。如果扔在主函數(shù)里極容易爆棧。數(shù)學、邏輯學及運籌學知識排列組合：排列組合是每年必考知識點。但