版2014年8月4日到5-貪心與搜索

貪心與搜索向鵬達(dá)貪心與搜索是有相關(guān)性的，所以可能采取兩種類型的題交雜的方式，有不少的題目會同時用到這兩種方法貪心算法（摘自百度百科）

對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，而僅是做出在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。如果要用貪心算法得到最優(yōu)解，那么要保證貪心算法所得到的局部最優(yōu)解就是整體的最優(yōu)解noip2012提高組

國王游戲

國王游戲

(game.cpp/c/pas)

【問題描述】

恰逢

H

國國慶,國王邀請

n

位大臣來玩一個有獎游戲。首先,他讓每個大臣在左、右手上面分別寫下一個整數(shù),國王自己也在左、右手上各寫一個整數(shù)。然后,讓這

n

位大臣排成一排,國王站在隊伍的最前面。排好隊后,所有的大臣都會獲得國王獎賞的若干金幣,每位大臣獲得的金幣數(shù)分別是:排在該大臣前面的所有人的左手上的數(shù)的乘積除以他自己右手上的數(shù),然后向下取整得到的結(jié)果。

國王不希望某一個大臣獲得特別多的獎賞,所以他想請你幫他重新安排一下隊伍的順序,使得獲得獎賞最多的大臣,所獲獎賞盡可能的少。注意,國王的位置始終在隊伍的最前面。

【輸入】

輸入文件為

game.in。

第一行包含一個整數(shù)

n,表示大臣的人數(shù)。

第二行包含兩個整數(shù)

a

和

b,

之間用一個空格隔開,

分別表示國王左手和右手上的整數(shù)。

接下來

n

行,每行包含兩個整數(shù)

a

和

b,之間用一個空格隔開,分別表示每個大臣左手和右手上的整數(shù)。

【輸出】

輸出文件名為

game.out。

輸出只有一行,包含一個整數(shù),表示重新排列后的隊伍中獲獎賞最多的大臣所獲得的金幣數(shù)。

【輸入輸出樣例】

game.in

3

1

1

2

3

7

4

4

6game.out

2

【數(shù)據(jù)范圍】

對于

20%的數(shù)據(jù),有

1≤

n≤

10,0

<

a、b

<

8;

對于

40%的數(shù)據(jù),有

1≤

n≤20,0

<

a、b

<

8;

對于

60%的數(shù)據(jù),有

1≤

n≤100;

對于

60%的數(shù)據(jù),保證答案不超過

109;

對于

100%的數(shù)據(jù),有

1

≤

n

≤1,000,0

<

a、b

<

10000?？紤]相鄰的兩個人A，B設(shè)A左手上的數(shù)字是A.left,右手上的數(shù)字是A.right.B同理。當(dāng)A位于B前面時答案是：max(C/A.right,C*A.left/B.right)當(dāng)B位于A前面時答案是max(C/B.right,C*B.left/A.right)我們把max拆開來考慮，即通過分情況考慮來去掉max。情況一：A.left*A.right<B.right此時上一頁的第一個max函數(shù)中的較大的一項是C/A.right，第二個max函數(shù)中較大的一項是C*B.left/A.right.（因為A.left*A.right<B.right可以推出A.right<B.left*B.right，再推出C/B.right<C*B.left/A.right）。那么比較的就是C/A.right與C*B.left/A.right.因為B.left是大于等于一的整數(shù)，所以后者要大（答案劣一些）。所以應(yīng)該把A放在前面。此時B.left*B.right比較大。情況二：B.left*B.right<A.right那么比較的就是C*A.left/B.right與C/B.right因為A.left是大于等于一的整數(shù)，所以前者要大。所以應(yīng)該把B放在前面。此時A.left*A.right比較大。情況三：其他情況。那么比較的就是C*A.left/B.right與C*B.left/A.right如果A.left*A.right大一些，那么應(yīng)該把B放在前面。也就是說按照left*right從小到大排序我們發(fā)現(xiàn)情況一和情況二也滿足‘最優(yōu)做法是按照left*right從小到大排序’的性質(zhì)，所以這樣做就行了。這題難點其實在于高精度乘法除法。累了吧，讓我們看一看搜索搜索的關(guān)鍵是，要找到合適的方法讓效率提高。如果是裸的搜索是很容易編的，所以說其藝術(shù)性就在優(yōu)化上。俗話說看起來越簡單的東西，精通起來就越難。搜索分為深度搜索（DFS）與廣度搜索（BFS），深度搜索又可以細(xì)分為記憶化搜索和迭代加深搜索(DFS-ID)等。NOIP2011提高組mayan用一句話來說題意，就是，給定一個存在重力的矩陣，每次只能向左或右交換方塊，連續(xù)3個或以上的方塊群會被消除。求操作次數(shù)為N時的操作步驟。搜索，進(jìn)行優(yōu)化雖然好像優(yōu)化方法說出來之后很容易理解，但是考場上不是很容易都想到因為題目規(guī)定了游戲步數(shù)，而且并沒有要你使用最少步數(shù)的方法，所以用DFS會很方便，用BFS會超空間。如何處理重力問題以及消除問題？深搜遞歸的時候參數(shù)要傳一個結(jié)構(gòu)體，即當(dāng)前局面狀態(tài)。寫一個函數(shù)Down，傳入一個局面，返回讓當(dāng)前局面中所有懸空的方塊掉下去的局面再寫一個函數(shù)Clear，傳入一個局面，返回讓當(dāng)前局面中所有可消去的方塊消去后的局面讓當(dāng)前局面輪流調(diào)用這兩個函數(shù)，直到局面沒有改變了為止。優(yōu)化左右的交換是等價的如果當(dāng)前局面某種顏色的方塊個數(shù)小于等于二，顯然這個局面就不可能通往勝利了（我當(dāng)時居然沒想到...什么？這個太容易了？大家都比我聰明TT）方塊的掉落，不能改變方塊的列，所以對于顏色i，如果某列l(wèi)1上某顏色方塊數(shù)量屬于[1,2]區(qū)間，那么必須通過交換，來從其他的某列l(wèi)2得到方塊。取一個l1，且l2最遠(yuǎn)，設(shè)這個距離為Di，那么必須要把所有顏色的Di消到0。而一次操作最多減少兩個顏色的Di，因此最少操作次數(shù)為：max{max{Di}(1<=i<=10),(sum(Di)(1<=i<=10)+1)/2}

