Problem - B - Codeforces We will simply go as far as we can each time, so we will sweep from left to right, that from right to left, ... until there are no more left. void solve(){ int N; cin >> N; vi A( N ); for( int i = 0; i < N; ++i ) c…

Problem - C - Codeforces First, it is easy to observe that the largest value in the initial input is definitely part of the answer. So we will continually take out the largest element from the set, and remove each pair of gcds created by t…

Problem - D - Codeforces I thought this was quite difficult, despite the technique required was not that advanced. The key is to come up with the dp form: dp[ i ][ j ][ k ] : maximal length of non-decreasing subsequence of A concatenated k…

D: Stamp Rally - AtCoder Grand Contest 002 | AtCoder Finally found an easy problem to start familiarising with parallel binary search ( I thought it is called holistic binary search ). pekempey.hatenablog.com The link above really helped, …

Problem - D - Codeforces 本來以為開頭提的持久化只是唬人的，但最後我還是用了 ( ? )。考慮到總共最多只會改變 Q = 1e5 個行，意味著最多只需紀錄 1e5 * 1e3 個位元。這是 512 MB 能勉強容下的。那麼就用持久化的思想，只有被改變的新創，否則統一指到池裡…

Problem - C - Codeforces 網路上找到了這張圖。以前學過這個定理。 滿足畢氏定理 a^2 + b^2 = c^2 的 a, b, c 必然滿足且各自唯一對應到 a = 2 * m * n, b = m^2 - n^2, c = m^2 + n^2 整數解 ( a, b, c ) 必然滿足一組整數的 ( m, n ) 且 m ≥ n ( 為什麼呢…

Problem - B - Codeforces 需要想那麼一下下。就會發現其實答案在輸入的邊上，且僅限於自身不是 bakery但連接的是 bakery的節點。取最小就行了。 void solve(){ int N, M, K; cin >> N >> M >> K; if( K == 0 ){ cout << -1 << endl; return; } vector< trip…

Problem - A - Codeforces 這題真的很簡單，我一分鐘就傳了。但因為太有紀念意義了。 我竟然漏看 grey也算，pretest全過，然後被 hack了，太智障了。 void solve(){ int N, M; cin >> N >> M; for( int i = 0; i < N; ++i ) for( int j = 0; j < M; ++j ){ s…