集訓(xùn)隊(duì)作業(yè)ioi2007hom第二輪

1、中國國家集訓(xùn)隊(duì)第二輪WorldFinals給出由水平垂直線段組成的兩幅圖，判斷第一首先,可以證明至少存在一個(gè)方案使得有個(gè)幅圖有的交點(diǎn)(線段的的端點(diǎn)或線段的交點(diǎn))。因?yàn)槿绻硞€(gè)方案中沒有的交點(diǎn)，不管情況如何總可以通過平移、縮放來構(gòu)造一個(gè)有的交點(diǎn)的方案。然后說到具體做法，枚舉重復(fù)交點(diǎn)后，就要枚舉比例。設(shè)（小圖、（大圖）分別是通點(diǎn)交點(diǎn)的兩條水平線（兩條豎直線，然后隨便找小圖中的另一條水平線（豎直線），再枚舉C對(duì)應(yīng)于大圖中的（豎直線BD的間隔與C的間隔之比。注意到C與BD的間隔都有不能為。接下來就判斷小圖平移和縮放的圖與大圖的局部圖（與前者位置一樣）是不是相同?？偨Y(jié)：此題主要編程能力，分析能力，觀察能

2、力。為第二分局部放大得少有一個(gè)端點(diǎn)同時(shí)出現(xiàn)在兩幅圖中洗牌時(shí)每次最多犯一個(gè)錯(cuò)誤（交換兩張牌。給如果還是多解則輸出字典定理：在洗牌過程換了兩個(gè)牌 A、B 就等價(jià)于在最終結(jié)果換A、B。方法就是*IDA首先限定步數(shù) depth。接下來就枚舉次數(shù)。然后就進(jìn)行搜索。在搜索過程序中，需要的一個(gè)剪枝就是用當(dāng)前至少還需要的交換次數(shù)是否不超過還能交換次數(shù)。而至少需要的交換次數(shù)等于P是不進(jìn)行任何交換的洗牌結(jié)果。對(duì)于在搜索中所有已經(jīng)進(jìn)行的交換（A，B，在P 換A，B 的位置，得到新P。然后P 至少要交換多少次才能變而言之就是 52 減去置換中循環(huán)的個(gè)數(shù)給出邊與坐標(biāo)軸平行的簡分析一個(gè)圖可以覆蓋整個(gè)平面當(dāng)且僅當(dāng)找到六個(gè)點(diǎn)

3、 (包含 4 個(gè)點(diǎn)的情況)按順序的 A、B、C、D、E、F，ABED相同，BCFE相同，CD AF 相可以證明 A，C，E 中至少有兩個(gè)點(diǎn)在多邊形點(diǎn)上B，D，F(xiàn) 中至少有兩個(gè)點(diǎn)在多邊形的頂首先可以枚舉這個(gè)位于多邊形頂點(diǎn)上的點(diǎn)其余兩個(gè)再分情況求出來Wall Game用最少移動(dòng)棋子使得它們當(dāng)共線是行共線時(shí)，把所有的棋從按行從小到大排序。最優(yōu)的共線就是正中間的那個(gè)棋子所在的行。首先棋子通過上下移用都移到那一行。然后再將第一次棋當(dāng)共線是列共線時(shí)，方法與情況（1）類當(dāng)共線是主對(duì)角線時(shí)，對(duì)于每一個(gè)棋子主對(duì)角線上有連續(xù)的幾個(gè)格子是移動(dòng)距離最少的情況下該棋子走到對(duì)角線的位置。設(shè) i 個(gè)棋子走到對(duì)角線上的第i

4、到B i 走最短距離。不難發(fā)現(xiàn)，如果第i 走到K 個(gè)格子，而K 不在，B i就要多走- i|B |分配問題了?？紤]先分配第一個(gè)格子，再 K個(gè)格子，找出所到尚未分配的棋子的集合 。就分配這些這棋子中 B 值最小的棋子。SA 值最小的棋子,如果有多個(gè)A時(shí)間復(fù)雜度程序：找不WorldFinalsn*n*n 的積木有的地方空面顏色相同6 個(gè)方程序CERC任務(wù) A 人選的需任務(wù) B 需要小于平均 ，任務(wù) C 沒有限分析首先把所有的人分成兩個(gè)部分，一部分是大于等于平均的，另一部分的是小于平均的。在同一部分里，又分成多個(gè)連通塊。對(duì)于每一個(gè)連通塊，2T 染色，又成兩部分，其中必定有一部分在任務(wù)C 里。也就是說

