Acm競(jìng)賽常用算法與數(shù)據(jù)結(jié)構(gòu)

1、 常用算法 &數(shù)據(jù)結(jié)構(gòu) 浙江大學(xué)微軟技術(shù)俱樂(lè)部 彭鵬ACM競(jìng)賽11、競(jìng)賽中常見(jiàn)的16種題型 3、競(jìng)賽中基本的數(shù)據(jù)結(jié)構(gòu)與算法 2、時(shí)空復(fù)雜度的分析0、如何建立一支強(qiáng)隊(duì)？2如何建立一支強(qiáng)隊(duì)個(gè)人的能力理論(幾何, 數(shù)論, 動(dòng)態(tài)規(guī)劃, 圖論等)技術(shù)(編程)隊(duì)員能力上的互補(bǔ)某論壇，一無(wú)聊男yy的中國(guó)“夢(mèng)之隊(duì)”錢(qián)文杰（？） 反應(yīng)奇快，擅長(zhǎng)隨機(jī)化，貪心，NOI貪心王劉汝佳or吳嘉之 見(jiàn)多識(shí)廣，做過(guò)的題必別人見(jiàn)過(guò)的題多趙爽 上海交大的“割題手”3Leader/Coordinato(協(xié)調(diào)比賽進(jìn)程)Reader(發(fā)現(xiàn)題目隱諱的涵義)Thinker(邏輯能力強(qiáng), 收集其他隊(duì)員意見(jiàn))Programmer/Debugg

2、er(反應(yīng)快/穩(wěn),細(xì)心)Helper(協(xié)助比賽, 查錯(cuò), 驗(yàn)證數(shù)據(jù)等)一支強(qiáng)隊(duì)需要的角色4參考書(shū)籍主要參考書(shū)籍C+ Primer C+ 標(biāo)準(zhǔn)程序庫(kù)算法導(dǎo)論算法藝術(shù)與信息學(xué)競(jìng)賽組合數(shù)學(xué)計(jì)算幾何？ 歷屆國(guó)家集訓(xùn)隊(duì)論文 5時(shí)空復(fù)雜度的分析時(shí)間復(fù)雜度的分析空間復(fù)雜度的分析6函數(shù)增長(zhǎng)和運(yùn)行時(shí)間引用劉汝佳序列和字符串7常見(jiàn)題型Dynamic Programming(動(dòng)態(tài)規(guī)劃)Greedy(貪心) Complete Search(窮舉) Flood Fill (種子填充)8常見(jiàn)題型Shortest Path (最短路徑)Recursive Search Techniques (回溯）Minimum Span

3、ning Tree （最小生成樹(shù)）Knapsack（背包） 9常見(jiàn)題型Computational Geometry(計(jì)算幾何) Network Flow(網(wǎng)絡(luò)流) Eulerian Path (歐拉回路)Two-Dimensional Convex Hull (二維凸包)10常見(jiàn)題型BigNums (大數(shù))Heuristic Search(啟發(fā)式搜索) Approximate Search (近似搜索)Ad Hoc Problems(雜題) 1112枚舉法又叫窮舉法，它利用了計(jì)算機(jī)計(jì)算速度快且準(zhǔn)確的特點(diǎn)，是最為樸素和有效的一種算法。不是辦法的辦法但有時(shí)卻是最好的辦法13Pizza Anyone

4、? （ZOJ 1219）題目大意： 你需要為你和你的朋友們訂一個(gè)皮薩。每個(gè)朋友都會(huì)告訴你他們想和不想放進(jìn)皮薩里的東西。 你是否能訂一個(gè)皮薩，讓他滿(mǎn)足每個(gè)人至少一個(gè)條件。 假設(shè)一共有16種東西可以放進(jìn)皮薩。14 是個(gè)對(duì)計(jì)算機(jī)很小的數(shù)15貪心法(Greedy)矩陣胚理論（詳情請(qǐng)參考算法導(dǎo)論） 枚舉法的時(shí)間效率很低，貪心法恰恰與其相反。并且貪心法的程序也很好實(shí)現(xiàn)。 無(wú)數(shù)論文都指責(zé)貪心法往往得不到問(wèn)題的最優(yōu)解。 絕世高手與普通高手的差距所在。16棧和隊(duì)列棧：后進(jìn)先出（LIFO）隊(duì)列：先進(jìn)先出（FIFO）17字符串的輸入與輸出 或 char s100;scanf(%s,s); string a(s);S

5、tring a; cin a;C+常用頭文件字符串的讀入哪種讀入更快？在輸入數(shù)據(jù)達(dá)到1M時(shí)，cin，cout將比scanf , printf在速度上有明顯的劣勢(shì)18排序排序的種類(lèi)：交換排序，選擇排序，插入排序，堆排序希爾排序，快速排序，歸并排序，桶排序19用C+實(shí)現(xiàn)排序#include數(shù)組 asort( a , a + 5 );vector asort( a. begin() , a. end() );20并查集并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合的合并問(wèn)題。并查集的主要操作有1合并兩個(gè)不相交集合2判斷兩個(gè)元素是否屬于同一個(gè)集合3路徑壓縮21Parity(ceoi99)有一個(gè)01

6、序列,長(zhǎng)度=1000000000,現(xiàn)在有n條信息,每條信息的形式是a b even/odd。表示第a位到第b位元素之間的元素總和是偶數(shù)/奇數(shù)。你的任務(wù)是對(duì)于這些給定的信息，輸出第一個(gè)不正確的信息所在位置-1。信息的數(shù)目不超過(guò)5000。如果信息全部正確，即可以找到一個(gè)滿(mǎn)足要求的01序列，那么輸出n。22Parity(ceoi99)從整個(gè)01序列肯定是無(wú)法入手的，因?yàn)樗拈L(zhǎng)度高達(dá)109。從范圍比較小的n入手。也就是說(shuō)我們需要對(duì)信息進(jìn)行一些特殊的處理。a b even/odd，那么將元素b指向a-1，邊的權(quán)值是even/odd。下面我們由樣例來(lái)說(shuō)明一下這個(gè)處理方法。23Parity(ceoi99)（

