網(wǎng)上找的一些綜合材料專題phaseiiformxzl

1、第二階段：初步表格：學校： 蕪湖一中一. 對題目的總體感覺（請不要回答得太簡略）二. 關(guān)于每道題目，寫出你的看法序號思路或者解法（請不要寫得太簡略，可以寫在多行里）對題目的評價或?qū)Φ?001不會做也許要從數(shù)學上加以突破。0002似乎可以坐標離散化以后，對每一對相鄰的 y1、y2 所確定的橫條進行掃描，找出每一段位于多邊形的，這樣的段都是梯形，可以算出每一段有多少格，把每段累加即可?？赡芗毠?jié)上會比較繁吧。0003很容易想到不少種 O(N2)的算法，但暫時想不出 O(NlogN)的算法?？赡苓€是靠二分。0004不會做。不容易想出很好的動規(guī)。0005不會做。由于出現(xiàn)了環(huán)，所以難度陡增。0006貪心。

2、貪心易想，但證明不容易。0007先求出凸包，然后凸包上的邊的傾斜角將 02pi 分成若干個區(qū)間，每個區(qū)間求出以這個區(qū)間的直線為Y 軸的最左和最右點。輸入的直線當作Y 軸的話，查找在哪個區(qū)間（二分），判斷最左點和最右點是否位于同側(cè)即可。 O(mlogn)一道比較好的幾何題，難度蠻大的。0008不會做。侯都做不出來，難度太大了。0009不會做。數(shù)學味道太濃。0010貪心，但是我不會。駱 出的，他有貪心的算法，但我沒搞懂。另外，原題似乎并不一定有解。0011暫時想到先二進制編碼，再用 RLE 算法或哈夫曼編碼來壓縮。但是利用不到可以相差最多 10 個象素這一點。很好的題目，可以綜合能力?？傮w上看，題

3、目難度非常大，但也有可能是因為我。這些題目涉及到各個方面，如果都研究透了，將會大大提高自己在各方面的水平，但是也許時間不夠。有些題目者自己會做，但是為了找到更好的方法，或者覺得解法和思考方法還能推廣，所以也出來，這種精益求精的精神是值得學習的，同時也希望者能將自己的好方法告訴大 家。國內(nèi)的題目似乎不是很多，大多數(shù)題目是 POI、BOI、USACO、Ural 和 ACM 上的，希望以后能看到的好的國內(nèi)題目。LML 三位大哥，以及其他的們，加油出?。〉念}目也很好，但是可能都沒法解決。涉及到幾何的題目很多，特別是幾何。這正是弱項，希望大家能幫助我。IOI2003 中國國家集訓(xùn)隊難題活動0012似乎作

4、者的想法是可行的，當有一些點 M1,M2Mx 與 OPQ 共面時，僅需要O是否在M1,M2Mx 和P,Q 組成的凸包上即可。但即使是這樣，依然是繁瑣的?？臻g幾何太繁了。0013似乎先產(chǎn)生 8 種不同偏移量的“同步編碼”，再進行匹配是可行的，但是可能時間上確實會有作者說 吧?？此坪唵蔚念}目，但可能在時間上做文章。另外，可能編程上也有些繁瑣吧。0014離散化？一個面一個面地掃描嗎？這類問題需要一定的空間想象力。0015不會做。只能想到搜索最小表示判重。也許會在數(shù)學上（比如Polya 定理）有所突破。0016原題寬搜。但是如果規(guī)模大了，就不好辦了。也以先判定有沒有解，再做。0017想不出來。很好的題

5、目，也很難。0018標準方法是貪心。O(n2)。但證明沒有多想?？床ㄌm文的標程真是痛苦呀！0019不會做。是否可以這樣認為：對于任意的Ax+By， N|(A0 x+B0y) - N|(Ax+By)成立的充要條件是存在整數(shù)t 且 0=t0，就算出這個點順時針和逆時針轉(zhuǎn)移一個球的Cost，選擇較小的一個，轉(zhuǎn)移。計算Cost 的方法，順時針和逆時針是對稱的，以順時針為例：假設(shè) 順時針地轉(zhuǎn)移，那么會導(dǎo)致 ClockWisei改為順時針的下一個（相應(yīng)地，要增加一定的轉(zhuǎn)移步數(shù)），然后判斷l(xiāng)ockWisej是否等于ClockWisei，其中 j 為 i 的順時針的下一個非零格，若等于，則lockWisej改

6、為順時針的下一個，同時ClockWisej改為順時針的下一個，同時更改Cost 中的轉(zhuǎn)移步數(shù)。這樣，等于是j 又向順時針轉(zhuǎn)移了一個，可能會造成連鎖的反應(yīng)，所以要繼續(xù)判斷下去。轉(zhuǎn)移一個球和球 Cost 的過程比較類似。每次判斷最多繞一圈，所以轉(zhuǎn)移一個球的復(fù)雜度為O(n)，整個算法的復(fù)雜度為 O(n2)。0020原圖顯然無環(huán)，而且給定的頂點順序就是拓撲有序的。設(shè)合并后的圖是較大的點可以走到較小的點。從后向前貪心地做：設(shè)colori代表 i 點的顏色，lefti、midi、righti代表 i 點的左、中、右的邊所指向的點，m 代表合并以后有多少個點，Si代表原圖中的點在合并以后的。開始時m=1，S