5、通塊有兩個(gè)屬性哪一部分在任務(wù)C里。對(duì)于兩個(gè)不同的連通塊A、BA選擇某個(gè)屬性時(shí)，B就可能不能選擇某個(gè)屬性。這時(shí)，AB就以某種方式產(chǎn)生。這時(shí)又再次轉(zhuǎn)化為2-SAT。最后再通過簡單構(gòu)造輸出一個(gè)方狀態(tài)：無數(shù)據(jù)2n 個(gè)工廠分配到河一些工廠之間必須直，有兩架直升飛機(jī)可以分析有度為 1 的點(diǎn)后，連通塊就變成了一連鏈。算法對(duì)于每通分塊，首先看它是否符合上述性質(zhì)。如果不符合，就在剩余圖中嘗試刪去一條邊使之滿足以上的性質(zhì)，這時(shí)有兩種情況：所有節(jié)點(diǎn)的度都為，圖的形態(tài)就是O字形，刪去任意一邊；有一個(gè)點(diǎn)的度為，形態(tài)是就6字形，刪去與這個(gè)點(diǎn)相連并在環(huán)上的一邊就可以。如果還不符合，就在剩余圖中找到度最大的點(diǎn)，若該點(diǎn)的度D

6、4 （3 條邊就枚舉該點(diǎn)上要?jiǎng)h去的邊，枚舉后，做法與上述的相如果總共需要的刪去的邊不2就有解，輸出狀態(tài)：無數(shù)據(jù)測試數(shù)：CERC2005Round Table每次圓桌會(huì)議由至少 圓桌旁坐下后相鄰騎有多少個(gè)騎士不可能分析：不難發(fā)現(xiàn)，如果騎士A 到騎士B 之間有一個(gè)割點(diǎn)，那么它們倆是不可能組成會(huì)議的。因此，我 如果在同一個(gè)獨(dú)立的部分里，如果有奇環(huán)的話，也就是不是二分圖，那就這部分的騎士都可以參加會(huì)議，否則都不行。程序Wild每個(gè)人用一個(gè)三元組1=a,b,ca要么bb要么 如果求出這M*M 個(gè)(a,?,?)組合中不能戰(zhàn)勝黨的個(gè)數(shù)，就出（a,?,?）能戰(zhàn)勝黨的個(gè)數(shù)Pixel在一n*n 黑白圖象上做一個(gè)3

7、2個(gè)動(dòng)作pixel 算法：對(duì)于每個(gè)動(dòng)作，表示成一個(gè)置換。然后求這動(dòng)作序列對(duì)應(yīng)的置換的乘積P。然后求出P循環(huán)，再求出這些循環(huán)的長度的最大公約數(shù)。這最大公約數(shù)就是答案。0 必須先想好每一個(gè)操作對(duì)應(yīng)的置換。如果沒有相當(dāng)?shù)陌盐?，程序很可能?huì)寫錯(cuò)，這時(shí)的程序會(huì)相當(dāng)難調(diào)試。程序Word 把一些單詞組成一個(gè) word ring，每個(gè)單詞的后兩個(gè)字母與后一個(gè)單詞的前兩個(gè)字母為一個(gè)圖的結(jié)點(diǎn)。如果一個(gè)單詞的開頭兩個(gè)字母為 S1,S2,尾部兩個(gè)字母為 T1,T2。那么就在結(jié)點(diǎn)(S1,S2)然后二分答案 K。將圖中的每一條都減少 K，看有沒有正環(huán)。如果有正環(huán)，那么就說明答案大于 K，否則答案就小K。郭華陽的程CERC

