SRM 622 Div2 L3 Subsets:回溯剪枝求最優子集
問題大意 給定整數數組,選擇子集使 sum + ones_cnt = product,最大化 sum + ones_cnt - product(即超出部分)。1
HDU 4183 Pahom on Water:最大流建模
問題重述 平面上多個圓(中心座標、半徑、頻率)。圓相交可通行。從起點到終點再返回。去程只能從低頻率向高頻率移動,返程反向。除起終點外每圓最多經過一次。問是否可行
UVA 10795 A Different Task:漢諾塔變體與狀態遞迴
問題大意 n 盤漢諾塔,給定初始狀態與目標狀態(每盤所在柱 1/2/3),求最少步數轉換。 遞迴策略 找最大不相同盤 k(從 n 向下)。 將 1..k-1
HDU 3473 Minimum Sum:劃分樹求區間中位數與絕對值和
數學轉化 對區間 [l,r] 求 min_x Σ |a_i - x|。最小值在中位數處取得。設中位數為 m,答案 = (右側元素和 - 右側個數*m) + (左
HDU 4417 Super Mario:劃分樹解決區間第 K 大
問題大意 長度 n≤1e5 序列,m≤1e5 查詢:區間 [L,R] 中 ≤ H 的數個數。等價於查詢第 k 大與 H 比較,k 為二分搜尋。 劃分樹原理
UVA 10090 Marbles:擴展歐幾里得與貪心
問題模型 兩種盒子:容量 n1 價格 c1,容量 n2 價格 c2。恰裝 n 顆珠子,最小化成本。n1*x + n2*y = n,x,y ≥ 0 整數,最小化
BZOJ 3519 [ZJOI2014] 消棋子:模擬與 Set 維護
問題大意 r×c 棋盤,n 種顏色各兩顆棋子。操作:選空格 (x,y) 及兩方向(上下左右),若兩方向最近棋子顏色相同則消除。給定 m 次操作,求實際消除數;並
ZOJ 2112 Dynamic Rankings:主席樹解決動態區間第 K 大
問題大意 序列長度 N≤50000,操作 M≤10000:查詢區間 [l,r] 第 k 小,或單點修改。值域 < 1e9。 主席樹核心思想 值域離散化映射到
STUN/TURN/ICE 協議在 P2P SIP 中的應用(一)
基本概念 打洞:內網主機主動向外發送封包,在 NAT 建立映射,允許特定外部回應穿透。 穿透:外部封包利用已建立的映射到達內網。 P2P 需雙方打洞,C/S
Effective C++ 條款 30:透徹理解 Inline 的利弊
Inline 基本觀念 Inline 函數以函數本體取代呼叫點,消除呼叫開銷。但可能導致目標碼膨脹,降低指令快取命中率。若函數體極小,Inline 反而可能減小
SDUT OJ 1124 飛越原野:三維 BFS 最短路
問題描述 m×n 網格,P 平地、L 湖泊。從 (1,1) 到 (m,n)。可上下左右移動(1 時間),或直線飛行任意距離(1 時間),總飛行距離 ≤ D。飛行
HDU 3118 Arbiter:判定奇環與二分圖
問題轉化 圖中不允許奇環。每走一步狀態翻轉,回到起點時狀態必須相同。求至少刪除幾條邊使圖無奇環,即使圖成為二分圖。 解法 N ≤ 15,狀態壓縮枚舉點集分為兩
HDU 4089 Activation:概率 DP 方程求解
問題模型 n 人排隊,Tomato 第 m 位。隊首每次:失敗留隊 (p1)、斷線移至隊尾 (p2)、成功離隊 (p3)、服務器崩潰 (p4)。求崩潰時 Tom