7、肖天）建立sum數(shù)組，sumi表示從1到i之和是奇（true）還是偶（false），sum0=false。這樣題目中給的任意問(wèn)題（a,b）的答案都可以用sumb xor suma-1表示。開(kāi)始我們并不知道sum1.n的值，不妨設(shè)為false，這時(shí)任意suma,sumb都是獨(dú)立的。對(duì)于每對(duì)問(wèn)答(a,b,c)，都可以知道sumb xor suma-1=c,由此把sumb和suma-1聯(lián)系起來(lái)。這步操作可以用并查集完成，對(duì)于問(wèn)答（a,b,c）如果suma-1,sumb不屬于一個(gè)集合就把它們并起來(lái)，否則如果suma-1 xor sumb不等于c則說(shuō)明出現(xiàn)矛盾，輸出總句數(shù)，退出。對(duì)于不出現(xiàn)矛盾的sum數(shù)

8、組，對(duì)于每個(gè)集合分為兩個(gè)部分，我們指定其中一個(gè)部分為true，另一個(gè)部分為false，則可以確定sum數(shù)組，利用sumi xor sumi-1可以求出第i位的數(shù)字，由于不同集合之間沒(méi)有問(wèn)答出現(xiàn)，所以此數(shù)列是一可行解，證明算法正確。 24堆(優(yōu)先隊(duì)列)優(yōu)點(diǎn)： 實(shí)現(xiàn)簡(jiǎn)單動(dòng)態(tài)維護(hù)一組數(shù)據(jù)中最?。ù螅┑囊粋€(gè)數(shù)組維護(hù) 25例題: 積水一個(gè)長(zhǎng)方形網(wǎng)格包含了n*m塊地，每塊地上面有1個(gè)長(zhǎng)方體。每一個(gè)長(zhǎng)方形蓋住了一塊地，地的面積是1平方英寸。相鄰的地上的長(zhǎng)方體之間沒(méi)有空隙。一場(chǎng)大雨降臨了這個(gè)建筑物，在建筑物的某些區(qū)域有積水產(chǎn)生。給各方格高度, 求積水總量26分析定義每塊地上的長(zhǎng)方體的高度稱(chēng)為原始高度積滿(mǎn)水時(shí)的

