前言：

快初賽了，以防萬一，整理了一些知識點

這數字Kobe This Is For You
友鏈：
CWH強無敵的初賽提綱
LTH牛逼格拉斯的初賽提綱
TJH毀天滅地的錯題集

1.計算機發展代別劃分

2.計算機硬體設備

由 存盤器、運算器、控制器、輸入設備、輸出設備 構成

存盤器：顧名思義就是用來存東西的可以分為兩大類，

運算器：運算器由算術邏輯單元（ALU）、累加器、狀態暫存器、通用暫存器組等組成，算術邏輯運算單元（ALU）的基本功能為加、減、乘、除四則運算，與、或、非、異或等邏輯操作，以及移位、求補等操作，

控制器：計算機的指揮系統，

輸入設備：比如：鍵盤、滑鼠、掃描儀、麥克風之類的，
輸出設備：比如：顯示幕、列印機、音箱之類的

3.進制之間的轉換

二進制：逢二進一
八進制：逢八進一
十進制：逢十進一
十六進制：逢十六進一不同的是，用ABCDEF代表10、11、12、13、14、15、

二進制轉十進制方法：“按權展開求和”
比如將 （ 1011.10 ） 2 （1011.10）^{2} （1011.10）2轉成十進制數

（ 1 1 1 * 2 3 2^3 23 + 0 0 0 * 2 2 2^2 22 + 1 1 1 * 2 1 2^1 21 + 1 1 1 * 2 0 2^0 20 + 1 1 1 * 2 ? 1 2^ {-1} 2?1 + 0 0 0 * 2 ? 2 2^{-2} 2?2）