NOIP2009提高組靶形數(shù)獨搜索？搜索。依次枚舉每一個沒放置數(shù)的格子里所放置的數(shù)。用hh[i][j]記錄第i行是否已經(jīng)填過j這個數(shù)了，對于每個列和九宮格的記錄同理。但是這樣可能還會超時，怎么辦？從右往左，從下往上搜。這個方法過于投機取巧？我們要領(lǐng)會出題者的意圖——想讓我們用常規(guī)的方法通過不了某個數(shù)據(jù)，而改用更高級的方法。但是一個數(shù)據(jù)只能讓特定的搜索順序進(jìn)行的搜索變得特別慢，所以說如果我們事先隨機一個搜索順序，或許就能不被某個數(shù)據(jù)卡掉。還是感覺這種方法不夠正義？對于每個局面，找出剩下未填的位置中的可填數(shù)字個數(shù)最少的位置，先填它。比如說A位置有4種合法填法，B位置有3種，C位置有5種，就先填B位置。每次進(jìn)入遞歸函數(shù)都要進(jìn)行一遍這個過程，太慢？其實只是讓時間增加了一倍左右，但是通過‘先搜分支少的’的方法可以讓運行速度呈指數(shù)地加快估計出題者是想讓我們用dancing-links解決這個問題這是一種算法，用類似二維雙向鏈表的結(jié)構(gòu)優(yōu)化了對于[精確覆蓋問題]的搜索速度，所以說只要把原問題轉(zhuǎn)化為這種[精確覆蓋問題]再搜索就可以極大加快速度。有興趣的同學(xué)可以百度搜一下這種算法，資料很多NOIP2007普及組紀(jì)念品分組普及組的題目都不會太難，增加信心用貪心每次考慮還沒有被選過的最大的物品，然后找一個能與之價格加起來小于那個上限的最大的物品，組成一對。注意題目里說了每一組最多兩個物品。如果找不到與之放在一組的物品，那么就單獨放一組。由于那個與之放在一組的物品的最大允許價值是不降的，維護(hù)一個指針即可。為什么這樣是正確的？如果當(dāng)前考慮到物品A，B是A能組隊的最大的物品，C的價值小于B。本來是A，B一組的，如果變成A，C一組，對于剩下的未選的物品集合的變化就是多了B少了C，這肯定是不會比變化之前更優(yōu)的。考場上如果只能‘意會’到這種貪心是正確的，怎么辦？寫一個暴力的程序，再寫一個數(shù)據(jù)生成器，與這種貪心方法的程序進(jìn)行對拍。USACOBetsy'sTour一個正方形的鎮(zhèn)區(qū)分為N*N個小方塊（1<=N<=7）。農(nóng)場位于方格的左上角，集市位于左下角。貝茜穿過小鎮(zhèn)，從左上角走到左下角，剛好經(jīng)過每個方格一次。當(dāng)N=3時，貝茜的漫游路徑可能如下圖所示：1<=N<=7.搜索我們注意到，在任何時刻，都必須保證和當(dāng)前所在位置不相鄰的未經(jīng)點至少有兩個相鄰的未經(jīng)點。通過這種想法，我們可以采取這樣的優(yōu)化：1.對當(dāng)前點周圍的點D,如果只有一個與D相鄰的未經(jīng)點,則點D為必經(jīng)點（下一步必須走到的點）2.如果當(dāng)前點周圍有兩個或兩個以上的符合上述條件的必經(jīng)點，則無論走哪個必經(jīng)點都會造成一個死胡同，需要剪枝3.如果當(dāng)前點周圍只有一個必經(jīng)點，則一定要走到這個點N=7的時候還是會超時不能形成孤立的區(qū)域。如果行走過程中把路一分為二，那么肯定有一部分再也走不到了，需要剪枝。如果每次都使用floodfill算法找連通塊，所耗時間會太多。我們必須有效率地進(jìn)行剪枝。當(dāng)前點左右都是已經(jīng)點(或者是邊界)，而上下都是未經(jīng)點當(dāng)前點上下都是已經(jīng)點(或者是邊界)，而左右都是未經(jīng)點這樣不管怎么走，必然是會有孤立的區(qū)域，只要將出現(xiàn)這種情況的狀態(tài)都剪掉即可。HNOI2011賽車游戲簡要題意給你一個道路每一段的長度與斜率s，對這段路來說，如果你用v的速度開，那么每公里的耗油量是max(0,a*v+b*s)，其中a,b是題目給定的常數(shù)?？傆土渴墙o定的，問開完這段道路最短時間。這題我當(dāng)年得了多少分呢？貪心不妨設(shè)我們把路分成一公里一公里的小段。我們發(fā)現(xiàn)，對于一小段路，在其上提速1km/h的代價總是a既然總油量是確定的，綜合上一條信息，這告訴我們，所有小段的速度的和是有限的假設(shè)路分為兩個小段（每個小段1km，共2km），在這兩個小段上的速度分別為x和y，那么我們要所用時間最少，也就是要1/x+1/y最小，并滿足x+y=C（C是一個定值）當(dāng)1/x+1/y最小時顯然有x=y.所以說，最優(yōu)的情況一定是所有路段的速度v都是相同的！（允許有一些下坡路段速度大于v，但是這些路段油耗都是零）具體做法？先不考慮下坡路段，算出此時在其他路段上的速度v如果v大于[最平緩的下坡路段零油耗時的速度]，說明這段下坡的速度不會比最終其他路段速度快，將其并入‘其他路段’的集合中，再次計算v。再比較v與[次平緩的下坡路段零油耗時的速度]，如果v是較大的，就并入，再次計算v...直到v是較小的為止。NOI2012騎行川藏

