1、雅虎:1. 對于一個整數矩陣，存在一種運算，對矩陣中任意元素加一時，需要其相鄰(上下左右) 某一個元素也加一，現給出一正數矩陣，判斷其是否能夠由一個全零矩陣經過上述運算得到。2. 個整數數組，長度為 n,將其分為m份，使各份的和相等，求m的最大值比如3，2，4，3，6可以分成3，2，4，3，6 m=1;3,62,4,3 m=23,32,46 m=3 所以m的最大值為3解：poj 1011，搜索+強剪枝Descripti onGeorge took sticks of the same len gth and cut them ran domly un til all parts became

2、at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All len gths expressed in un its a

3、re in tegers greater tha n zero.OutputThe output should contains the smallest possible length of original sticks, one per line.首先說一下這個題的解題思想。1. 選取某一個開始長度，開始組合小木棒，這個開始長度的限制條件為不小于木棒最大長度，不大于所有木棒長度和，能被長度和整除2. 從可用的最長的那根小木棒開始組合木棒，找出所有的結果集，找到結果集后開始組合下一根木棒。3. 直到所有的小木棒都被組合完成，搜索結束。http:/blog.csd n.n et/night_

4、blue/article/details/2966056思路二：1.le n=maxai & len |sum(ai)2. 為了避免重復搜索，令每個大S的組成中，小S的長度依次遞減，這樣就需要在搜索之前對ai排序；全部的大 S的第一段小S依次遞減3. 如果在某層搜索中，嘗試將aj加入到第i個大S的組成中，如果最終aj沒有被使用，且aj+1=aj，不需要繼續嘗試 aj+14. 如果此次是在嘗試第i個大S的第一段小S aj，aj為當前可以被使用的最長的小S,如果此次嘗試失敗，直接退出搜索，即退回到對第 i-1個大S的搜索。試想：失敗說明現在使 用aj是不可行的，那么什么時候使用aj呢？如果沒有退出

5、搜索，肯定會在之后的搜索中使用aj，因為所有的小S必須都使用。之后的aj和最初嘗試的aj有什么不同呢？沒有不 同，它們等價，因此之后也不會成功，不需要繼續搜索。都一致：先對這些數進行排序；1. #in elude 2. #in elude 3. using n amespaee std;4.4. int sticks64, n, len, num;(num 為可以得到多少對)5. bool used64;7.6. bool eompare( int a, int b)7. 8. return a b;9. 12.13. bool dfs( int cur, int left, int leve

6、l)14. /cur:當前已經計算的木棒編號，left:該段還剩的長度，level:已經成功的木棒 數15. if(left = 0) /匹配一根木棒成功16. if(level = num-2)17. returntrue;18. for(eur = 0; usedeur; eur+)/ 找到第一個還沒被用的19. ;20. usedeur = true;21. if(dfs(eur+1, le n-stickscur, level+1)22. returntrue;23. usedeur = false;24. return false;1.32.33

7、.5.56.57. else if(cur = n-1)/ 最后一根了return false;for( int i = cur; i left)con ti nue;usedi = true;if(dfs(i, left-sticksi, level)return true;usedi = false;1.1. 不行的話，就不會使用這個return false;int mai n()while(ci nn) if(n = 0)break;int sum = 0;fo

8、r( int i = 0; i n; i+) scan f(%d, &sticksi);sum += sticksi;sort(sticks, sticks+n, compare); /由大到小排序bool end = false;for(len = sticks0; len = sum/2 ; len+) if(sum%le n = 0) 58.usedO = true;59.num = sum/le n;60.if(dfs(0, le n-sticksO, 0) 61.end = true;62.prin tf(%dn, le n);63.break;64.65.used0 = false

9、;66.67.68.if(!e nd)69.printf(%dn, sum);70.memset(used, 0, sizeof(used);71.72.system(pause);73.return 0;74. 搜狐：3. 四對括號可以有多少種匹配排列方式？比如兩對括號可以有兩種：()()和()卡特蘭數(Catalan)例子1:Cn=n對括號正確匹配組成的字符串數，例如3對括號能夠組成：()()() ()()() ()()()()例子2 : Cn= n+1個數相乘，所有的括號方案數。例如，4個數相乘的括號方案為：(ab)c)d(a(bc)d (ab)(cd) a(bc)d) a(b(cd)例

10、子3： Cn=擁有n+1個葉子節點的二叉樹的數量。例如4個葉子節點的所有二叉樹形態：分析：卡特蘭數”除了可以使用 公式計算Cn=C (n，2n)-C( n-1，2n)，也可以采用分級排列法”來求解。以n對括弧的合法匹配為例，對于一個序列()而言，有兩個左括弧，和一個右括弧，可以看成 抵消了一對括弧，還剩下一個左括弧等待抵消”，那么說明還可以在末尾增加一個右括弧，或者一個左括弧，沒有左括弧剩余的時候，不能添加右括弧。arr = new doublen + 1;/arr 代表有k個括弧的時候，剩余(個數為i的排列方案個數arr1=1；double Catala n(i nt n)if (n = 0

11、) return 1;for (int i = 2; i = 2 * n; i+)var m = i = n ? i : 2 * n + 1 - i;for (i nt j = (i - 1) & 1; j 0) arrj - 1 += arrj;if (j j位置的這些括號的最大組成種數，dpij = dpi-1j-1 /i是（,j 是），并且他們搭配+ sigama（dpik * dpk+1j）, i 與 k 搭配，k+1 與 j 搭配,ik0 iak & k=0&k0）maxLe nln cr0=1;maxLenlncri表示以i結尾的最長遞增子序列長度。代碼如下：/*maxLenlnc

12、ri表示以i結尾的最大遞增子串長度*/maxLenlncri = max maxLenlncrk+1 if aiak ( k=0&k0);int maxLe nln cr(i nt* p, int len)int* maxLe nlncr=new in tle n;int maxLe n=1;/*Default value=1*/for(i nt i=0; ile n; i+)maxLe nln cri = 1;for(i nt i=1; ile n; i+)for(i nt k=0; k ak)maxLe nln cri=max(maxLe nln crk+1, 1);if(maxLe nl

13、n crimaxLe n)maxLe n=maxLe nln cri;retur n maxLe n;5. 一種分情況的二分：首先觀察這個序列，先下降，然后突然上升(暫且叫斷點吧)，接著又下降，而且有個性質(* )斷點前面的所有數都比斷點后面的所有數小！令當前二分的區間是l,h，那么這個區間有 3中可能性：(1) 落在斷點前的那個下降區間里面；(2) 落在斷點后的那個下降區間里面；(3 )跨區間。我們看怎么判斷當前落在哪個區間里，另a是原來的數組如果al ah，由性質(*)得到不可能是跨區間的(否則因為I在斷點前的區間,h在斷點后的區間，那么肯定有alah)，那么只可能是(1)或者(2)，這樣這個區間就是普通的下降區間，用常規的二分在這個區間