CSP初賽知識點復習

10CSPCSP-J/S〔初賽學問點精講NOIP〔全國青少年信息學奧林匹克競賽〕于2022年取消。取而代之的是由CCF推出的非CSP?J/SCSP〔NOIP初賽〕常常使某些大神對根底學問不太了解無緣復賽...以今日學習下初賽學問點。信息學史及根本學問一、信息學及計算機史計算機的頂級獎項：圖靈獎、馮計算機的頂級獎項：圖靈獎、馮·諾依曼獎圖靈獎：由ACM〔美國計算機協(xié)會〕圖靈獎：由ACM〔美國計算機協(xié)會〕1966年。是“計算機界的諾貝爾獎”。馮IEEE設立。對信息科學做出突出奉獻的大神：圖靈〔所以才有個獎〕，馮諾伊曼中國獲圖靈獎的大神：姚期智〔清華就有姚班，就是以他的名字命名的〕世界第一臺電子計算機：埃尼阿克〔ENIACENIAC〕，1946214日在美國賓夕法尼亞大學誕生。又被叫做電子管計算機。賓夕法尼亞大學誕生。又被叫做電子管計算機。二、關于編程二、關于編程編程語言：編程語言：分兩類：面對對象和面對過程。分兩類：面對對象和面對過程。高級語言和低級語言的區(qū)分：高級語言和低級語言的區(qū)分：高級語言更簡潔移植。常見低級語言：常見低級語言：匯編匯編面對對象的高級語言：面對對象的高級語言：C++C++，Java，EIFFEL，Simula67等。面對過程的高級語言：面對過程的高級語言：CC，F(xiàn)ortran語言。遞歸編程：遞歸編程：于解決很多的計算機科學問題。簡潔來講，就是于解決很多的計算機科學問題。簡潔來講，就是“自身調用自身”〔在函數(shù)中〕。PP類/NP類/NPC類問題：1、P類問題：假設一個問題能找到一個在多項式時間內(nèi)解決它的算法，那么這個問題就是P問題。2、NP類問題：留意：NP問題P類問題，而是在多項式時間內(nèi)驗證一個解的問題。或者，我們可以將其理解為在多項式時間內(nèi)猜出一個解的問題。3、NPC類問題：定義如下：假設一個問題是NP問題，而且全部的NP問題都可以約化到它。那么它就是NPC類問題。再來介紹一下關于約化的定義：假設一個問題A可以約化為問題B，含義就是這個問題A可以用問題B的解法來解決。三、關于計算機先上張大圖：重要設備：硬件組成：重要設備：硬件組成：掌握器(Control):依據(jù)其要求進展掌握，調度程序、數(shù)據(jù)、地址，協(xié)調計算機各局部工作及內(nèi)存與外設的訪問等。運算器運算器(Datapath):算器的功能是對數(shù)據(jù)進展各種算術運算和規(guī)律運算，即對數(shù)據(jù)進行加工處理。存儲器存儲器(Memory):存儲器的功能是存儲程序、數(shù)據(jù)和各種信號、命令等信息，并在需要時供給這些信息。(Inputsystem:為外部設備，簡稱外設，輸入設備的作用是將程序、原始數(shù)據(jù)、文字、字符、掌握命令或現(xiàn)場采集的數(shù)據(jù)等信息輸入到計算機。常見的輸入設備有鍵盤、鼠標器、光電輸入機、磁帶機、磁盤機、光盤機等。輸出設備輸出設備(Outputsystem):出設備與輸入設備同樣是計算機的重要組成局部，它把外算機的中間結果或最終結果、機內(nèi)的各種數(shù)據(jù)符號及文字或各種掌握信號等信息輸出出來。微機常用的輸出設備有顯示終端CRT、打印機、激光印字機、繪圖儀及磁帶、光盤機等。CPUCPU及存儲：CPUCPU〔中心處理器〕=運算器+掌握器+存放器運算器=算術規(guī)律運算單元〔ALU〕及浮點運算單元〔FPU〕存儲器=內(nèi)存儲器+外存儲器BIOS是英文“BasicInputOutputSystem“縮略語，直譯過來后中文名稱就是“根本輸入輸出系統(tǒng)。其實，它是一組固化到計算機內(nèi)主板上一個ROM芯片上的程序，它保存著計算機最重要的根本輸入輸出的程序、系統(tǒng)設置信息、開機后自檢程序和系統(tǒng)自啟動程序。其主要功能是為計算機供給最底層的、最直接的硬件設置和掌握。隨機存儲器RAM的“隨機”指“隨時訪問”所以，我們登記來以下學問點：斷電后可以保存數(shù)據(jù)：硬盤，ROM斷電后不行以保存數(shù)據(jù)：顯存〔顯卡內(nèi)存〕，RAM，CPU計算機各存儲單位及進位關系：計算機各存儲單位及進位關系：計算機的存儲單位有以下幾種：計算機的存儲單位有以下幾種：TB/GB/MB/KB/B他們之間的進位關系為1024〔這應當是常識，沒打過競賽還沒玩過手機么？〕1B=8(bit，這里的bi是二進制下的一位內(nèi)存。進制及進制轉化十進制轉任意進制將十進制轉換成N進制，只需把十進制數(shù)每次除N求余數(shù)，然后把余數(shù)逆序寫出來?？床欢涂磮D：50塊錢買點啥不好...任意進制轉十進制簡潔說就是：按位轉，第i位的數(shù)字乘以要轉換的進制的n1次冪即可。還是上圖：任意進制相互轉化這里考慮用十進制做中轉，先把A進制轉十進制，再把十進制轉B進制。關于小數(shù)的進制轉換十進制轉任意進制的小數(shù)不進展除法運算，而進展乘法運算后取整，取整后從前向后排列。任意進制轉十進制的小數(shù)只需要乘上負指數(shù)，最終算出來即可。各進制的字母表達H(Hexadecimal)——16進制D(Decimal)——10進制O(Octonary)——8進制二進制的相關學問論學問。關于位運算的相關學問請有興趣的同學自己學習。1、原碼1、原碼顧名思義，原碼就是十進制數(shù)直接轉換成二進制之后直接形成的二進制編碼。顧名思義，原碼就是十進制數(shù)直接轉換成二進制之后直接形成的二進制編碼。2、補碼2、補碼正數(shù)的補碼是本身，負數(shù)的補碼是其正數(shù)的補碼是本身，負數(shù)的補碼是其反碼加一。3、反碼3、反碼顧名思義：正數(shù)的反碼是本身，負數(shù)的反碼是其除符號位之外的全部位按位取反的結果。附：ASCII碼ASCII美國信息交換標準代碼最通用的信息交換標準。一共定義了128個字符。這里不賦ASCII碼的轉換表。只給出幾種比較常用的轉換：0→48A→65a→97空格→32換行→13位運算〔即真正的程序設計與運用的時候也有很一種根本操作。關于位運算的相關學問，本蒟蒻在另一篇特地的博客中具體的講解。常用的位運算技巧各種位運算的運算法則以及位運算優(yōu)先級。會有具體的解析。規(guī)律運算規(guī)律運算規(guī)律運算一共有三種，每種都有兩種寫法：規(guī)律非┐規(guī)律與：&&或∧規(guī)律或：||或∨規(guī)律運算的優(yōu)先級非>>與>>或位運算+規(guī)律運算的優(yōu)先級規(guī)律非〔！，┐〕=按位反〔~〕>位移運算〔〕>不等號〔〕>等號〔==,!=〕>按位與&〕>按位異或^〕>按位或〔〕>規(guī)律與&&，∧〕>規(guī)律或〔|，∨〕規(guī)律表達式tru和fals，在C/C++中，返回的值以01表示真。條件表達式條件表達式的根本形式如下：<1>？<2>：<3>123。其實也等價于if?elseif?else條件語句。例如下：#defineMin(a,b)a<b?a:b一個結果。即：右結合性。比方：<1>？<2>：<3>？<4>：<5>那么，在執(zhí)行的時候是從3開頭推斷是否為真，然后執(zhí)行某一個表達式，依次向上回溯。圖論理論學問根本概念完全圖：任意兩點都有邊相連，我們很簡潔推出來，一張完全圖的邊數(shù)為〔完全圖：任意兩點都有邊相連，我們很簡潔推出來，一張完全圖的邊數(shù)為〔n為節(jié)點個數(shù)〕n×(n?1)2n×(n?1)2連通圖連通圖：顧名思義，連通圖就是連通的圖，即任意兩點都能直接或間接到達，這就區(qū)別于完全圖必需直接用邊到達的定義。我們用一張圖來理解一下這幾種遍歷方式。這張圖的先序遍歷：我們用一張圖來理解一下這幾種遍歷方式。這張圖的先序遍歷：1245367中序遍歷：4251637后序遍歷：4526731樹：emm...直觀來講，就是一張長得像樹的圖。定義是任意兩點之間的簡潔路徑有且只有一條。樹是一棵連通且無環(huán)的圖。它的邊數(shù)是n?1。二叉樹的遍歷二叉樹的遍歷二叉樹有不同的遍歷方式，一般來講，我們將其分成三類：先序遍歷〔也叫先根遍歷〕、中序遍歷〔中根遍歷〕以及后序遍歷〔后根遍歷〕。先序遍歷：遍歷方式如下：根—先序遍歷：遍歷方式如下：根—左兒子—右兒子中序遍歷：遍歷方式如下：左兒子—根—右兒子后序遍歷：遍歷方式如下：左兒子—右兒子—根一個推論一個推論：圖例如下：圖例如下：滿二叉樹：節(jié)點個數(shù)已滿。先序遍歷+中序遍歷=一棵確定的二叉樹后序遍歷后序遍歷+中序遍歷=一棵確定的二叉樹先序遍歷先序遍歷+后序遍歷=啥也不是特別二叉樹及其性質特別二叉樹及其性質完全二叉樹：只有最終一層不是滿的，且最終一層的全部節(jié)點均集中在左側。完全二叉樹：只有最終一層不是滿的，且最終一層的全部節(jié)點均集中在左側。圖例如下：圖例如下：特別二叉樹的性質特別二叉樹的性質：11、對于一棵完全二叉樹來講，它的葉子節(jié)點為n2×n?1。此結論可逆。2、對于一棵滿二叉樹來講，它的層數(shù)〔深度k2k?1。此結論可逆。拓撲排序本蒟蒻有一篇特地講拓撲排序的講解：拓撲排序詳解簡潔數(shù)據(jù)構造根本理論1、棧。這就是棧。棧的根本原則是：后進先出來一發(fā)圖示？11附：前、中、后綴表達式一篇特地的博客：淺談前、中、后綴表達式2、隊列樣就只能從隊首買完票再離開，從隊尾進入隊伍。隊列的根本原則是：先進先出。再來一發(fā)圖示：3、鏈表戳：鏈表詳解4、字符串字符串子串的概念：字符串是一串字符〔廢話〕，它的子串被定義為：字符串任意個連續(xù)的字符組成的子序列。字符串子串個數(shù)的計算公式：12〔就是字符串長度等差數(shù)列〕假設是非空子串，就把那個一減去即可〔子串個數(shù)的公式加一就是考慮空子串的狀況〕。時空簡單度的計算時間簡單度時間簡單度：漸進時間簡單度用符號O表示。一個程序的語句執(zhí)行次數(shù)可以用一個代數(shù)式表示，那么我們?nèi)∵@個代數(shù)式的最高次項且無視此項系數(shù)作為時間簡單度。假設一個程序的語句執(zhí)行次數(shù)為2n3+3n2+n+7O(n3)。計算非遞歸程序的時間簡單度計算非遞歸程序的時間簡單度：簡潔粗暴，數(shù)循環(huán)。常數(shù)常數(shù)：常數(shù)即為我們無視掉的OO中最高次項的系數(shù)與低次項所帶來的時間消耗。空間簡單度空間簡單度：類比時間簡單度?？撮_空間開了多大。計算空間占用量計算空間占用量：依據(jù)我們以上說過的計算機存儲單位的學問：一個int占用的內(nèi)存是4B，所以我們把開的int41024就是KB1024MB。公式：公式：n為元素個數(shù)，M為最終答案〔以MB為單位〕M=4n1024×1024PS:256MB6×107個int類型的變量。另外，大數(shù)組必需開全局變量。假設扔在主函數(shù)里極簡潔爆棧。數(shù)學、規(guī)律學及運籌學學問數(shù)學、規(guī)律學及運籌學學問 排列組合：排列組合是每年必考學問點。但是這是一個比較大