8、2004Artof，每個(gè)國家的為首都所在發(fā)生 假設(shè)相鄰算法線段AB,BA。把這些有向線段都放到一個(gè)集S。對(duì)于 S 中的每一條有向線段 AB ，求出它的下有向線段NextAB)。它定義ABB順時(shí)針旋然后，對(duì)于每一條有向V，求Next（V為止。這時(shí)就求到一個(gè)環(huán)。求這一個(gè)環(huán)的有向面積 S如果 S 大于 0，這就說明這就一個(gè)多邊形的環(huán)接下來，還要求一個(gè)點(diǎn) P 所屬的環(huán)。我們定義這樣的環(huán)為包含的該點(diǎn)面積最小的環(huán)，設(shè)為Find(P。有時(shí)候，一個(gè)外部環(huán)可能被一個(gè)環(huán)所包圍。這時(shí)，該外部環(huán)與包圍它的 環(huán)是同類的。使用 對(duì)于CAPTICAL用FIND 求出它所在的環(huán)。把所有與該環(huán)同類的都標(biāo)記為CAPITAL。最后

9、，如果有兩個(gè)相反的有向線段 S 和 S，那么它們各自對(duì)應(yīng)的 CAPITAL 就是相鄰的。已編的程序PolishOlympiadinInformaticsPOIXIII2005-1-4Tetris 模擬一些長方體的下落，計(jì)算最后的高度這一個(gè)題了很好久好久，一直沒有想出來我問過很多的大牛，但是他們就是不能很好地用來表述最后我只好看郭華陽的程序去學(xué)二維線段樹我這才然大悟我看完郭華陽的程序后，發(fā)現(xiàn)我寫的一與郭華陽的有很大差別。我以前寫的一維線段樹一個(gè)節(jié)點(diǎn)有兩個(gè)信息：Same,TopTop表示該節(jié)點(diǎn)對(duì)應(yīng)的區(qū)間的最大高度，如果 Same 為真的話就表示該區(qū)間的高度Top。另外，如果一個(gè)節(jié)點(diǎn)的祖先有Same

10、 為真的情況，就取 same 為真的最高的祖先的值這樣的寫法有明顯的缺點(diǎn)，那就是節(jié)點(diǎn)具有傳遞一維線段樹的定義：而另一種寫法就是樹的每一個(gè)區(qū)間存兩個(gè)信息Cover 和 Top。表示某些覆蓋該節(jié)點(diǎn)的區(qū)間的最大高度，Top 表示的就是該節(jié)點(diǎn)對(duì)應(yīng)的子樹的最大 Cover 值。單個(gè) Cover的值不具有什么意義，并不表示該節(jié)點(diǎn)對(duì)應(yīng)的區(qū)最大高度一維線段樹操作 ：（1 ） 首先談?wù)劯采w操作 update_1（c,d,height height。對(duì)于底部區(qū)間a,b（底部區(qū)間指的是線段樹中的節(jié)點(diǎn)區(qū)間被c,d包含并且父親的區(qū)間不被 c,d包含，把其 cover 更新max(cover,height)，并且把祖先的

11、 Top 值也更新了。這樣的操作是完備的，就是說覆蓋操update_1D（c,d,height）的所有信已經(jīng)完全加入的線段(2) getmax_1D(c,d)：表c,dd的區(qū)間的最大高度。這始講二維線段樹。二維線段樹的每一個(gè)節(jié)P的對(duì)應(yīng)的區(qū)間a,b表示橫坐標(biāo)上界b、下界a 的矩形的具體信息。類似地，每一個(gè)節(jié)點(diǎn)上都Cover2，Top2，它們是以縱坐標(biāo)為離散對(duì)象的。Cover2是一棵一維線段樹，它的每一個(gè)節(jié)點(diǎn)區(qū)間c,dCover 表示某些覆c,d對(duì)應(yīng)的子樹的最大Cover值。Top2也是一棵線段樹，它的一個(gè)節(jié)點(diǎn)區(qū)間c,d的 cover 值表示是所有 P的子樹Cover2的節(jié)點(diǎn)區(qū)間c,dcover值

