0w1

Stack

IOI 15 Teams ( Persistent Segment Tree + Stack Monotonicity )

PEG Judge - IOI '15 - Teams 就是一個蛋疼。。改天補說明。 這個問題有兩種解法,一種是霍爾定理+DP,似乎code比較短也比較好寫,但我對二分匹配完全沒概念Orz。。 只能用持久化線段樹去很直觀的搞,雖然說這就是想定解。 首先因為每個學生的屬性是二維的,…

UVA 12265 Selling Land ( Stack Monotonicity )

UVa Online Judge 白訓練指南的一道經典的單調棧好題。思路是先想像我們大致會做一個高度單調遞增的維護,注意到要判斷一個左上角到當前的右下角構成的矩形周長是否足夠優,只需要知道它的高和當前的列的差( 寬 )。由於只有寬是動態增加的,所以只要能不斷的…

CFR 635 E. Package Delivery ( Greedy + Stack Monotonicity )

Problem - E - Codeforces Basically when the car is in gas station i, there is one and only one optimal decision. If it is possible to move to the first station with cheaper gas price after this one, buy the minimum amount of gas here in or…

Introduction to stack optimizations

Stacks can be used to maintain for monotonous properties, can optimize for many problems, but only if you can discover the monotony in the problem. Here are some problems for exercise from the ant book. 3250 -- Bad Hair Day POJ 3250 Bad Ha…