NOIP2018TG 初赛复习
Date： 20180911
TCP/IP OSI7
面向對象的程序設計語言
1.不是自頂向下
2.simula 67語言 第一個
3.繼承性、封裝性、多態性
NOIP支持的語言環境：
對于c / c++ ：Dev-Cpp \ RHIDE (DJGPP) （推薦：Dev-Cpp）
對于pascal： free pascal IDE \ Lazarus \ Dev-Pascal \ （推薦 Lazarus）
隨機化快速排序
Date 20180912
82.5
Huffman 編碼 合法性驗證
一定是完全二叉樹，或者單邊二叉樹
Prime 算法
每一次保證最小生成樹集合 U 中是聯通的
每一次 每個點到集合 U 的距離最短的加入，
由于這個點更新，迭代各個點到集合的距離
CPU 全稱中央處理器，最早不是Intel發明，運行速度不能比較（內因外因）
OSI7 是上下傳輸，層層向下，層層向上，傳輸協議TCP/IP
TCP 傳輸控制協議 IP 因特網互聯協議
域名-->IP 反映射不行
HTML語言
但是各種連接形式自己有自己的編碼，
超鏈接就是隱含URL，超鏈接連接內部資源也可以
NOI競賽的規則（初賽帶的物品、復賽帶的物品）
初賽：
選手進入考場時，只許攜帶筆、橡皮等非電子文具入場。禁止攜帶任何電子產品或機器設備入場，無存儲功能的手表除外；手機（關機）、U盤或移動硬盤、鍵盤、鼠標、鬧鐘、計算器、書籍、草稿紙及背包等物品必須存放在考場外。
復賽:
NOIP復賽時，選手須同時攜帶個人有效身份證件、NOIP準考證入場。
選手進入考場時，只許攜帶筆、橡皮等非電子文具入場。禁止攜帶任何電子產品或機器設備入場，無存儲功能的手表除外；手機（關機）、U盤或移動硬盤、鍵盤、鼠標、鬧鐘、計算器、書籍、草稿紙及背包等物品必須存放在考場外。
（ NOIP2009 TG 問題解決T1）
{ 1 2 3 4 6 7} 和 {8,9} 兩個集合考慮
1,2,3,4,7,6
1,2,3,7,4,6
兩種可能
在1后插入5,
6種可能
2*6=12
8在9前插入就對于普遍序列
{1,2,3,4,7,6,5}
有（1+2+3+...+8）=36
答案就是12*36=432
（ NOIP2009 TG 問題解決T2）
轉為7進制忘了轉回來了GG
不能轉進制！！！
7^3=343 7^2=49 7=7 1=1
顯然大的盡量去取
10015/343=29 余 68
68=49+7+7+7+7+1
29+6=35
Date：20180913 NOIP2009
80.5
1. Linux 沒有后綴名
.com和.exe 都是 windows下的后綴名
2. 7*7=41 在十進制下7*7=49顯然未知的進制一定大于10
一個個嘗試發現 (7)_12 * (7)_12 =(41)_12
所以在(12)_12 = (14)_10
所以 (12)_12 * (12)_12 = (14)_10 * (14)_10=（196）_10 = （144）_12
答案是 144
3. R1 R2 R3 R4 R5 第一個出棧的是R3
于是
Stack R1 R2
Out R3
In R4 R5
所以最后一個出棧的是R1 R4 R5 都可以
4. 插入排序 （原地排序）
數據范圍==數據規模
5.拓撲排序
1）有環圖不可以有拓撲排序
2）拓撲排序不是唯一確定的
3）圖可以使不連通的所以入度為0的點可能有多個注意！！！
6. +0和-0的補碼都是0000 0000，（取反+1符號位被進掉）
+0 和-0的源碼有2個： 1000 0000 ； 0000 0000
7.（問題求解 T2）二分圖沒奇數環，左邊點數為n，右邊定點為（7-n）
答案 y= （7-n）*(n) n=3或者4 最大答案為 12
8.哈密爾頓圖 暴力dfs n！ 就是經過一個路經過每個點恰好一次
Date：20180916 NOIP2011
1.
|運算 ：有一個是1就是1否則為0
^運算：相同為1不同為0，其中，x^0=x
&運算：全相同為1，不同為0
2.
快速排序最優時間復雜度O(n log n)，
最差時間復雜度O(n^2) ，
平均時間復雜度O(nlogn)，
運用快速排序求K大值是O(n)最好：就是K在正中間掃一遍
3.
2017年：
(Association for Computing Machinary,ACM)提名斯坦福大學前總裁約翰·L·軒尼詩（ John L. Hennessy）
以及加州大學伯克利分校退休教授大衛·A·帕特森（David A. Patterson）為2017年度ACM圖靈獎獲得者，
4.
2017 年 10 月 3 日北京時間 17 點 45 分許，美國物理學家雷納·韋斯（Rainer Weiss）、基普·索恩（Kip Thorne）和巴里·巴里什（Barry Barish），
因構思和設計激光干涉儀引力波天文臺 LIGO，對直接探測引力波做出杰出貢獻，榮獲2017年諾貝爾物理學獎
5.
與信息技術有關的獎項：約翰·馮諾依曼獎 圖靈獎 王選獎 D-Link榮膺PC Magazine杰出技術獎
6.
實數之所以能表示很大的數字是因為采用階碼
double型 實數之所以能精度很大是因為采用較長的尾數
7.
移動元素至有序想想最長上升子序列
交換任意元素多想想環
交換相鄰元素多想想逆序對
8.
高精度乘法要打！
9.
看程序題目如果比較惡心不是遞歸題，想想規律！
如NOIP2011 TG T4 就是枚舉出0-2^(n-1) 2^n個數字
然后每個數字看看和其他數字差多少位
分析：n(0)=n(1)=2^(n-1)
每位不同一定有2^(n-1)個無論是1/0
每個數字都有n個位數，就是n*2^(n-1)
共有2^n個數字，答案就是有2^n*n*2^(n-1)=n*2^(2n-1)
方法：其實就是小數據找找規律。。
?Date：2018-09-17
NOIP2012
1.
P問題：在多項式時間（空間）內可解的問題
NP問題：可以在多項式的時間里驗證一個解的問題
NPC問題：可以存在多項式時間的算法的NP問題
Hint：
NP問題不是非P類問題
所有的P類問題都是NP問題
一般來看 NP!=P
2. 本題中，我們約定布爾表達式只能包含p,q,r三個布爾變量，
以及“與“（^）、”或“（v）、”非“（~）三種布爾運算。
如果無論p,q,r如何取值，兩個布爾表達式的值總是相同，則稱它們等價。
例如，(pVq)Vr和pV(qVr)等價，pV~p和~qVq也等價，而pVq和p^q不等價。
那么，兩兩不等價的布爾表達式最多有_______個。
腦洞題1：對于p、q、r三個變量，每個變量可取0,1兩種取值，共有8種組合。
???????????? 對于每種組合，代入表達式只有0和1兩種答案。
? ? ? ? ? ?? 因此兩兩不等價的表達式只有2^8=256種。
3.對于一棵二叉樹，獨立集是指兩兩互不相鄰的節點構成的集合。
例如圖1有5個不同的獨立集（1個雙點集合，3個單點集合，1個空集），
圖2有14個不同的獨立集，那么，圖3有_____________個不同的獨立集。
腦洞題2：樹形DP
f[u][0]：u為根，不取u總數
f[u][1]：u為根，取u總數
f[u][0]=f[v_left][1]*f[v_right][1]
f[u][1]=f[v_left][0]*f[v_right][0]
ans=f[top][1]+f[top][0]=5536
?
Date 20180922
1.一般來說根節點默認深度是1
2.IPv4合法性：（內網）保留字192. / 172. / 10. 其余要在[0，255]內
3.高級語言解析方式有兩種：解釋程序（一般不生成.exe）、編譯程序（生成.exe）
4.mod運算 首先滿足 a%b=(a-[a/b]*b)其中[]為取整符號
其次mod運算的 值 的正負性同 a的正負性
如 13%(-3)=-4..+1 所以 13%(-3)=1
（-13）%3=-4..-1 所以（-13）%3=-1
轉載于:https://www.cnblogs.com/ljc20020730/p/9630530.html
總結
以上是生活随笔為你收集整理的NOIP2018TG 初赛复习的全部內容，希望文章能夠幫你解決所遇到的問題。