9、水面高度稱(chēng)為積水高度（高于積水高度的水一定會(huì)流走，低于積水高度的水一定流不走）積水高度與原始高度之差為積水深度如果一個(gè)長(zhǎng)方體上不可能有積水，那么它的積水高度就等于它的原始高度。最外圈不能積水，積水高度等于原始高度27分析由外而內(nèi)計(jì)算。每次選取外圍的格子中積水高度最低的一個(gè)格子x，考慮它周?chē)性诰W(wǎng)格內(nèi)部的格子y想象不斷的往x和y里注水，但是x的積水高度固定（想象該高度處有一個(gè)小孔），因此如果y的原始高度不小于x的積水高度，那么它的積水高度就是它的原始高度如果y的原始高度小于x的積水高度，那么它的積水高度就等于x的積水高度每次用堆取出x進(jìn)行計(jì)算，O(mnlogmn)。28哈希表(Hash)理論上

10、查找速度最快的數(shù)據(jù)結(jié)構(gòu)之一缺點(diǎn)：需要大量的內(nèi)存需要構(gòu)造Key 29Hash表的實(shí)現(xiàn)數(shù)組沖突解決法開(kāi)散列法閉散列法C+ sgi stl 實(shí)現(xiàn)30Hash Key的選取數(shù)值：方法一：直接取余數(shù)（一般選取質(zhì)數(shù)M最為除數(shù)）方法二：平方取中法，即計(jì)算關(guān)鍵值的平方，再取中間r位形成一個(gè)大小為 的表是多少？31字符串：int ELFhash( char* key )unsigned int h = 0;while( *key )h = ( h 24;h &= -g;return h % M;方法二：ELFhash函數(shù)方法一： 折疊法：即把所有字符的ASCII碼加起來(lái)32二分搜索樹(shù)普通的二分搜索樹(shù)時(shí)間復(fù)雜度：

11、缺點(diǎn)： 容易出現(xiàn)不平衡的情況AVL Tree ， Splay tree , 紅黑樹(shù) 33樹(shù)堆(Treap)Treap = Tree + heap每次插入/刪除結(jié)點(diǎn)的時(shí)候，給結(jié)點(diǎn)隨機(jī)分配一個(gè)優(yōu)先級(jí)，讓Treap關(guān)于優(yōu)先級(jí)形成一個(gè)堆的同時(shí)，關(guān)于關(guān)鍵碼形成BST跳躍表、B樹(shù)34跳躍表（Skiplists）35線(xiàn)段樹(shù) 在一類(lèi)問(wèn)題中，我們需要經(jīng)常處理可以映射在一個(gè)坐標(biāo)軸上的一些固定線(xiàn)段，例如說(shuō)映射在OX軸上的線(xiàn)段。由于線(xiàn)段是可以互相覆蓋的，有時(shí)需要?jiǎng)討B(tài)地取線(xiàn)段的并，例如取得并區(qū)間的總長(zhǎng)度，或者并區(qū)間的個(gè)數(shù)等等。一個(gè)線(xiàn)段是對(duì)應(yīng)于一個(gè)區(qū)間的，因此線(xiàn)段樹(shù)也可以叫做區(qū)間樹(shù)。3637 Atlantis （ZOJ

