斑的家

A. Dima and Guards

題意：有 n 根柱子，每個柱子旁有2個 guards ，你想要收買其中一根柱子的2個guards 。

每個 guard 可以接收飲料或餅乾。但是每個人對這2者的價格都不一樣，他們只接受比某個

價格還高的物品。

你有 m 元，問能不能達成任務。

題解： 假設guard a 可接受飲料的價格為t1, 餅乾為t2 , guard b 為 t3,t4 。

若 min(t1,t2) + (t3,t4) <= m 那麼就有解。

B. Dima and To-do List

題意：A₁,A₂...A_n 數字形成的陣列，另外還有一個數字 k 且 k | n 。

問從陣列中的哪個位置 s ( 0< s < k )開始 ，使得  sum = A_s + A_(s+k) + A_(s+2k) ... A_(s+kn) 最小。

題解： 直接算。

C. Dima and Salad

題意：想要做一盤salad ，做salad 的食材(ai,bi) ,i < n 表示甜度及卡路里，找出甜度最大且滿足以下式子。

題解：將式子轉換一下變成

這樣子題目就是knap-sack 的問題了，可以想成weight,value  = (ai - k*bi, ai)，找出

一種組合使得 weight = 0 ，且value 最大。

D. Dima and Trap Graph

題意：有一個圖，每個邊上有2個值[l,r] ，且l < r 。

loyalty 表示[a,b] 的差值。

想要從點1 走到點n 帶著loyalty ，要通過某edge [l,r] 要滿足 l <= a < b <= r。

問最大loyalty 是多少？

題解：若有一條path ，想要完整通過，那麼loyalty 是[ max(l_i), min(r_i) ] 。

可是不知道path 是哪一條？

從另一個角度想，是否有某個邊[ l,r] 的 [l , h] , h <=r 是 loyalty ？

首先從一條path 有2個邊觀察， [l₁,r₁], [l₂,r₂] ，如果兩者有交集那麼

loyalty 就可能是 [l₂,r₁] 或 [l₁,r₂] 。3個邊以上請自行prove 。

那麼我們可以對每條邊，binary search x ，[l_i , x ] , l_i <=x <= r_i 。

 然後用bfs ,dfs 問可否能從點1走到點n 。

E. Dima and Magic Guitar

題意：有一個二維陣列 n x m ，每個entry aij 有值 < k 。

有一個陣列 A_i,  。想要找出最大 f(A_i,A_i-1) = | x₁ - x₂ | + | y₁ - y₂ | ， a_x1,y1 = A_i  a_x2,y2 = A_i-1。

題解：根據絕對值的性質。

| x₁ - x₂ | + | y₁ - y₂ | 可能是

x₁-x₂+y₁-y₂

(-x₁)+x₂+y₁+(-y₂)

x₁-x₂+(-y₁)+y₂

(-x₁)+x₂+(-y₁)+y₂

對於(x₁,y₁) 它在絕對值中佔有的合(稱為subsum)可能是

Case 1 ：x₁+y₁,

Case 2 : -x₁+y₁,

Case 3 : x₁-y₁,

Case 4 : -x₁-y₁。

對於(x₂,y₂)來說也一樣。

(x₁,y₁) 要和(x₂,y₂) 算出| x₁ - x₂ | + | y₁ - y₂ | 的話，

可能是Case 1 + Case 4 = ( x₁- x₂) + (y₁- y₂)。

或是Case 2  + Case 3  = (-x₁+ x₂) + (y₁- y₂)

或Case 3 + Case 2

or Case 4 + Case 1。

這題先算出a_i,j 中的(i,j) 在絕對值中佔的合。

然後對於A_i 去找出它最大a_x1,y1 = A_i 的subsum 和A_i-1 找出 a_x2,y2 = A_i-1 的subsum 。

加起來最大的就是答案。