演算法-資料結構

1/3ページ

CSU暑期集訓day04_遞推_動態規劃_抽獎概率

題目: HDU 2006’10 ACM contest的頒獎晚會隆重開始了!  為了活躍氣氛,組織者舉行了一個別開生面、獎品豐厚的抽獎活動,這個活動的具體要求是這樣的:  首先,所有參加晚會的人員都將一張寫有自己名字的字條放入抽獎箱中;  然後,待所有字條加入完畢,每人從箱中取一個字條; […]

CSU暑期集訓day05_DFS_單源最大權路徑

題目: 有一棵由N個結點構成的樹,每一條邊上都有其對應的權值。現在給定起點,求從該點出發的一條路徑(至少有一條邊)使得這條路徑上的權值之和最大,並輸出這個最大值。 Input 第一行一個正整數T,代表資料組數。每組資料第一行兩個正整數n(2<=n<=10^5),s(1<=s< […]

CSU暑期集訓day05_DFS_N皇后問題

題目: 在N*N的方格棋盤放置了N個皇后,使得它們不相互攻擊(即任意2個皇后不允許處在同一排,同一列,也不允許處在與棋盤邊框成45角的斜線上。  你的任務是,對於給定的N,求出有多少種合法的放置方法。 Input 共有若干行,每行一個正整數N≤10,表示棋盤和皇后的數量;如果N=0,表示結束。 Ou […]

CSU暑期集訓day06_平衡等式

題目: 寫一個程式要求當輸入在整數範圍內的一個整數R後, 計算機便會檢查,在下式□處能否填上“+”、“-”或“×”號湊成相應等式。如能湊成,則印出所有這些等式的個數。注意,考慮符號的優先順序。 1□2□3□4□5□6□7□8□9=R Input 只有一行,就是一個整數R。 Output 只有一行,就 […]

(二) 連結串列 – 經典問題彙總

(一)找到連結串列的倒數第n個節點     1.這個問題不難,我們可以兩次遍歷連結串列,第一遍記錄連結串列的長度L,第二遍從頭遍歷連結串列,找到L-n 1的位置的節點,然後輸出,這樣時間複雜度為o(n),空間複雜度為o(1)     2.上面的方法看起來不錯,但是我們還可以有更好的方法,我們僅僅使用 […]