12、1128） 一個(gè)平面被很多矩形覆蓋，矩形之間會(huì)相互疊加。輸出矩形覆蓋的總面積。38Atlantis （ZOJ 1128）線(xiàn)段樹(shù)矩形切割39矩形切割40字典樹(shù)( Trie )當(dāng)關(guān)鍵字是串的時(shí)候，理論上查找最快的數(shù)據(jù)結(jié)構(gòu)定義：保存字符串用的樹(shù)型數(shù)據(jù)結(jié)構(gòu)(多叉樹(shù)），其中每個(gè)節(jié)點(diǎn)表示一個(gè)公共前綴，單詞信息保存在相應(yīng)的頁(yè)節(jié)點(diǎn)里面。41給如下幾個(gè)單詞，構(gòu)造的單詞樹(shù)：An，Ant，All，AllotAlloy，Aloe，Are，Atebe版權(quán)歸浙江大學(xué)ACM領(lǐng)隊(duì)徐串所有轉(zhuǎn)載需保留此字樣42T9（ZOJ 1038）題目描述：手機(jī)有智能英文輸入法，他根據(jù)自己已有的詞匯表，即使你每個(gè)數(shù)字只按一次也可以猜出你要按的

13、是哪個(gè)單詞（方法就是從所有可能的串中選出出現(xiàn)概率最高的一個(gè)）。詞匯表:hell 3hello 4idea 8next 8super 3按435561是的響應(yīng)顯示iidhelhellhello43動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的時(shí)間效率極高。 動(dòng)態(tài)規(guī)劃的算法簡(jiǎn)潔，一般只用邊界和狀態(tài)轉(zhuǎn)移方程就可清晰地表示出進(jìn)行規(guī)劃的步驟；而因?yàn)橛辛诉@些用數(shù)學(xué)語(yǔ)言描述的天然材料，編程也較為方便。最重要的一點(diǎn)：動(dòng)態(tài)規(guī)劃不單是一種思想，也不單是一類(lèi)算法，它是思想方法和具體算法的混合物。 摘自徐靜動(dòng)態(tài)規(guī)劃的算法與實(shí)現(xiàn)44動(dòng)態(tài)規(guī)劃無(wú)后效性遞推法和記憶化搜索45深度優(yōu)先搜索(DFS)按照深度優(yōu)先的順序遍歷狀態(tài)空間，通常用遞歸或者棧來(lái)實(shí)現(xiàn)。

14、void dfs ( state , depth )if ( state = 結(jié)束狀態(tài) ）退出；枚舉所有可行狀態(tài)更新全局變量；dfs( newstate , depth + 1 );還原全局變量46寬度優(yōu)先搜索(BFS)如果代價(jià)和搜索樹(shù)深度成正比，那么可以通過(guò)廣度優(yōu)先搜索得到解。由于空間占用大，BFS用處不是很廣，一般只用在路徑尋找問(wèn)題中，但是一旦使用，將比深度優(yōu)先搜括看得多雙向?qū)挾葍?yōu)先搜索深度優(yōu)先和寬度優(yōu)先搜索比較47Prime Ring Problem （ZOJ 1457）A ring is compose of n circles as shown in diagram. Put nat

15、ural number 1, 2, ., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.Note: the number of first circle should always be 1. n (0 n 20) 48while ( !deque.empty() )state = deque0;deque.pop();枚舉所有可行狀態(tài)tempstate = 狀態(tài)改變(state);deque.push_back(tempstate);寬度優(yōu)先搜索(

16、BFS)寬度優(yōu)先搜索的框架49Winlinez (ZOJ 1591)Now we have a board of 9 * 9 grids, on which there are several beads. These beads have only seven colors, we number them 1 - 7. We define the empty grid to be zero. Each turn you can move any bead on the board to the destination where there is a route between them.

