0w1

Entries from 2016-02-10 to 1 day

UVA 1423 Guess ( 拓撲排序 + 並查集 )

UVa Online Judge 用前綴和去想,若矩陣某個 ( i, j ) 為 +, 代表 pa( j ) - pa( i - 1 ) > 0, 同時意味著 pa( i - 1 ) ( j ) 建有向邊,最後的拓撲序就能是他們合法的大小關係。比較特別的是當pa( j ) - pa( i - 1 ) == 0 的時候,因為這代表 pa( j ) == pa…

UVA 10054 The Necklace ( Euler's Path )

UVa Online Judge 可以把顏色當作節點,則珠子就是節點之間的邊,題目要求就等價於問是否能用每個邊恰好一次構成一個迴路。這就是經典的尤拉迴路問題。 若滿足"所有點構成的圖聯通且不存在奇度數的節點"則必有尤拉迴路( 而且隨便走都是 ),而尤拉路徑除此之…

UVA 11624 Fire! 水題BFS

UVa Online Judge 一個大水題,先對火做BFS預處理每個格子發生火的最早時間,然後再搞人的就行了。注意會需要用到 ( t, x, y ) 三個變數一組的某種結構,以前都搞什麼雙重pair 真是太恐怖了,tuple我現在還不太會用。。寫完這題就想,我以後就像這樣子做吧。…

Monotonic optimal split point DP ( 凸性 2D / 1D 優化 )

http://sprout.tw/oj/pro/144/ Short summary for the problem: given an array of N ≤ 1000 numbers a[ 1 ], a[ 2 ] .., a[ N ], each pair of numbers a[ i ], a[ i + 1 ]adjacent to each other can merge into a new single number, producing a[ i ] + …

UVA 12538 Version Controlled IDE ( 持久化隨機二元搜尋樹 )

UVa Online Judge - Offline Here are some good resources I read through in order to understand how to implement persistent RBST for this problem. morris821028.github.io blog.csdn.net #include <bits/stdc++.h> using namespace std; const int MAXMEM = 5e7; co</bits/stdc++.h>…

Persistent segment tree

2104 -- K-th Number Given n ≤ 1e5 numbers a1, a2 .., an, then there are m ≤ 1e5 queries [ l, r ], for each query, answer the k-th minimum number among al, a(l + 1) .., ar. First we discretize the integers so that there are at most 1e5 inte…