0w1

Entries from 2016-03-13 to 1 day

TIOJ 1063 Area ( Deque Monotonicity )

1063 - 最大矩形(Area) | TIOJ INFOR Online Judge 跟這題很像的,不過這次是要求矩形面積。 UVA 12265 Selling Land ( Stack Monotonicity ) - 0w1 很容易注意到,如果先發生的( 左邊開始的 )矩形比後發生的矩形高,那只要先發生的矩形好好的,後面發生的矩…

UVA 12265 Selling Land ( Stack Monotonicity )

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

JOI 10 本選 Shopping in JOI Kingdom ( Dijkstra )

Shopping in JOI Kingdom | Aizu Online Judge 店のある町からMSSPをして店のない町から一番近い店への最短経路を計算する。そうしたあと、答えは max{ round( dis[ i ] + dis[ j ] + weight[ i ][ j ] / 2 ) } Ɐ e( i, j ) ∈ E だとわかる。 #include <bits/stdc++.h> usin</bits/stdc++.h>…

JOI 10 本選 Books ( DP )

Books | Aizu Online Judge ナップサックするだけ。 #include <bits/stdc++.h> using namespace std; const int MAXN = 2e3 + 3; const int MAXK = MAXN; const int MAXC = 1e5 + 5; const int MAXG = 10 + 2; void upmax(int &x, int v){ if( x < v ) x = v; } int n, k; i</bits/stdc++.h>…

JOI 11 本選 Festivals in JOI Kingdom ( MSSP Dijkstra + Kruskal + Doubling LCA )

Festivals in JOI Kingdom | Aizu Online Judge 先に全ての町について、一番近い祭りの距離を計算する。そして、最大全域木をその最短距離に基づき作る( 祭りに近い方からと遠い方から来ても、近い方を取る )とクエリ( u, v )に対しての答えは ( u, lca( u, …

JOI 10 本選 Bug Party ( Binary Search + MLE Persistent Segment Tree / AC Priority Queue )

Bug Party | Aizu Online Judge 很容易想到,如果固定最小值b,那麼我們必須由小到大拿進所有a,直到 sum( a ) ≤ b * cnt 不再成立。由於要快速( O( lg n ) 以下 ) 求出大於等於某個b值的最小的x個a值的總和,條件形式複雜,如果不加功夫用持久化線段樹亂搞…