Input31000010000105200001585000056Output12531.34496464簡要題意：一個道路有N段路，對于一段長度是s,風(fēng)阻系數(shù)是k,風(fēng)速是v的路，如果使用V的速度騎行，需要的能量是k*s*(V-v)^2.給定總能量，問騎完這個道路的最短時間。這道題與上道題有較大的相似性對于這道題而言，讓一個小段（1km）的速度加快1km/h，需要的能量是與當(dāng)前速度以及這段的性質(zhì)有關(guān)的。我們需要將上題的方法推廣到更普適的情況，以適應(yīng)這道題設(shè)當(dāng)前有一個方案，第i段路的速度是V[i]，且讓走這段路所需的時間減小Δt所需要多耗的能量為de[i]*Δt。其實de[i]就是這段的耗能E對于耗時t的導(dǎo)數(shù)，將t=k[i]/V[i]代入E=k[i]*s[i]*(V[i]-v[i])^2再對t求導(dǎo)即得de[i]。最優(yōu)方案中，de[1],....,de[N]的值都是相等的。這讓我們先想到，二分最優(yōu)方案的de的值，然后計算出此時每一段的速度（計算速度時需要解一個三次方程，可用三分法求解），然后求出總耗能，比較總耗能與給定的耗能，來決定二分的區(qū)間往哪邊縮小。這種貪心的方法比較巧妙，關(guān)鍵是找出最優(yōu)策略中的不變量——de的值。USACOlatinUSACO上的搜索題好多啊...搜索優(yōu)化有哪些呢1.在第一行的排列已經(jīng)確定以后，第一列的每一種排列對應(yīng)的方案數(shù)都相同。所以只需要搜索(2,2)到(N,N)的邊長為n-1的正方形即可（最后乘上第一列的可能方案數(shù)）。且對于(2,2)這個位置，填3，4……的方案數(shù)完全一樣（與填1的可能不同），因此只要枚舉填1或者3。2.最后一行不用搜，因為已經(jīng)由之前的確定了（所以只要搜(2,2)-(n-1,n)的矩形）娛樂題有N個人，每個人有一個黑歷史，一開始每個人只知道自己的黑歷史。然后大家想來共享黑歷史，目標(biāo)就是讓每個人都知道所有人的黑歷史。傳遞信息的方式只能是兩個人進(jìn)行交流，這兩個人可以把所有的自己已知的黑歷史告訴對方。信息量再大也沒事，都算是一次交流。問讓每個人都知道所有人的黑歷史，最少需要多少次交流比如說N=3的情況，A，B，C三個人。A先跟B交流，此時A知道A和B的黑歷史，B知道AB的，C知道C的。B跟C交流，此時A知道AB的，B知道ABC的，C知道ABC的。B再跟A交流，此時大家都知道ABC其中每個人的了。需要3次。答案是2N-3第一個人先跟第2...N個人交流，其中跟第N個人交流之后，第一個人和第N個人都知道了所有人的信息。然后第一個人只需要跟第2...N-1個人交流，那么就讓他們都知道了所有人的信息。真是這樣嗎~~~想一想N=4的情況，能不能比5次更少一點呢？比如說，4次？4次是可以做到的。A先跟B交流，此時A和B都知道了AB的信息。C跟D交流，此時C和D都知道了CD的信息。A跟C交流，此時A和C都知道了ABCD的信息。B跟D交流，此時所有人都知道了ABCD的信息。所以，2<=N<=3時答案是2N-3，N>3時答案是2N-4N>4時，方法是讓第4個人跟5...N交流一遍來收集信息，然后再按照N=4的情況讓1、2、3、4互換信息，然后第4個人再跟5...N交流一遍來下發(fā)信息。如上是2014年8月4日上午的講課內(nèi)容。此題作為中午的思考題被出出來。USACOmilk4超市中有P個桶(1<=P<=100)，每個桶有各自的容積你需要買回最少的桶，使得它們可以量出容積為Q的牛奶(1<=Q<=20000)。你每次可以使用一個桶，從巨大的牛奶池里裝出等于這個桶容積的牛奶，放到一個大罐子里，你需要讓這個罐子里的牛奶量為Q。你不能進(jìn)行其他類型的操作。保證有解搜索因為題目中要求桶數(shù)最少，而深搜是不知道搜索的層數(shù)的，所以要用到迭代加深搜索。在主函數(shù)中，for循環(huán)從1開始枚舉搜索層數(shù)（也就是使用的桶數(shù)），在for循環(huán)里面調(diào)用搜索函數(shù)（其中有一個參數(shù)是我們當(dāng)前定下的搜索層數(shù)）。如果找到解，就跳出循環(huán)。可以用廣搜做嗎？應(yīng)該可以，但太耗空間。你可能認(rèn)為迭代加深搜索在定下深度為m+1層的搜索的時候，重復(fù)了深度為m的搜索已經(jīng)做過的部分，但由于當(dāng)深度上升時，搜索所用的時間呈指數(shù)上升，所以說重復(fù)的部分耗時可以忽略不計。（這段是應(yīng)一些同學(xué)的要求寫的，因為反映具體的遞歸過程不太會寫。不過應(yīng)該很多人都會吧..是比較基礎(chǔ)的遞歸）在遞歸函數(shù)里要傳入一個參數(shù)k，代表我們已經(jīng)考慮完前k個桶了，那么當(dāng)前只需考慮將第k+1~第P個桶中的哪個桶放入買桶的集合，然后再遞歸下去（傳下去的參數(shù)為當(dāng)前選擇的桶的編號）。當(dāng)搜索到一個組合，判斷用這些牛奶桶是否可以得到解的時候，要結(jié)合動態(tài)規(guī)劃的方法來做。設(shè)f[i]為用這些桶是否能夠量出容量為i的牛奶，它是一個布爾型數(shù)組。初始條件為f[0]=1，其他f的值都為0.狀態(tài)轉(zhuǎn)移方程f[i]=f[i]orf[i-v[j]](j為使用的所有牛奶桶)目標(biāo)狀態(tài)為f[Q]如果f[Q]為1，則當(dāng)前解合法，直接輸出即可。

