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

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

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

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

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

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

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

7、i=0（1=in），且 Sn=1。然后依次處理 n-1、n-21。對(duì)于一個(gè)點(diǎn)i，如果Si=0，就將 m 加一，同時(shí)令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目前的想法是：最后肯定是一棵樹(shù)，那么共有N-1 條邊。于是，可以把每個(gè)點(diǎn)的花費(fèi)cost 改為e=F/(N-1)-cost，則假如當(dāng)前已有的收入為 I，工作時(shí)間為T，那么再加上一條邊(收入為 i,時(shí)間為t)之后的收入為I+i

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

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

10、算法，對(duì)于壓縮的串，匹配算法不好推廣，但后法似乎很容易推廣。將在冬令營(yíng)的中詳細(xì)地比較這兩種方法，所以我就不多寫(xiě)了。0041上看，應(yīng)該是先盡量把大盒子的填到大的容器里，看能不能把所有的容器填滿，如果能，再?gòu)氖Ｏ碌暮凶永镉纱蟮叫〉匕堰x取一些盒子與原來(lái)的盒子交換，使價(jià)值減少。但是沒(méi)有證明。0043稱所有分割開(kāi)兩個(gè)區(qū)域的格子為“圍墻”，一開(kāi)始“圍墻”就是最一圈的格子。每次找到最低的一個(gè)圍墻，進(jìn)行Flood Fill，注意只能擴(kuò)展比這個(gè)圍墻低的格子。擴(kuò)展出的連通區(qū)域的水位就是這個(gè)格子的高度（于是可以算出這片區(qū)域的容積），同時(shí)，這片區(qū)域周圍的格子成為新的圍 墻，而這片區(qū)域的格子將被標(biāo)記為“考慮”，因?yàn)橐院?/p>

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

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

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

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

15、而這些情況都是可以利用上面的幾個(gè)數(shù)組計(jì)算出來(lái)的。注意到上面的分析中很多情況是對(duì)稱的，有些數(shù)組方案是等效的，所以還可以優(yōu)化。0078如果只求方案數(shù)的話，可以規(guī)定第一行的皇后只能放在左半行，因?yàn)榉旁谟野胄械那闆r是對(duì)稱的。但是這樣也只能節(jié)省一半的時(shí)間。0091先用Dijkstra 算法計(jì)算出A、B、C 到每個(gè)點(diǎn)的最短距離，也就求出了原來(lái)的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)當(dāng)前求得的最小值，那么就替換當(dāng)前的方案。0099用S e=(x1,y1,manner1,x2,y2,manner2,x3,y3,x4,y4)代表一個(gè)狀態(tài)，其中前三個(gè)數(shù)代表第一個(gè) L的“頭”的坐標(biāo)和擺放方式，然后是第二個(gè)L 的信息，x3、y3 代表第一個(gè)圓片的位置，x4、y4 代表第二個(gè)圓片的位置。首先求出所有合法的方案，為它們 ，設(shè)為 1 到n。建立S e 到Number的雙向 。先標(biāo)出所有的無(wú)法繼續(xù)的狀態(tài)為L(zhǎng)ose，其余的狀態(tài)為Unknown。依次處理

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