17、The route means that the bead can move up, down, left or right to the adjacent empty grid and may go on until it reaches the destination. After the moving, if there are five or more same-colored beads in a line (row, column, diagonal), they will all be eliminated.50博弈問(wèn)題 給定一個(gè)有向無(wú)環(huán)圖(X, F)，其中X是一個(gè)非空的點(diǎn)集(每

18、個(gè)點(diǎn)表示一個(gè)位置)，F(xiàn)是一個(gè)在集合X上的函數(shù)，對(duì)于集合X中的任意一個(gè)元素x，F(xiàn)(x)返回一個(gè)集合X的子集，即，F(xiàn)(x)表示了由一個(gè)位置x可以到達(dá)的位置。如果F(x)是空集，則稱(chēng)x是一個(gè)結(jié)束位置。 現(xiàn)在兩個(gè)人在這樣的一個(gè)有向圖上玩游戲，首先在一個(gè)初始位置x0上放置了一個(gè)棋子，然后他們將按照如下規(guī)則進(jìn)行游戲： 首先由選手I從初始位置x0進(jìn)行移動(dòng)。 兩個(gè)選手交替移動(dòng)。 在一個(gè)位置x，選手可以將棋子移到位置y上，其中yx。 如果輪到某一個(gè)選手移動(dòng)時(shí)棋子處在一個(gè)結(jié)束位置，那么這個(gè)選手就會(huì)因?yàn)闊o(wú)法繼續(xù)移動(dòng)棋子而被判輸?shù)暨@局游戲。 對(duì)于給定的有向圖和初始位置，請(qǐng)你判斷出選手I與選手II誰(shuí)會(huì)獲勝。 樓天城淺談

19、一類(lèi)博弈問(wèn)題的解法51局面局面局面終結(jié)局面局面估價(jià)函數(shù)Alpha-Beta剪枝52A Multiplication Game（）Stan和Ollie一起做游戲。游戲的內(nèi)容是將一個(gè)整數(shù)乘上到中的任一個(gè)數(shù)。Stan總是從開(kāi)始，然后兩個(gè)人交替相乘。在游戲開(kāi)始前，兩個(gè)人訂了一個(gè)數(shù)（1n4294967295 ),誰(shuí)先到達(dá)，誰(shuí)就是最后的勝利者。53最大公約數(shù)最小公倍數(shù)歐幾里得輾轉(zhuǎn)相除int gcd ( int a , int b)return b?gcd(b,a%b):a;int lcm ( int a , int b)return a / gcd (a , b) * b;54篩選法求質(zhì)數(shù)表Eratost

20、henes（埃拉托色尼）篩選法：每次求出一個(gè)新的素?cái)?shù)，就把n以?xún)?nèi)的它的所有倍數(shù)都篩去。在實(shí)現(xiàn)的時(shí)候，對(duì)于一個(gè)素?cái)?shù)p，只需要篩去 等就可以了，因?yàn)?已經(jīng)在q的第一個(gè)素因子被找到的時(shí)候被篩去了55#define N 100#define M 100int p M , plist = 0;int init()memset( p , 0 , sizeof( p ) );for ( int i = 2; i = N; i+ )if ( !p i )p plist+ = i;int del = i * i;while ( del a i + 1 & i = 0 ) i-; if ( i 0 ) retur

21、n 0; for ( Min = i + 1 , j = i + 2; j a i & a j a Min ) Min = j; swap( a i , a Min ); for ( int j = i + 1; j n; j+ ) for ( int k = j + 1; k a k ) swap( a j , a k ); return 1;61Catalan數(shù)將正邊形用對(duì)角線(xiàn)剖分成三角形的方法數(shù)通項(xiàng)公式62Fibonacci數(shù)Fibonacci數(shù)的O(lgn)實(shí)現(xiàn)63彩票 大街上到處在賣(mài)彩票，一元錢(qián)一張。購(gòu)買(mǎi)撕開(kāi)它上面的錫箔，你會(huì)看到一個(gè)漂亮的圖案。圖案有n種，如果你收集到所有n種彩票，

22、就可以得大獎(jiǎng)。請(qǐng)問(wèn)，在平均情況下，需要買(mǎi)多少?gòu)埐势辈拍艿玫酱螵?jiǎng)呢？ 64分析總結(jié)已有0個(gè)圖案: 拿1次就可以多搜集一個(gè)已有1個(gè)圖案: 平均拿n/(n-1)次就可多搜集一個(gè)已有k個(gè)圖案: 平均拿n/(n-k)次就可多搜集一個(gè)所以總次數(shù)為: n(1+1/2+1/3+1/n)65數(shù)值分析定積分計(jì)算(Romberg)多項(xiàng)式求根(牛頓法)線(xiàn)形方程組(高斯消元法)66生成樹(shù)問(wèn)題最小生成樹(shù)(MST)最大生成樹(shù) ?Prim算法Kruskal算法兩種算法的使用范圍67最短路問(wèn)題單源最短路徑問(wèn)題Dijkstra多源最短路徑問(wèn)題Floyd-WarshallBellman-ford68第n短路徑第二最短路徑：枚舉最短

