PEG Judge - IOI '12 - Crayfish Scrivener題意： 要求支持三種詢問至多 1e6 筆： T L: 在當前字串尾添上字符 L U a: 取消前 a 個操作 P x: 輸出當前第 x 位的字符解法： Rope 水過，詳見代碼。 時間 / 空間複雜度： 有人說內部是持久化平衡樹，有人說是分塊…

1343 - [IOI 2007, Day 1] Sails | TIOJ INFOR Online Judge題意： 有 N 個桿子，第 i 個桿子的高度為 H[ i ]，待放的旗子數量為 K[ i ]。 對於一個高度，若有 x 個旗子，那麼該高度的貢獻為 x * ( x - 1 ) / 2。 求最小總貢獻。資料規模： 輸入的第一行有一…

PEG Judge - IOI '98 - Picture題意： 給很多矩形的左下角和右上角座標，問總周長為何。被包含的線段不算在周長裡。資料規模： The first line of the input contains the number of rectangles (0 ≤ number of rectangles 解法： 掃描線，考慮對 X, Y 方向…

http://ioinformatics.org/locations/ioi16/contest/day2/paint/paint-TWN.pdf 1959 - [IOI 2016] Paint | TIOJ INFOR Online Judge題意： 給一個序列含 '.', 'X', '_'，分別代表該位置的字符為未知、必為黑色、必為白色。再給 K 個數字 C[]，代表由左到右看…

http://ioinformatics.org/locations/ioi16/contest/day2/messy/messy-TWN.pdf 1960 - [IOI 2016] Messy | TIOJ INFOR Online Judge題意： 你可以將任意數量的無號 n 位數丟 ( add_element() )進一個 set 裡面，然後呼叫 compile_set()，這個 set 裡面的所有…

http://ioinformatics.org/locations/ioi16/contest/day1/molecules/molecules-TWN.pdf 1956 - [IOI 2016] Molecules | TIOJ INFOR Online Judge題意： 給 L, U, W, N, result，要你找一個在集合 S，使得該集合為下標的 W 的總和在 L 和 U 之間 ( 含 )，寫在…

シラバスに載ってて自分がまだよく知らないトピック： BCC Z-algorithm Minimax algorithm Sweeping line algorithm Bipartite Graphs O( VE ) Maximum Bipartite matching ∆ Maximum flow. Flow/cut duality theorem Euler Path / Cycle 2-D Tree Trie ∆ KM…

PEG Judge - IOI '15 - Sorting 首先我們要想到，如果 k回合內能完成，那麼 k + 1回合內一定也能完成，這是很顯然的，因為對方換了什麼，換回來就行了。所以我們可以進行二分搜，現在問題就簡化成要在O( n ) 判斷 k回合內可不可能達成。 接著要發現，設原始…

終於做出來了。。 首先要直覺地想到，如果有一個日期是值得賣的，那麼一定會將所有都在這一天賣出去，因為如果留到後面的價值更高，這一天就根本不會是值得賣的。 如果要比較兩個不同日期賣出的錢，舉例來說比較 day i 和 day j，且不失一般性 i x[ 1 ] * x[…

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

PEG Judge - IOI '15 - Boxes with Souvenirs 実はそんなに難しくない Greedy。まず、どういう操作があるか考えてみよう。 １、時計回りに動いて逆時計回りに戻る ２、１の真逆 ３、一周する １をする場合は半周を過ぎないのは簡単に見える（そうする必要が…

PEG Judge - IOI '13 - Dreaming 題目大意是給一個森林，希望用任意數量的長度為L的邊將他黏成一棵樹，使得最後這棵樹的直徑最小，求的是這樣的直徑。 很容易想到，最理想的方法一定是將所有樹折半，以他的樹心( 該點對於樹上其他點的最長距離最小 ) 連結，…

PEG Judge - IOI '03 Practice Task - Balancing Act The idea of a tree center, is a node in the tree that would minimize the maximum subtree size after it is removed. Carefully simulating it without recomputing will do alright. O( n ). #incl…

PEG Judge - IOI '94 - The Buses First we can describe a route by defining its first time of arrival and its interval. After preprocessing all the possible routes, we should perform a brute force search with some heuristic functions to prun…

PEG Judge - IOI '94 - The Primes 不停的 TLE，原來枚舉的順序影響這麼大呢。。 首先最好枚舉兩個對角線，因為他們影響的最大。 接著枚舉外面兩行，所以我們要事先紀錄中間那三個數字總和為多少且頭尾為多少的質數有哪些。 再來我們發現這兩個格子可以 O( 1…

PEG Judge - IOI '94 - The Clocks 一開始想用 PFS，後來想一想沒有權重可以直接BFS，寫完丟出去才發現 RE / TLE。。 // Will TLE O( ( ans.size() ) ! ) #include <bits/stdc++.h> using namespace std; struct State{ int clk[ 9 ]; State(){} void read(){ for(int i = 0</bits/stdc++.h>…

PEG Judge - IOI '94 - The Castle 強行枚舉每個牆壁破壞後的樣子，直接把牆壁減掉，然後檢查完再加回來就行了。雖然很明顯，但要記得意識到只有破壞牆壁的連通分量會有面積的更新，所以不需要每次都檢查全部。有一點小小卡到的是後來枚舉破壞牆壁的時候忘記…

PEG Judge - IOI '94 - The Triangle 感言：終於找到一個好 judge可以寫 ioi題了呢，雖然有點懷念錯過的 hoj。。 #include <bits/stdc++.h> using namespace std; const int MAXN = 100 + 2; int n; int tri[ MAXN ][ MAXN ]; int dp[ MAXN ][ MAXN ]; int ans; void upmax(</bits/stdc++.h>…

1236 -- Network of Schools Given a network, answer at least how many nodes we need to spread information to let the whole graph know, and the minimum directed edges required to add so the whole graph becomes an SCC. The first query is just…