我們可以邊搜索，邊進(jìn)行f數(shù)組的修改（要記錄哪些位置被修改了，方便回溯）如果當(dāng)前桶的容積是V，但是f[V]=1，說明通過之前的桶的組合就可以代替當(dāng)前桶了，剪掉這種情況。由于直觀上會覺得小的桶更加有用，所以事先將桶按照容積從小到大排序，再進(jìn)行搜索，效果會更好。我們發(fā)現(xiàn)，對于一個桶的集合，如果是最優(yōu)方法的話，肯定每一個桶都要用到。否則方法可以更優(yōu)。也就是說，如果大小為x的容量可以不使用當(dāng)前剛加入的桶就能達(dá)到了，我們不妨認(rèn)為這種容量是‘達(dá)不到的’。也就是f[x]賦為0.具體來說，我們在每次加桶來更新f數(shù)組之前，把f數(shù)組復(fù)制一遍，設(shè)為g。更新之后，如果有某個i滿足g[i]=1，那么就令f[i]=0，因為這個容量之前就已經(jīng)是可以達(dá)到的了。讓f中1的個數(shù)盡量少，為什么能夠優(yōu)化呢？注意到，我們的轉(zhuǎn)移方程也可以看為，對于每個i

,若f[i]=1，則令f[i+v[j]]=1.（v[j]是剛剛加入的桶的容量）因為f[i]=1的i的個數(shù)比較少，我們可以用一個數(shù)組去記錄哪些位置上的f[i]=1，于是我們更新一次f所需復(fù)雜度只是f中1的個數(shù)了。帶權(quán)中位數(shù)問題SGU114給你N個東西，每個東西有兩個性質(zhì)a[i]（數(shù)值）和b[i]（權(quán)重）你要找到一個數(shù)X，使得sigma{abs(a[i]-x)*b[i]}最小。如果每個b[i]都是1，那么問題就等價于找中位數(shù)。貪心先將東西按照a從小到大排序。求出b[i]的和，設(shè)為B。先令temp=0。從前往后掃描東西，讓temp+=b[i].當(dāng)temp首次大于B/2時，當(dāng)前的東西的a值就是x的最優(yōu)值（之一）。最優(yōu)性顯然吧考慮將x變小或者變大，答案都不會更優(yōu)。為便于理解，可以考慮每個東西的b值都為1的情況，那么就是樸素的中位數(shù)的問題，上一頁所說的用temp進(jìn)行的那個過程顯然是對的。然后我們可以把第i個東西拆成b[i]個b值為1的東西。（如果b[i]是1.5，你就拆成1.5個b值為1的東西...雖然你會覺得很詭異，但的確可以這么理解）SGU313題目大意：在一個長為L（10^9）的環(huán)形跑道上，有n(n<=50000)個X，n個O，他們每個都位于跑道的某個整數(shù)位置上——我們以某個點為起點，位置即為順時針離起點的距離。告訴你每個X和O的坐標(biāo)，請你找出一種配對方案，使得每個X跑到自己心愛的O那里所經(jīng)過的長度之和最短。輸出每個X配對的是第幾個O。如果不是一個環(huán)而是一個直線就很好做了，直接O（n）模擬掃一遍，開一個棧存放還未匹配的點編號，注意這些點可能是X集合的也可能是O，因為他們的先后沒有規(guī)定。問題就是要找一個分割點，從這個分割點分割開后再對形成的一條直線進(jìn)行上述操作。首先我們證明對最優(yōu)方案，必定存在至少一根X、O中間的子線段，他們中間是沒被任何匹配線覆蓋的（即能找到一個分割點）。對上面這個圖，他必定不是最優(yōu)方案。為什么呢？我們可以對所有交叉的匹配進(jìn)行調(diào)整，使得調(diào)整后肯定不比原來差，且有分割點存在。對于原來的X和O的順序是X、X、O、O的一個子集，其中第1個和第3個連，2和4連，我們把它調(diào)整成1和4連，2和3連，這樣答案不變。假設(shè)最優(yōu)方案沒有分割點，那么調(diào)整之后答案不變，但是必有一條最長的匹配已經(jīng)包圍了整個環(huán)了，這顯然是荒謬的。下一步就是枚舉分割點（其實是分割線段）。但是枚舉是O(N)的，加上判斷o（n），明顯超時。我們要探尋神奇的性質(zhì)。我們先隨便假設(shè)一個點為起點（不妨設(shè)排序后第一個點）。若以此點所在線段進(jìn)行分割，那么求得答案就是每條線段長度*架在它上面的匹配邊的條數(shù)的和。架在它上面的匹配邊的條數(shù)，這個有神奇的性質(zhì)。掃一遍的過程中，每碰到一個黑點，下一截的線段標(biāo)記+1，碰到白點就-1。我們發(fā)現(xiàn)架在它上面的匹配邊的條數(shù)即為線段標(biāo)記的絕對值.比如XXOOOX，架在相應(yīng)線段上面的匹配邊的條數(shù)即為1210|-1|0.（也就是121010）