23、路徑上的每條邊，每次刪除一條，然后求新圖的最短路徑，取這些圖的最短路徑。最短的一條即為第二最短路徑第n最短路徑可以在求解第n-1最短路徑的基礎(chǔ)上求解69Arbitrage (ZOJ 1092)題目大意:有很多很多種貨幣,每?jī)煞N貨幣之間都有一個(gè)匯率,問(wèn)是否能找到一種套匯(?)的方法70網(wǎng)絡(luò)流問(wèn)題特點(diǎn)： 2.較高的編程復(fù)雜度 3.較死板的構(gòu)造方法 1.較廣的使用范圍由于后面的兩個(gè)特點(diǎn)，網(wǎng)絡(luò)流算法已經(jīng)逐步淡出了高中信息學(xué)舞臺(tái)。但在競(jìng)賽中，網(wǎng)絡(luò)流算法仍占據(jù)著一席之地71網(wǎng)絡(luò)流模型若有向圖G=(V,E)滿(mǎn)足下列條件： 有且僅有一個(gè)頂點(diǎn)S，它的入度為零，即d-(S) = 0，這個(gè)頂點(diǎn)S便稱(chēng)為源點(diǎn)，或稱(chēng)為發(fā)

24、點(diǎn)。有且僅有一個(gè)頂點(diǎn)T，它的出度為零，即d+(T) = 0，這個(gè)頂點(diǎn)T便稱(chēng)為匯點(diǎn)，或稱(chēng)為收點(diǎn)。每一條弧都有非負(fù)數(shù)，叫做該邊的容量。邊(vi, vj)的容量用cij表示。則稱(chēng)之為網(wǎng)絡(luò)流圖，記為G = (V, E, C)72最大流最大流的定義求有向帶權(quán)圖G=(V,E,C)的一個(gè)流,它滿(mǎn)足容量限制條件 ，且原點(diǎn)提供的流量最大最大流解法Ford-Fulkerson methodPush-relabel algorithmRelabel-to-front algorithm算法導(dǎo)論第26章73最小費(fèi)用最大流給定網(wǎng)絡(luò)G=（V，E，C，W），求網(wǎng)絡(luò)上的一個(gè)流f，使得f是網(wǎng)絡(luò)的最大流，且每條弧的流量與費(fèi)用的乘

25、積加起來(lái)的總合帶上下界的最小費(fèi)用最大流最小費(fèi)用路算法消圈算法74網(wǎng)絡(luò)流算法（金愷） 難點(diǎn)：網(wǎng)絡(luò)流在具體問(wèn)題中的應(yīng)用，最具挑戰(zhàn)性的部分是模型的構(gòu)造，其次是算法的優(yōu)化。 構(gòu)造沒(méi)有現(xiàn)成的模式可依，只能根據(jù)題目的具體條件來(lái)分析。這需要對(duì)各種網(wǎng)絡(luò)流的性質(zhì)了如指掌，并且歸納總結(jié)一些經(jīng)驗(yàn)，發(fā)揮我們的創(chuàng)造性。一般來(lái)說(shuō)，用得最多的方法是拆點(diǎn)法。優(yōu)化是算法的重要環(huán)節(jié)，它并非朝夕之功就能提高的，必須靠經(jīng)驗(yàn)的積累。 75二分圖匹配問(wèn)題二分圖是一類(lèi)很重要的圖，它的頂點(diǎn)可以分成兩個(gè)集合X和Y，圖的所有邊一定是有一個(gè)頂點(diǎn)屬于集合X，另一個(gè)頂點(diǎn)屬于集合Y。76二分圖的最大匹配同類(lèi)結(jié)點(diǎn)不鄰接。圖的一個(gè)匹配是一些邊的集合，任意兩

