HDU 3607:線段樹 + 離散化 + DP 優化
問題描述 有 N 個連續盒子,每個有高度 h 和價值 v。從任意盒子進入,只能向右移動,且只能跳到高度更高的盒子。求可獲得的最大價值和。 解題思路 DP 狀態
UVA 10765 Doves and bombs:雙連通分量與割點應用
問題描述 給定一個連通無向圖,刪除某個頂點後圖分裂成幾個連通塊。按連通塊數從多到少、頂點編號從大到小輸出前 m 個結果。 解題思路 利用 Tarjan 算法求
HDU 2121 Ice_cream's world II:最小樹形圖 (朱劉算法)
問題描述 有向圖 N 點 M 邊,每條邊有代價。需選擇一個根(首都),使從根可達所有點,且生成樹總代價最小。若無解輸出 impossible,否則輸出最小代價和
HDU 3152 Obstacle Course:BFS + 優先隊列求最小路徑和
問題描述 N×N 網格,每個格子有代價。從 (1,1) 走到 (N,N),只能上下左右移動,求路徑上格子代價之和的最小值。 解題思路 經典的網格最短路問題,邊
BZOJ 1116 CLO:並查集判斷圖匹配
問題描述 給定一個無向圖,問是否存在一個點與邊的匹配,使得匹配數等於點數(即每個點恰好匹配一條邊,每條邊至多匹配一個點)。 解題思路 這等價於判斷圖中每個連通
九度 OJ 1049:字符串刪除指定字符
問題描述 輸入字符串 s 和字符 c,刪除 s 中所有字符 c,輸出結果。多組測試數據。 解法一:直接遍歷輸出 讀取字符串和字符,遍歷字符串,遇到非 c 字符
BZOJ 1107 駕駛考試:LIS 與樹狀數組優化 DP
問題描述 給定一條道路,有起點、終點和若干中間點。某些點之間有單向道路(上坡/下坡)。求最長可行駛路徑長度,並扣除起始即可到達所有終點的點數。(具體題意較複雜,
UVA 11997:K 個數組取前 K 小和(優先隊列歸併)
問題描述 給定 k 個長度均為 k 的數組,每個數組取一個數相加,共有 k^k 種和。求最小的 k 個和並輸出。 解題思路 利用「兩兩歸併」策略:先將第一個數
UVA 620 Cellular Structure:字符串模式識別
問題描述 微生物細胞鏈由 A、B 兩類細胞組成。健康生物的生長遵循三種規則: 簡單階段:空鏈 → A 完全生長階段:在右側添加 AB 誘變階段:在左側加 B,
Codeforces 523D:排序與優先隊列模擬銀行排隊
問題描述 有 n 位顧客和 k 個窗口。每位顧客給出到達時間和辦理所需時間。顧客按到達時間先後服務,每個窗口同一時刻只能服務一位。輸出每位顧客離開時間。 解題
LeetCode:Reverse Words in a String 字符串單詞反轉
問題描述 給定一個字符串,以單詞為單位反轉順序。單詞由非空格字符組成,單詞間可能有多個空格,結果中單詞間僅保留一個空格,且首尾無空格。例如 i am echo
UVA 10404 Bachet's Game:完全背包與博弈論
問題描述 有 n 塊石子,兩人輪流取走,每次必須從給定的 m 個數字集合中選擇一個數取走對應數量的石子(集合中必含 1)。取走最後一塊石子者獲勝。Stan 先手
Codeforces 500E New Year Domino:倍增與線段樹離線解法
問題描述 有 n 個多米諾骨牌按 x 座標遞增排列,第 i 個位於 x=p_i,長度為 l_i。推倒第 x_j 個骨牌,它會向右倒下,觸碰到的骨牌也會連鎖倒下。
UVA 11796:兩條狗的行走路徑最遠與最近距離
問題描述 給定兩條狗的行走路線(各自由一系列點構成的折線),兩狗同時出發、同時到達,且速度均勻。求它們在行走過程中的最遠距離與最近距離之差。 解題思路 將問題
HDOJ 4786 Fibonacci Tree:克魯斯卡爾算法與費波納契數應用
問題描述 給定一個包含 N 個頂點和 M 條邊的無向圖,每條邊被染成白色或黑色。問是否存在一棵生成樹,使得其中白色邊的數量是某個正費波納契數(費波納契數列定義為
LeetCode 題解:Next Permutation 算法詳解與實現
問題描述 實現 nextPermutation 函數,將給定數字序列重新排列為字典序中下一個更大的排列。若不存在更大的排列,則重新排列為最小的排列(即升序排列)