（ 2 ? n 2^{-n} 2?n = 1 2 n \frac{1}{2^n} 2n1?)(n >= 0) 例如( 2 ? 1 2^{-1} 2?1 = 1 2 1 \frac{1}{2^1} 211? ）

（ 8 + 0 + 2 + 1 + 0.5 + 0 ） （8 + 0 + 2 + 1 + 0.5 + 0） （8+0+2+1+0.5+0） = ( 11.5 ) 10 (11.5)^{10} (11.5)10

十進制轉二進制方法：“除以2取余數然后逆序輸出”
比如將 （ 89 ） 10 （89）^{10} （89）10轉成二進制數

  2  |89
     ————
  2  |44      ....... 1
     ____
  2  |22      ....... 0
     ————
  2  |11      ....... 0
     ____
  2  |5       ....... 1
     ————
  2  |2       ....... 1
     _____
  2  |1       ....... 0
     _____
     0        ....... 1

然后倒著念就是 ( 1011001 ) 2 (1011001)^{2} (1011001)2

4.資訊編碼表示

1.編碼： 將各類資訊轉換成0和1，即二進制數，這一程序稱為編碼
2.資料： 能被計算機接受和處理的符號的集合稱為資料
3.位元：指1位二進制的數碼（0 或 1），位元是計算機中表示資訊的資料編碼中的最小單位
4.位元組：位元組表示一組連續二進制數，通常用8位2進制數表一個位元組，也就是1位元組=8位元
5.ASCII碼：
0 ~ 9 —— 48 ~ 57
A ~ Z —— 65 ~ 91
a ~ z —— 97 ~ 123

5.關于各種排序

6.計算機網路：

1.網路的定義：利用通信線路和設備，把分布在不同地理位置上的多臺計算機連接起來，
2.網路的分類：

3.IP地址：
用于標識Internet網路上節點的32位地址，
該地址通常由句點分隔的八位位元組的十進制數表示（例如：192.168.7.27）
IP地址的主機號的每個域取值范圍0~255，但主機ID所有域不能都為0或255.

7.原碼 補碼 反碼

原碼：
第一位代表符號位0為正，1為負
然后接他的二進制數
設x=11110001 則x原 = 011110001

反碼：
正數的反碼就是他的原碼
負數的反碼就是除了符號位（第一位）以外的數全都取反
例如1111010 的 反碼 就是 1000101

補碼：
正數的補碼就是他的原碼
負數的補碼符號位為1，數值各位取反，最低位+1

8.邏輯運算

非：！
與：&
或：|
異或 ：^

運算級比較
括號>非>與>或 和 異或

非：0變1,1變0；簡單記憶就是取反
與：有1為假必為假簡單來說就是只要有0就是0兩個1才是1
或：有1為真必為真簡單來說就是只要有1就是1兩個0才是0
異或：相同為0不同為1

9.堆疊

先進后出
例如：
入堆疊順序：1 3 2 4 5
出堆疊順序：5 4 2 3 1
可以這樣理解堆疊有口無肛門 = 嘔吐

10.佇列

先進先出
例如：
入隊順序：8 7 5 6 1 2 3
出隊順序：8 7 5 6 1 2 3
可以這樣理解佇列有口有肛門 = 拉米巴米巴

11.樹

1.定義：
每個元素稱為節點
有一個特定的節點，稱為根節點

2.基本概念：

就比如這張圖
節點1是根節點
這棵樹的深度為3
度：一個節點的兒子個數，
葉節點：度數為0的節點，例如節點4 5 6，

3 .樹的遍歷：
先序遍歷：根左右 拿上圖說 就是123456
中序遍歷：左根右 拿上圖說 就是425136
后序遍歷：左右根 拿上圖說 就是452631

4 .二叉樹的基本結構：
是一種度數為2的數，每個節點的子節點分別稱為左孩子，右孩子，它的兩顆子樹分別稱為左子樹，右子樹，
二叉樹可以為空，一定是有序的

5.二叉樹的性質：
在二叉樹的第i層有 2 i ? 1 2^{i-1} 2i?1個節點（i>=1）
深度為k的二叉樹至多有 2 k ? 1 2^{k-1} 2k?1個節點（k>=1）

6 .特殊的二叉樹：
1.滿二叉樹：深度為k且有 2 k ? 1 2^{k-1} 2k?1個節點
2.完全二叉樹：如果二叉樹的深度為k，則除第k層外其余所有層節點的度都為2，且葉子節點從左到右依次存在，也即是，將滿二叉樹的最后一層從左到右依次洗掉若干節點就得到完全二叉樹，滿二叉樹是一棵特殊的完全二叉樹，但完全二叉樹不一定是滿二叉樹

12.圖

1.什么是圖？：
一種資料結構，定義為G = （V,E）

2.圖的一些定義和概念：
1）：有向圖:圖的邊有方向（箭頭）

2）：無向圖:圖的邊沒有方向（雙向）

3）：結點的度：無向圖中與節點相連的邊的數量，稱為結點的度，
4）：結點的入度：有向圖中，以某個結點為終點的有向邊的數量，
5）：結點的出度：有向圖中，以某個結點為起點的有向邊的數量，
6）：權值：邊的“費用”，可以理解為邊的長度，
7）：連通：如果圖中結點U,V之間存在一條從U通過若干條邊或點到達V的通路，則稱為UV連通，
8）：回路：起點和終點相同的路徑稱為回路或環，
9）：強連通分量：有向圖中任意兩點都連同的最大子圖，

13 面向物件程式設計語言

Smalltalk，Eiffel, C++,java,PHP，C#
C是面向程序程式設計語言
面向程序程式才是“自頂向下，逐步求精”，而面向物件程式設計并不是，而是基于問題物件的自底向上的設計方法，
（就是物件是下到上，程序是上到下 ）

14.組合數學初步

卡特蘭數 = c ( 2 n , n ) ( n + 1 ) \frac{c(2n,n)}{(n+1)} (n+1)c(2n,n)?

「 一 些 理 論 性 的 東 西 」 「一些理論性的東西」 「一些理論性的東西」:

1.一個字串本質不同的子串（包含空串）的個數的方法
（ 子 串 長 度 + 1 ） ? 字 串 長 度 2 \frac{（子串長度 + 1）*字串長度}{2} 2（子串長度+1）?字串長度? ? - ? （ 重 復 字 母 的 個 數 + 1 ） ? 重 復 字 母 的 個 數 2 \frac{（ 重復字母的個數 + 1）*重復字母的個數}{2} 2（重復字母的個數+1）?重復字母的個數? + + + 1 1 1
例如：abcbcbc
本質不同的子串個數的方法：
（ 8 + 1 ） ? 8 2 \frac{（8 + 1）* 8}{2} 2（8+1）?8? ? - ? （ 3 + 1 ） ? 3 2 \frac{（3 + 1）* 3}{2} 2（3+1）?3? + + + 1 1 1 = = = 30 30 30

2.在32位作業系統中bool型陣列a[10000][10000]約占記憶體95MB bool型變數占一個位元組（ 8 8 8 個位元位 b i t bit bit）

3.存盤空間 = 像 素 ? 圖 象 位 數 8 \frac{像素*圖象位數}{8} 8像素?圖象位數?

4.NOIP的組織者是ccf，CSP的組織者也是ccf
在2019年由于某種原因 NOIP 停賽，一周后，CSP正式“接棒”，
2020年恢復NOIP，只有高中生可以參加NOIP（好像是?）
NOIP與CSP最大的關系好像就是交錢與不交錢吧

5.NOI競賽歷史
1984年，鄧x平：“計算機的普及要從娃娃做起，”，第一屆NOI舉辦
1995年，第一屆NOIP
1989年，IOI，保加利亞
1995年，WC
1999年，NOI網路同步賽
2007年，APIO
2011年，NOIP取消保送
2014年，CSP認證（Certified Software Professional，軟體能力認證）
2019年，CSP非專業級別的能力認證