那么，當(dāng)匹配點往后移一位時，相當(dāng)于是最左邊的點移到了最右邊，若最左邊是X，那么線段變成了XOOOXX，新標(biāo)記就是010|-1||-2||-1|我們驚奇的發(fā)現(xiàn)，所有邊的標(biāo)記都-1了！

假設(shè)我們枚舉的分割點為k。k點的前綴和是vk(黑點為1，白點-1)。那么所有邊新標(biāo)記變成了原標(biāo)記-vk!

那么，相當(dāng)于找一個數(shù)，讓它與所有線段原標(biāo)記的差絕對值*對應(yīng)線段長度的值盡量小。

我們發(fā)現(xiàn)，這就是一個帶權(quán)中位數(shù)模型（sgu114是裸的帶權(quán)中位數(shù)模型）折半搜索（雙向廣搜）比如這樣一道題九宮格的華容道游戲大家都知道吧，每個格子有一個1~8的數(shù)，還有一個格子是空的給你初始狀態(tài)和結(jié)束狀態(tài)，問你有沒有N步以內(nèi)從初始狀態(tài)變換到結(jié)束狀態(tài)的方法，如果有的話輸出步驟N很大怎么辦呢？我們可以搜索（深搜廣搜均可）出從初始狀態(tài)開始走N/2步（向上取整）可以到達(dá)的狀態(tài)，把這些狀態(tài)用一個數(shù)字（就像MD5碼一樣?。┍硎?，存在哈希表里（通過掛鏈的方式，也就是哈希表只是一個索引，在掛著的鏈上存儲具體的九宮格狀態(tài)。這樣是為了避免兩個實際上不同的狀態(tài)卻算出了同樣一個數(shù)字）注意，搜索的時候要判重然后我們再從結(jié)束狀態(tài)開始，搜索N/2（向下取整）步，然后對于每一種狀態(tài)，也用一個數(shù)字表示，并且在哈希表內(nèi)查找這種狀態(tài)是不是被記錄過。如果被記錄過，就說明從兩邊的搜索到達(dá)了同樣的一個狀態(tài)，說明這是一個解。就像挖隧道一樣如果你確定了隧道的開始點和結(jié)束點，選擇只從一邊挖的話，如果要恰好挖到結(jié)束點，需要嘗試很多次但如果先從開始點開始挖一半的路程并且在挖到的地方做上標(biāo)記（嘗試許多次，做上許多標(biāo)記），再從結(jié)束點開始挖一半的路程，只要找這種標(biāo)記就行，就可以減少嘗試次數(shù)折半搜索的搜索過程就像一個菱形如上是2014年8月4日的講課內(nèi)容。tyvj的一道題在烈日下工作了一個月的你，七夕了，你要給妹子送禮物，禮物當(dāng)然是一塊純手工的磚，每次妹子看到這塊磚就能想起你。這里有N個泥土塊（N<=45），每個塊有一定的質(zhì)量，你可以選擇其中一些泥土塊去燒結(jié)成你的磚，而你對燒成的磚的質(zhì)量有要求，它必須是一個精確的值，Q克(1<=Q<=10^8)，也就是你要找出一些塊，他們的質(zhì)量和恰好是Q。問是否有可行方案?？吹絅的大小，很誘人吧，很奇怪吧，45？45除以2大約等于22，而使用O(2^N)的爆搜所能承受的最大N值大約也是這么多。于是想到了折半搜索先搜索前22個土塊能組成的質(zhì)量，存在哈希表里，再搜索后22個土塊能組成的質(zhì)量，比如當(dāng)前在后22個土塊中搜到的質(zhì)量和是x，然后在哈希表里查找是否存在Q-x這個值（也就是前22個土塊中是否存在和為Q-x的組合）。USACOprime3在下面的方格中，每行，每列，以及兩條對角線上的數(shù)字可以看作是五位的素數(shù)。方格中的行按照從左到右的順序組成一個素數(shù)，而列按照從上到下的順序。兩條對角線也是按照從左到右的順序來組成。這些素數(shù)各個數(shù)位上的和必須相等。左上角的數(shù)字是預(yù)先定好的。一個素數(shù)可能在方陣中重復(fù)多次。如果不只有一個解，將它們?nèi)枯敵觯ò凑者@25個數(shù)字組成的25位數(shù)的大小排序）。一個五位的素數(shù)開頭不能為0（例如：00003不是五位素數(shù)）輸入：一行包括兩個被空格分開的整數(shù):各數(shù)位上的數(shù)字的和以及左上角的數(shù)字。輸出：對于每一個找到的方案輸出5行，每行5個字符,每行可以轉(zhuǎn)化為一個5位的質(zhì)數(shù).在兩組方案中間輸出一個空行.如果沒有解就單獨輸出一行"NONE"。搜索優(yōu)化？一行行的順序枚舉連樣例都過不了(....)先枚舉兩條對角線，因為他們控制的行列是最多的，而且左上角的數(shù)已經(jīng)確定了。再枚舉中間的一豎列,因為它同樣控制的行列最多,再枚舉最上面一行和最下面一行。此時第3行的2，4兩個數(shù)也可以通過減法得到了。最后枚舉第2，4行，第3行可以通過減法得到。于是所有格子都已經(jīng)確定了，驗證一下就行。由于要適應(yīng)這種奇葩的搜索順序，需要多個數(shù)組記錄滿足條件的素數(shù)，比如已知第1,3,5位的所有素數(shù)，或已知第1位的所有素數(shù)都要預(yù)處理出來。并且每個數(shù)用5個1位數(shù)儲存（也就是用一個大小為5的數(shù)組儲存...），這樣操作方便而且效率高。你問我怎么想出來這種奇葩的搜索順序的？呵呵，我也不知道，看題解才想出來的（如果是考場上想出來真的要靠功力和造化）不過如果知道了這種方法之后，理解起來還是不難的如果不知道哪種搜索方式比較快，可以編個數(shù)據(jù)生成器，自己試試一種方便的調(diào)試方法有某位弱得跟粉一樣的渣詢問我調(diào)試程序的一些技巧，所以我準(zhǔn)備作為飯后甜點講一講~比如你有一個遞歸函數(shù)intwork(intp){...

}然后你發(fā)現(xiàn)好像有的時候p會變成負(fù)值，但是p是負(fù)值就是出現(xiàn)bug的時候，你想跳轉(zhuǎn)到這種時候。那么你可以這么寫intxxx（隨便多定義一個全局變量）intwork(intp){if(p<0)xxx=0;...

}然后把斷點設(shè)在xxx=0那一行處，再點調(diào)試，就可以在運行到那一行時停下，此時正好p是小于零的。為什么要寫xxx=0呢？你寫其他的也是一樣的，比如用p=p代替xxx=0，總之目的就是讓那里有一個語句，有一個東西..不過有的時候編譯器會自動把p=p或者p=p+1-1這種語句過濾掉，因為它會認(rèn)為這是碼農(nóng)們偶爾精神出問題時寫下的廢話HNOI2010matrix矩陣A和矩陣S都是N*M的非負(fù)整數(shù)矩陣。矩陣A的元素都小于P矩陣S的第一行和第一列均為0;且滿足S[i,j]=A[i,j]+A[i-1,j]+A[i,j-1]+A[i-1,j-1]（i,j>1）給出N,M,P，以及矩陣S求字典序最小的矩陣A使得滿足條件。30%：N,M≤10另30%：P=2100%：1＜N,M≤2001＜P≤10如果A的第一行與第一列已經(jīng)確定，那么我們就可以按部就班地算出A的所有元素的值了。這樣一來需要決策的元素個數(shù)就從200的平方變成了399。我們試圖建立A[i,j]與第一行或第一列之間的直接等式關(guān)系。以下是一個較易理解的建立等量關(guān)系的方法：首先不看元素在0到P-1范圍內(nèi)的限制，設(shè)A1,k和Ak,1都為0，并計算將A補全。（此時A中可能有負(fù)數(shù)或者大于等于P的整數(shù)）我們只需要搜索A的第一行，每當(dāng)確定一個元素，就可以更新A[j,1]的取值范圍。根據(jù)公式，除了A[1,1]以外，A[i,1]的取值是互不影響的。不斷更新第一列每個元素的可以取值的范圍，一旦出現(xiàn)有某個元素下界大于上界的情況就剪枝。顯然這樣搜索的字典序是最優(yōu)的。USACOcryptcow農(nóng)民Brown和John的牛們計劃協(xié)同逃出它們各自的農(nóng)場。它們設(shè)計了一種加密方法用來保護(hù)它們的通訊不被他人知道。如果一頭牛有信息要加密，比如"InternationalOlympiadinInformatics"，它會隨機地把C，O，W三個字母插到到信息中（其中C在O前面，O在W前面），然后它把C與O之間的文字和O與W之間的文字的位置換過來。這里是兩個例子：為了使解密更復(fù)雜，牛們會在一條消息里多次采用這個加密方法（把上次加密的結(jié)果再進(jìn)行加密）。一天夜里，John的牛們收到了一條經(jīng)過多次加密的信息。請你寫一個程序判斷它是不是這條信息經(jīng)過加密（或沒有加密）而得到的：搜索按從小到大的順序依次找出C,O,W，然后交換中間的兩個串并將這三個字符刪掉。如此往復(fù)直到?jīng)]有成對的C,O,W，判斷一下最后生成的字符串是否是題目所給的串。由于添加的COW是一起的，因此給出的字符串的字符個數(shù)應(yīng)該等于47（目標(biāo)字符串的長度）+3*k。如果不滿足就可直接判斷無解。除了COW三個字符外，其他的字符的個數(shù)應(yīng)該和目標(biāo)串相一致。如果不一致也可直接判斷無解。一個有解的字符串中，COW三個字母最早出現(xiàn)的應(yīng)該是C，最后出現(xiàn)的應(yīng)該是W，如果不滿足則剪枝。搜索中間肯定會出現(xiàn)很多相同的情況，因此需要開一個hash來記錄搜索到過哪些字符串，每搜索到一個字符串，就判重。對搜索到的字符串，設(shè)不包含COW的最長前綴為n前綴（同樣也可以定義n后綴），那么如果n前綴不等于目標(biāo)串的長度相同的前綴，那么當(dāng)前字符串一定無解，剪枝。N后綴也可采取相同的判斷方法。需要優(yōu)化搜索順序。經(jīng)過試驗我們可以發(fā)現(xiàn)，O的位置對于整個COW至關(guān)重要?？梢哉f，O的位置決定了整個串是否會有解。因此，我們在搜索時，應(yīng)該先枚舉O的位置，然后再枚舉C和W的位置。W要倒序枚舉。在判斷當(dāng)前串的子串是否包含在目標(biāo)串中的時候，可以先做一個預(yù)處理：記錄每一個字母曾經(jīng)出現(xiàn)過的位置，然后可以直接枚舉子串的第一個字母的位置。這樣比用pos要快2倍左右。APIO2011方格染色（這個題目不要求做）USACOfence8農(nóng)民John準(zhǔn)備建一個柵欄來圍住他的牧場。他已經(jīng)確定了柵欄的形狀，但是他在木料方面有些問題。當(dāng)?shù)氐碾s貨儲存商扔給John一些木板，而John必須從這些木板中找出盡可能多所需的木料。當(dāng)然，John可以切木板。因此，一個9英尺的木板可以切成一個5英尺和一個4英尺的木料(當(dāng)然也能切成3個3英尺的，等等)。John有一把夢幻之鋸，因此他在切木料時，不會有木料的損失。所需要的木料規(guī)格都已經(jīng)給定。你不必切出更多木料，那沒有用。（一看就覺得是美式翻譯）在如下的說明中，rail代表的是‘目標(biāo)塊’，board代表的是‘原材料’。采用dfs-id（其實就是從小到大試驗?zāi)芮谐傻膲K數(shù)）來搜索每一個rail來源的board。以下技巧都是針對這種搜索順序來制定的。很容易就能注意到，由于每塊rail的價值是相等的——也就是說切小的要比切大的來的劃算。那么我們在搜索能否切出i個rail的方案是自然要選最小的i個rail來切。經(jīng)過一些實驗可以發(fā)現(xiàn)，先切大的rail比先切小的rail更容易提前出解。先切大的board要比先切小的更快。由于r最大可能是1023，但是rail長度的范圍卻只有0~128，提醒了我們有很多rail的長度會是相同的。為減少冗余，若有rail[i+1]=rail[i]，則rail[i+1]對應(yīng)的board一定大于等于rail[i]對應(yīng)的board。如果board[i]=board[i+1]，那么從board[i]切下的最大的rail一定大于等于從board[i+1]切下的最大的rail。對于切剩下的board（無法再切下rail），統(tǒng)計一下總和。如果大于board長度總和-rail長度總和，一定無解。HNOI2011任務(wù)調(diào)度搜索+貪心+隨機調(diào)整對于每個隨便順序的點，暴力搜索他屬于類型1還是類型2。注意N<=20，這種指數(shù)復(fù)雜度是可以接受的。并且我們注意到，機器a一定是先處理完所有類型1的任務(wù)再處理完所有類型2的任務(wù)。機器b一定是先處理完所有類型2的任務(wù)再處理完所有類型1的任務(wù)。而且如果有兩個第1類任務(wù)P,Q,在a機器上P先完成，那么在b機器上也是讓P先完成。否則一定能夠通過調(diào)整變成這種情況，且答案不變。貪心的部分然后我們對于先要在a機器上運行的任務(wù)，以需要在b機器上運行的時間(從小到大)作為第一關(guān)鍵字，需要在a機器上運行的時間作為第二關(guān)鍵字，進(jìn)行排序。將排序結(jié)果作為a機器處理的先后順序。對于先要在b機器上運行的任務(wù)，以需要在a機器上運行時間作為第一關(guān)鍵字，在b機器上運行時間作為第二關(guān)鍵字排序。這只是一個較優(yōu)的安排。還是會有一個點過不了。隨機調(diào)整的部分在此基礎(chǔ)上，每次在第1類任務(wù)中隨機選擇兩個任務(wù)，交換它們的位置。再在第2類任務(wù)中隨機選擇兩個任務(wù)交換它們的位置。如果算出的答案比原來優(yōu)，那么就接受這種調(diào)整。

