amoshyc

# Your init script
#
# Atom will evaluate this file each time a new window is opened. It is run
# after packages are loaded/activated and after the previous editor state
# has been restored.
#
# An example hack to log to the console when each text editor is saved.
#
# atom.workspace.observeTextEditors (editor) ->
#   editor.onDidSave ->

amoshyc

PTC 2015/12_1 C: Warehouse

題目

比賽時，記憶體並沒有限制，題目放上 etutor 後，記憶體有 64MB 的限制， 造成 next 陣列開不出來（etutor 竟然把 MLE 回報成 TLE…）。 現在有新增第二筆測資，N <= 500，這樣就能在 64MB 的限制下解出該筆測資。

分析

amoshyc

PTC 2015/12_1 A: Constrained 0-1 Knapsack Problem

題目

給定一些物品的價值與重量，在滿足 Wa <= 總重 <= Wb 的條件下，選至少 L 個物品出來，並使單位重量的價值 ceil(sum(w) / sum(v) 最大化。

分析

乍看之下很像可以用二分搜解的平均最大化的問題，但仔細分析可以發現， 新增加的條件會造成二分搜解法中的單調性消失，所以不能使用二分搜來解這題。

amoshyc

二分搜：講解

以下出現 A[l, r] 代表 A 陣列中 [l, r] 這個區間。 同理 A[l, r) 代表 A 陣列中 [l, r) 這個區間。

以下範例皆不處理 IO 的部份，都假設變數皆已被讀入。

基本使用

大一時學過，我們可以用二分搜在一個單調（遞增或遞減）的陣列中，尋找某個值在哪裡：

amoshyc

Poj 3662: Telephone Lines

題目

分析

K lengths of cable for free 這是指「K 條 cable 免費」，而不是「長度大於 K 的免費」…

觀察可得，當我們確定 longest remaining cable = L 時， 我們可以用最短路徑演算法得到此時從 0 走到 N-1 最少需要幾條 > L 的邊（d[N-1]），

amoshyc

Poj 3185: The Water Bowls

題目

分析

上一題 poj 3276 的簡化（K=3）與小變形（首尾可反轉二個）

相當於只能反轉連續三個， 並且反轉區間的頭從 -1 開始直到 N-2（不是 N-3），

amoshyc

Poj 3276: Face The Right Way

題目

分析

書上例題…… 枚舉 + 貪心（dp）

我們枚舉 K，看 K 固定時需要多少次反轉次數，最直覺的寫法是：

amoshyc

Poj 2100: Graveyard Design

題目

分析

尋找一個連續區間，他們的平方和等於 q，問這種區間有幾個，分別是那些區間……

爬行法輕鬆解

amoshyc

Poj 2739: Sum of Consecutive Prime Numbers

題目

分析

爬行法…

先建質數表，然後在質數表上爬行。

amoshyc

Poj 2566: Bound Found

題目

爬行法（尺取法）

※ 以下都是我自己著墨出來的，不保證正確

※ 以下 r+ 指的是比 r 大的數