7、i=0（1=in），且 Sn=1。然后依次處理 n-1、n-21。對于一個點i，如果Si=0，就將 m 加一，同時令Si=m，然后依次j=i-1,i-2,1，若colori=colorj and Srighti=Srightj and Smidi=Smidj and Srighti=Srightj，那么 i 和j 可以合并，也就是令Sj=Si。最后的 m 就是要求的。0021目前的想法是：最后肯定是一棵樹，那么共有N-1 條邊。于是，可以把每個點的花費cost 改為e=F/(N-1)-cost，則假如當前已有的收入為 I，工作時間為T，那么再加上一條邊(收入為 i,時間為t)之后的收入為I+i

8、，時間為T+t，且最后的所有收入加起來正好等于減總花費。但之后就不知道怎么做了。0024此題相當于：有一個標準的球和n-1 個球，其中有一個質(zhì)量與標準的不同，問是不是可以在k次比較之內(nèi)找到壞球。用三分法可以證明如下結(jié)論：現(xiàn)有N 個小球，其中有一個壞球不知比標準球輕還是重。 令H=log3(2N)，其中x表示大于等于 x 的最小整數(shù)。要保證在N 個球中找出壞球并知道其輕重，至少需要稱H 次。假設(shè)N2，有如果N(3H-1)/2，那么稱H 次就足夠了；如果N=(3H-1)/2，那么稱 H 次足以保證找到壞球，但以保證知道壞球比標準球輕還是重；如果N=(3H-1)/2，而且還另有一個標準球，那么稱 H

9、 次足以保證找到壞球和知道，知道壞球比標準球輕還是重。將在冬令營的中詳細地講這題，所以我就不多寫了。0025寬搜，隊列里只存在模M 的意義下彼此不同的各類數(shù)中的最小的一個。開始時隊列中從大到小地填入X1,X2Xm，當然，要保證它們模M 的值不等，否則只填最小的那個。然后依次擴展，即將待擴展的數(shù)乘以 10 再加上X1,X2Xm，如果余數(shù)是新的，就填到隊尾。直到產(chǎn)生出余數(shù)為 0的為止。一個技巧是不需要存數(shù)，只需要存余數(shù)和數(shù)的最后一位以及從哪里擴展出來的，這樣打印的時候倒推一遍就可以了。時間復(fù)雜度O(n*m)，空間復(fù)雜度O(n)。0038對于未壓縮的串，有O(n)的匹配算法或是另外一種基于最小表示的

10、算法，對于壓縮的串，匹配算法不好推廣，但后法似乎很容易推廣。將在冬令營的中詳細地比較這兩種方法，所以我就不多寫了。0041上看，應(yīng)該是先盡量把大盒子的填到大的容器里，看能不能把所有的容器填滿，如果能，再從剩下的盒子里由大到小地把選取一些盒子與原來的盒子交換，使價值減少。但是沒有證明。0043稱所有分割開兩個區(qū)域的格子為“圍墻”，一開始“圍墻”就是最一圈的格子。每次找到最低的一個圍墻，進行Flood Fill，注意只能擴展比這個圍墻低的格子。擴展出的連通區(qū)域的水位就是這個格子的高度（于是可以算出這片區(qū)域的容積），同時，這片區(qū)域周圍的格子成為新的圍 墻，而這片區(qū)域的格子將被標記為“考慮”，因為以后

11、如果和它相連的區(qū)域水位高了，就會從這片區(qū)域流走。處理過的圍墻不能再處理。這樣直到所有圍墻都被處理完。令 N=n*m，如果用堆來存圍墻，時間復(fù)雜度為O(NlogN)；如果一開始將所有格子排序，在中途標記圍墻，時間復(fù)雜度等于排序復(fù)雜度，可以是O(NlogN)，甚至 O(N)（如果用計數(shù)排序的話）。如果我有時間，會寫這題的解題，因為這題確實比較好。0045可以用搜索自身判重（最小表示判重）來解決。正方形的就是經(jīng)典的“撕郵票”問題，六邊形的是“蜂巢問題”， 省有一年省賽考過。這兩題我都做過。正三角形應(yīng)該也類似。如果是六邊形和三角形，建立坐標系的時候有一個小技巧可以幫助思考旋轉(zhuǎn)、翻轉(zhuǎn)的公式，是比較巧妙有

12、趣的，我準備（可能沒有時間）寫一篇小文章來具體講講。正方形的可以有很 的剪枝，我不是很擅長，但曾經(jīng)和 過。0046原題的規(guī)模比較小，所以可用化搜索解決：設(shè)整數(shù)se 對應(yīng)的二進制串代表了某個人是否出現(xiàn)在已排的隊列里，Ss e代表某種s e 對應(yīng)的不同排列數(shù)，很容易得出Ss e的表達式。但是如果規(guī)模比較大了，就不好做了，是否有圖論的方法呢？0047建立一個先序遍歷搜索樹，顯然，環(huán)的情況只會出現(xiàn)在某個頂點連向它的祖先。某個頂點連向最近的祖先的邊是有效的，其他的可以忽略，不妨刪掉。依次考慮每個頂點，如果它有連向祖先的邊，看這個邊是否形成一個大于 3 的圈，如果是，那么再看這個圈里有沒有別的小圈把它破壞