26、條邊沒(méi)有公共端點(diǎn)。圖中包含邊數(shù)最多的匹配稱(chēng)為圖的最大匹配匈牙利算法網(wǎng)絡(luò)流解法（Hopcroft）77二分圖的最小覆蓋定理：二分圖中點(diǎn)對(duì)邊的最小覆蓋等于其最大匹配數(shù)。M個(gè)是足夠的。只需要讓它們覆蓋最大匹配的M條邊，則其它邊一定被覆蓋（如果有邊e不被覆蓋，把e加入后得到一個(gè)更大的匹配）M個(gè)是必須的。僅考慮形成最大匹配的這M條邊，由于它們兩兩個(gè)無(wú)公共點(diǎn)，因此至少需要M個(gè)點(diǎn)才能把它們覆蓋78二分圖的匹配二分圖的最佳匹配二分圖的完美匹配二分圖的完備匹配穩(wěn)定婚姻問(wèn)題79獨(dú)立集考慮圖G=（V，E）。S是V的一個(gè)子集，如果在S中任意兩個(gè)頂點(diǎn)在G中都不是鄰接的，那么S就是G的一個(gè)獨(dú)立集。如果在G中不存在具有|S

27、1|S|，則稱(chēng)S為G的最大獨(dú)立集80誘導(dǎo)子圖頂點(diǎn)-導(dǎo)出子圖另V1是圖G=(V,E)的頂點(diǎn)集V的子集,如果E1是E的子集,且邊(vi,vj)屬于E1,當(dāng)且僅當(dāng)vi和vj屬于V1,那么子圖G1=(V1,E1)就叫做G在頂點(diǎn)集V1上的導(dǎo)出子圖。如果vi和vj屬于V1，那么E中任何一條以vi和vj為端點(diǎn)的邊都屬于E181弦圖定理:如果一個(gè)圖的任何誘導(dǎo)子圖都不是K階環(huán)(K=4),那么該圖稱(chēng)為弦圖82Fishing Net (ZOJ 1015)判斷一個(gè)圖是否是弦圖?83計(jì)算幾何判兩條線(xiàn)斷相交判點(diǎn)在多邊性?xún)?nèi)部二維凸包叉乘84Online Judge的簡(jiǎn)稱(chēng)一種通過(guò)網(wǎng)絡(luò)信息交互在線(xiàn)判題的系統(tǒng)它模擬了ICPC比賽

28、真實(shí)的情況當(dāng)前世界上規(guī)模比較大的OJUVA ZOJURALUSACOOJ是什么85Zhejiang university online judge推薦使用：gcc + vivs2003/vs200586Submission Error - 提交使用了不正確的隊(duì)名、題號(hào)等。No Such Problem - 檢查題號(hào)有沒(méi)有填錯(cuò)？Compile Error - 程序不能通過(guò)編譯。Run Time Error - 程序運(yùn)行過(guò)程中出現(xiàn)非正常中斷。Memory Limit Exceeded - 內(nèi)存使用量超過(guò)裁判規(guī)定的上限。Output Limit Exceeded - 輸出數(shù)據(jù)量過(guò)大，多半死循環(huán)了Ti

29、me Limit Exceeded - 運(yùn)行超過(guò)時(shí)限還沒(méi)有得到輸出結(jié)果。Wrong Answer - 答案錯(cuò)誤。Presentation Error - 輸出格式不對(duì)，可檢查空格、回車(chē)等等細(xì)節(jié)。Accepted - 恭喜恭喜！Out Of Contest Time - 比賽已經(jīng)結(jié)束啦！Contest Rule Violation - 宣判極刑，參賽資格隨即被取消?？赡苁盏降姆答佇畔ǎ?7常見(jiàn)問(wèn)題long long vc+6.0 _int64gcc vc+7.0 long longprintf(“%lld”)在處理浮點(diǎn)數(shù)時(shí)，請(qǐng)選擇double讀入一行g(shù)ets() , getline()88ZOJ輸入輸出程序提交上去后，服務(wù)器（？）會(huì)編譯它（gcc),然后重新定向它的輸入輸出。所以，cod