12、；其 Top 表示該節(jié)點(diǎn)c,d對(duì)應(yīng)的子樹的最大 Cover 值。二維線段樹操作：（1） 覆蓋操作 （ab,cd,height：表示把橫坐標(biāo)從 ab，縱坐標(biāo)從 cd Height。首先找出兩維線段樹中 ab Cover2 進(jìn)行 兒子節(jié)點(diǎn)的 Cover2 的底部區(qū)間的 Cover 更新為 Height ， 所 以 就 要 將 對(duì) Top2 進(jìn) 行 二 維 線 段 樹 操 作 ：（ 2 ） 詢 問 操 作 getmax2Db,c)。這等價(jià)于求與ab,c)矩形有交的二維線段樹中的oer2 的最大ovr 值。對(duì)于二維線段樹中底部區(qū)間，求它的子樹與ab,c)矩形有交的最大over 值就等價(jià)于求o2 中與(

13、abcd矩形有相的最大 or 值，也就是 對(duì)2 求 getmax1D(c,dve2中與(abcd矩形有相的最大cover 值就等于對(duì)ve2求geax_c,?？偟臅r(shí)間復(fù)雜度是 PASCAL程序：tet.pas郭華陽C+程序：tet.cpp2-1The給有向圖，求一條從 開始1 結(jié)束的連續(xù)頂點(diǎn)序列，或不存在參見問題2-3給一棵樹，用L條無公共點(diǎn)的路徑覆蓋盡量多的結(jié)點(diǎn)參見問題2-5給一n*m 網(wǎng)格，每每次切下一個(gè)寬度為 1slice，里面的數(shù)之和不得超過k每次切完后剩下的部分仍應(yīng)量少slice。分析：矩形被完全切掉時(shí)，矩形一定被切下 N 次橫 slice 或被切下 M 次豎 slice。假如被切下

14、N 次橫 slice，那么就可以認(rèn)為切下一個(gè)slice 的費(fèi)用0，切下一個(gè)slice 的費(fèi)用為 xi,j1N 行、i 列到j(luò) 列的矩形的最少費(fèi)用。由于橫 slice 是免費(fèi)的，應(yīng)該盡量的使slice。如果該矩形能夠只用slice，那么費(fèi)用就 0，否則就將矩形的上部、下部能橫 slice 都slice，剩下的子矩形如果最左列的總和不大于k，xi+1,j+1去更xi,j，如果最右列的總和不大于 k，那么 xi,j-1+1 去更新 xi,j。最后x1,m+n 去更新答案假如被切下 M 次豎 slice，分析與上述相似。2-6n 1n 之間的整數(shù)，把它變成 1n的排列。每個(gè)新數(shù) mi必須在區(qū)間ai b

15、i內(nèi)，改變費(fèi)用為ki|mi-mi|，mi為第i 個(gè)數(shù)原算法構(gòu)造帶權(quán)二分圖。二分圖左邊XN個(gè)結(jié)點(diǎn)表示原來的NYN 個(gè)結(jié)點(diǎn)表示改變N 個(gè)數(shù)。如果mi 可以變成mi，那么就在Xi 和 Ymi之間連一條費(fèi)用為 ki|mi-mi|的邊，否則在 Xi 和 Ymi之間連一條費(fèi)用為 無窮大的邊。求最小費(fèi)用的完備匹配。這時(shí)可以使用 KM算法。這樣的時(shí)間復(fù)雜度是 O（N3。但我寫的程序3-2給 出 n 和 m1,m2,mn，求方程 a1 xor a2 xor xor an=0 0=ai=mi，ai 不全為0參見問題3-4n 個(gè)回文詞，兩兩拼接的方法有n2種。其中有多少種的拼接結(jié)果也是回文詞參見問題POIXII20

16、04-Two parties 把 n 個(gè)人分到兩分析party，使得“有偶數(shù)設(shè)布爾值 xi為第 i 個(gè)人是否在第一個(gè) party。如果i 個(gè)有偶數(shù)個(gè)朋友，那么關(guān)于第i 個(gè)人的件就可以轉(zhuǎn)化xj1xorxj2xorxixorxj1xorxj2xor然后就要解含有 n 個(gè)未知數(shù)n xor 方程的。用消元就可以解決這問題個(gè)朋友與自己分到同一個(gè) party”的人數(shù)盡量多. 允許其中一個(gè)party 沒有人。每個(gè)不是自己的朋友關(guān)系是對(duì)稱的camel (pra)平面上有 n 個(gè)點(diǎn)，初每次只能右轉(zhuǎn)（0 到 180 度，線路不能交叉，最后回到點(diǎn) 1。要求盡量多的其他到 i 的最多點(diǎn)的路線的點(diǎn)數(shù)。初始條件就是F1,

17、2=2。轉(zhuǎn)移方程就是 觀察轉(zhuǎn)移方程中的 i，等式左邊和右邊都出現(xiàn)了。 就可以猜想，如果i 固定，能否高效地求出所以 如果可以的，應(yīng)該按什么順序來枚舉 i 呢？想象最優(yōu)路線的圖象，它就像是一個(gè)心型。對(duì)每Pi 定義一個(gè)排序函數(shù)，F(xiàn)(Pi)表示向P1Pi 時(shí)針旋轉(zhuǎn)多少度才P1P2 同向。并對(duì) P2Pn F(Pi)為關(guān)鍵字從小到大排序。排序后，從小到大的依次枚舉上述的iFk,i|ki按極角從小到大排序，同時(shí)也把Fi,|按極角從小到大排序。然后從后到前地一個(gè)個(gè)處理 F,j，不難發(fā)現(xiàn),Fi,j的前趨狀態(tài) Fk,i必定排序的序列后面連續(xù)多個(gè)，并且當(dāng)前的 Fi,j比上一個(gè) Fi,j的可選策略要多些或相同。這時(shí)可以用一個(gè)指針動(dòng)態(tài)地可選策略區(qū)和最優(yōu)策時(shí)間復(fù)雜度程序：了El判斷一個(gè)有向圖是否PS-graph. 即可以從一條邊經(jīng)過若干次 doublesplit操作得分析double的逆向操作刪去重split 的B 只和 A,C 相連。那么一個(gè)PS-graph