初賽復習知識點

-

• 初賽復習知識點
• • @[TOC](-)
  • 一些盆友的初賽總結
  • 邏輯運算
  • 計算機基本結構
  • 卡特蘭數
  • 二叉樹的基本概念
  • 遍歷二叉樹
  • 二叉樹的性質
  • 圖的一些定義和概念
  • 關于 ∏ \prod ∏
  • 十進制轉二進制（小數部分）
  • NOI競賽歷史
  • 原碼反碼補碼
  • 因特網提供的服務
  • 整形資料與位元組
  • 鏈表

一些盆友的初賽總結

(T)JH姐的初賽總結
??????????
LTH 大 佬 {\color{white}大佬} 大佬的初賽提綱?
???????????

邏輯運算

& (并且) 有false則false
| (或者) 有true則true
! (非) 非false則true，非true則false
^ (異或) 相同為false，不同為true
&& (短路與) 有false則false,若&&左邊運算式或者值為false則右邊不進行計算
|| (短路或) 有true則true,若||左邊運算式或者值為true則右邊不進行計算

計算機基本結構

ROM（只讀存盤器）只能讀出無法寫入資訊，資訊一旦寫入后就固定下來，即使切斷電源，資訊也不會丟失，所以又稱為固定存盤器
RAM（隨機存取存盤器）即一旦斷電所存盤的資料將隨之丟失，RAM在計算機和數字系統中用來暫時存盤程式、資料和中間結果
美國AMD半導體公司專門為計算機、通信和消費電子行業設計和制造各種創新的微處理器

卡特蘭數

卡特蘭數 C(2n,n)/(n+1)

h n = 1 n + 1 ( 2 n n ) h_{n}=\frac{1}{n + 1}\begin{pmatrix}2n\\n \end{pmatrix} hn?=n+11?(2nn?)

二叉樹的基本概念

?表示空二叉樹
O表示僅有根結點的二叉樹

遍歷二叉樹

前序遍歷（根左右）
中序遍歷（左根右）
后序遍歷（左右根）

二叉樹的性質

在二叉樹的第i層上最多有 2 i ? 1 2^{i-1} 2i?1個結點( k > = 1 k>=1 k>=1)
深度為k的二叉樹至多有 2 k ? 1 2^{k-1} 2k?1個結點( k > = 1 k>=1 k>=1)
對任意一棵二叉樹，如果其葉結點數為 n 0 n_{0} n0?，度為2的結點數為 n 2 n_{2} n2?則一定滿足： n 0 = n 2 + 1 n_{0} = n_{2} + 1 n0?=n2?+1
具有n個結點的完全二叉樹的深度為 f l o o r ( l o g 2 n ) + 1 floor(log_{2}^{n}) + 1 floor(log2n?)+1
對于一棵n個結點的完全二叉樹，對任一個結點(編號為i)，有兩種情況
1、如果 i = 1 i=1 i=1，則結點 i i i為根，無父節點；如果 i > 1 i>1 i>1，則其父節點編號為 i / 2 i/2 i/2
如果 2 ? i > n 2 * i > n 2?i>n，則結點i無左孩子(當然也沒右孩子，結點 i i i為葉結點）;否則左孩子編號為 2 ? i 2 * i 2?i
2、如果 2 ? i + 1 > n 2 * i + 1 > n 2?i+1>n，則結點 i i i 無右孩子；否則右孩子編號為 2 ? i + 1 2 * i + 1 2?i+1

圖的一些定義和概念

有向圖：圖的邊有方向，只能按箭頭方向從一點到另一點
無向圖：圖的邊沒有方向，可以雙向
結點的度：無向圖中與結點相連的邊的數目，稱為結點的度
結點的入度：在有向圖中，以這個結點為終點的有向邊的數目
結點的出度：在有向圖中，以這個結點為起點的有向邊的數目
權值：邊的“費用”，可以形象地理解為邊的長度
連通：如果圖中結點U,V之間存在一條從U通過若干條邊、點到達V的道路，則稱U、V是連通的
回路：起點和終點相同的路徑，稱為回路，或“環”
完全圖：一個n階的完全無向圖含有n * (n - 1) / 2 條邊；一個n階的完全有向圖含有n * (n - 1) 條邊
強連通分量：有向圖中任意兩點都連通的最大子圖；特殊地，單個點也算一個強連通分量

關于 ∏ \prod ∏

∏ k = 1 n \prod_{k=1}^{n} ∏k=1n? a k a_{k} ak?表示 a 1 a 2 ? ? ? a n a_{1}a_{2}···a_{n} a1?a2????an?

例如 ∏ k = 1 4 \prod_{k=1}^{4} ∏k=14?= (1 + 2)(2 + 2)(3 + 2)(4 + 2) = 3 × 4 × 5 × 6 = 360

十進制轉二進制（小數部分）

例子： ( 0.25 ) 10 (0.25)_{10} (0.25)10?

0.25 × 2 = 0.5 0.25 × 2 = 0.5 0.25×2=0.5 （整數部分為 0 ）
然后不要整數部分，變成 0.5 0.5 0.5
0.5 × 2 = 1.0 0.5 × 2 = 1.0 0.5×2=1.0（整數部分為 1 1 1）
然后不要整數部分，變成 0.0
結束，順著數，就是 ( 0.01 ) 2 (0.01)_{2} (0.01)2?

?

NOI競賽歷史

1984年，DXP：“計算機的普及要從娃娃做起，”，第一屆NOI舉辦

1995年，第一屆NOIP

1989年，IOI，保加利亞

1995年，WC

1999年，NOI網路同步賽

2007年，APIO

2011年，NOIP取消保送

2014年，CSP認證（Certified Software Professional，軟體能力認證）

2019年，CSP非專業級別的能力認證

原碼反碼補碼

原碼
第一位為符號位，正數為0，負數為1
后面就是接它的二進制數

反碼
正數的反碼就是它的原碼
負數的反碼就是它的原碼除符號位外取反
例如110010是原碼，那么反碼就是101101

補碼
正數的補碼和它原碼一樣
負數的補碼 = 它的反碼最后 + 1

因特網提供的服務

萬維網（www）：是一個全球規模的資訊服務系統

電子郵件（E-mail）：具體格式為（收件人郵箱名+@郵箱所在主機的域名）

檔案傳輸協議（FTP）：用于在計算機間傳輸檔案

遠程登錄（Telnet）：指通過Internet與其他主機連接

整形資料與位元組

編譯器可以dao根據自身硬體來選擇內合適的容大小，但是需要滿足約束：short和int型至少為16位，long型至少為32位，并且short型長度不能超過int型，而int型不能超過long型，這即是說各個型別的變數長度是由編譯器來決定的，而當前主流的編譯器中一般是32位機器和64位機器中int型都是4個位元組

鏈表

鏈表不是線性的.不需要事先計算存盤空間
因為他是一個一個結點連成的,.你要加一個結點,就增長一點空間.
插入洗掉不需要移動元素
所需空間與線性表長度成正比

就先寫到這吧，本蒟蒻會間斷更新的，，，記得多來康康