即使交換2000次左右，依然很快。均分紙牌有N堆紙牌，編號分別為1，2，…，n。每堆上有若干張,但紙牌總數(shù)必為n的倍數(shù).可以在任一堆上取若干張紙牌,然后移動。移牌的規(guī)則為：在編號為1上取的紙牌，只能移到編號為2的堆上；在編號為n的堆上取的紙牌，只能移到編號為n-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上?，F(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多。SampleInput498176SampleOutput6貪心按照從左到右的順序移動紙牌。如果第i堆的紙牌數(shù)不等于平均值v：1．若a[i]>v，則將a[i]-v張從第i堆移動到第i+1堆；2．若a[i]<v，則將v-a[i]張從第i+1堆移動到第i堆。若n=3，三堆紙牌數(shù)分別為為1，2，21的話，v=8,那么讓第一堆的紙牌數(shù)達(dá)到8的時候，需要從第二堆拿7張過來，此時第二堆的紙牌數(shù)是-5。這樣很奇怪嘛？其實我們只是改變了移動牌的順序而已，而算出的最小操作次數(shù)是正確的。我們一定可以通過調(diào)整操作的順序，使得每堆的牌數(shù)任何時候都大于等于零，比如每次只考慮將牌數(shù)大于v的牌堆的牌移到相鄰位置（這樣的操作一定存在）。NOIP2010提高組第三題簡要題意：給你n個點，有些點之間有帶權(quán)邊，你要把這些點分為兩個集合，使得兩個端點在同一集合中的邊的最大邊權(quán)盡量小。二分答案，用二分圖判斷是否合法這樣是O(nlogn)的有沒有接近O(n)的做法？能貪心嗎？如何貪心？假設(shè)題目一開始就把邊按照邊權(quán)從大到小排序了。從大到小考慮每一條邊enemy-friend并查集這道題網(wǎng)上有很多題解，這里就不細(xì)講了SGU246請問，在一個長度為P的圓環(huán)的整點上最多能夠放置多少個1，使得所有的1之間在圓環(huán)上的距離都不為Q.1<=Q<=P<=10^18將那些整點標(biāo)號為0~P-1.如果我們在0處放置一個1，那么Q處便不能夠放置1了，于是根據(jù)貪心的思想，我們在2*Q處放置一個1....。如果這樣能夠把所有的位置都確定，那么答案就是Pdiv2。如果P與Q不互質(zhì)，那么這樣做是不能確定所有位置的。比如P=12，Q=3.考慮有幾個這樣的不相關(guān)的部分。應(yīng)該是有g(shù)cd(P,Q)個的，而且每個部分的長度都是P/gcd(P,Q).所以答案就是gcd(P,Q)*(P/gcd(P,Q)div2)變成回文串給你一個小寫字母組成的字符串，長度為N。每次操作，你可以交換串中相鄰的兩個字符。請你使用最少的操作次數(shù)，讓字符串變成一個回文串。如果有解則輸出最少操作次數(shù)，如果無解輸出WTF.1<=N<=10^6看到這么大的數(shù)據(jù)范圍，驚呆了，感覺應(yīng)該是類似貪心的做法。最多只允許一種字符的出現(xiàn)次數(shù)是奇數(shù)，且它會出現(xiàn)在最中間位置。否則無解。如果有出現(xiàn)奇數(shù)次的字符，先將這種字符的排在最中間的那個（比如有7個這種字符，就選第4個）移到整個串的最中間去。然后如果對于某種字符，在串的左半邊的數(shù)量跟在串的右半邊的數(shù)量不等，則進(jìn)行跨越中線的調(diào)整（調(diào)整時你可以讓左半邊的的一個調(diào)整到右半邊去（剛調(diào)整到中間字符的右邊就可以了），再讓右半邊的一個到左邊去，這樣交替調(diào)整...其實你也可以讓所有需要從左邊調(diào)整到右邊去的先調(diào)整，但要注意由于此時原來中間那個字符的位置可能就不在中線上了，所以你需要調(diào)整到的位置是原來中間那個字符的位置的右邊的相鄰位置，而不一定是‘跨越中線’。）事實上不管用這里說的哪種方法調(diào)整，都是最優(yōu)的。接下來，我們可以只調(diào)整左半邊。先使得左半邊最左的字符等于右半邊最右的字符..然后再使左半邊第二左的字符等于右半邊第二右的字符...這樣一定是最優(yōu)的。如果只要求輸出答案，也可以考慮上課時說的‘求逆序?qū)€數(shù)’的方法。不過直接調(diào)整，得到的結(jié)果也是一樣的。SGU296給你一個有N位的數(shù)n，你需要刪去其中P位，并使得剩下的數(shù)盡量大。1<=P<N<=1000選取的最高位只能是原數(shù)的1~N–P+1位我們應(yīng)該選取其中最大的數(shù)如果有多個最大的數(shù)，選取位置最靠前的（也就是高位）次高位的方法類似，注意要保證當(dāng)前已經(jīng)刪的數(shù)不能超過題目要求。SGU165給你n個數(shù)a[1]..a[n],其中-50<=a[i]<=50對每個i都成立。且sigma{a[i](i=1~