13、掉，如果破壞不掉的話，那么就說明圖中存在大于 3 的洞。0066初步的想法是：設(shè)needi代表為了拼出某一段的數(shù)，在初始的時候數(shù)字 i 的最小需求量， increasei代表拼完了這一段數(shù)之后，數(shù)字 i 的增量（可能為負）。先求 199 的needi和 increasei，然后根據(jù)這個可以求 1999 的needi和increasei，就這樣，直到 1x999 無法表示，而 1(x-1)999 可以表示，于是所求的數(shù)上下界就定下來了，再一位一位地確定。這只是大概想法，也許細節(jié)上會很繁。0075首先，原圖一定可以排列成： 下面接著一棵二叉樹，這個二叉樹的每個非葉子節(jié)點都有兩個兒子。所有的葉子節(jié)點

14、從左到右連在一起，邊的葉子節(jié)點連在一起。對于原圖中的二叉樹的每個非葉子節(jié)點x 定義下面幾個數(shù)組：Root_To_Rightx代表在以 x 為根的中，從根走到這棵樹上最右邊的葉子，并且走完這棵樹上的每個點的最好代價，類似的，還有Root_To_Left，Left_To_Right，Left_To_Root，Right_To_Root 和Right_To_Left，而這些數(shù)組是互相的，但是有階段性，所以可以用動態(tài)規(guī)劃推出來。最口可以先走到二叉樹的根，再走到左邊或右邊的葉子，最后回到 ；或者先走到左邊的葉子，再走到根或右邊的葉子，最后回到入口；以及先走到右邊的葉子，再走到根或左邊的葉子，最后回到 。

15、而這些情況都是可以利用上面的幾個數(shù)組計算出來的。注意到上面的分析中很多情況是對稱的，有些數(shù)組方案是等效的，所以還可以優(yōu)化。0078如果只求方案數(shù)的話，可以規(guī)定第一行的皇后只能放在左半行，因為放在右半行的情況是對稱的。但是這樣也只能節(jié)省一半的時間。0091先用Dijkstra 算法計算出A、B、C 到每個點的最短距離，也就求出了原來的A 到B、C 的最短距離 SA、SB。然后枚舉 X、Y，假設(shè)在X、Y 之間建橋符合要求，那么從A 到B 的最短距離 d(A,B)=mind(A,X)+d(X,Y)+d(Y,B)，d(A,Y)+d(X,Y)+d(X,B)，同樣d(A,C)=mind(A,X)+d(X,

16、Y)+d(Y,Z)，d(A,Y)+d(X,Y)+d(X,C)，判斷：若 d(A,B)SA and d(A,C)SB且d(A,B)+d(A,C)當前求得的最小值，那么就替換當前的方案。0099用S e=(x1,y1,manner1,x2,y2,manner2,x3,y3,x4,y4)代表一個狀態(tài)，其中前三個數(shù)代表第一個 L的“頭”的坐標和擺放方式，然后是第二個L 的信息，x3、y3 代表第一個圓片的位置，x4、y4 代表第二個圓片的位置。首先求出所有合法的方案，為它們 ，設(shè)為 1 到n。建立S e 到Number的雙向 。先標出所有的無法繼續(xù)的狀態(tài)為Lose，其余的狀態(tài)為Unknown。依次處理

17、每個Unknown 狀態(tài)，如果后繼狀態(tài)有Lose，則標記此狀態(tài)為Win，如果后繼全都是Win，則標為Lose，否則不改動。一遍處理完，再進行下一遍，直到某次沒有做出任何改動，停止，標記所有 Unknown 為 Draw。復(fù)雜度也許高了一點。四. 除了自己的題目外，這 100 道題目中你最希望別人的題目有哪些？請分別說明理由并的難度。（說明：這里是指你希望大家的題目，而不是你準備參加的題目?；蛟S有些題目，你自己并不拿手或者沒什么并寫明理由。），但是特別希望聽其他人的，本題的意思就是要你把這些題目列出來五. 雖然目前還不會做，但你自己有一定想法，將會積極參與的題目有：00020003001000110002很好的一道離散化的題目？也許有非離散化的方法？0005怎樣處理這樣有后效？還是貪心嗎？00120014空間幾何怎么處理才方便呢？00150093像這種求本質(zhì)不同的方案，怎么做才高效呢？0017非常有趣的題目，感覺上比較有探討價值。0023像這種折疊的題目該怎么做呢？00490058怎樣解模線性方程組比較簡便？希望大家教我。0053像這種摸不著頭腦的構(gòu)造題目該怎么做呀？00600095這兩道題目有點像：都涉及到“定方向”，是否有類似的解法呢？0062有點像n-S