Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

TIOJ 1952 小向的試煉 3-3:鑰匙 ( Segment Tree, Tags )

1952 - 小向的試煉 3-3:鑰匙(Key) | TIOJ INFOR Online Judge題意: 給一個長度為 N 的字串,接著 M 筆詢問。詢問 L, R, K 代表 [ L, R ] 的字母要按照字典序大到小( K = 0 ) 或小到大( K = 1 )排序。求所有操作後的字串長相。資料規模: 第一行有兩個正整…

IOI 2007 Sails ( Greedy )

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

TIOJ 1908 大根蘿蔔 ( DP, bitmask )

1908 - 大根蘿蔔 | TIOJ INFOR Online JudgeProblem Description: You are given a matrix of N * N, each cell with a positive value. You can take values away from each cell at most once, in any order, but after taking a value from a particular …

TIOJ 1045 A.細菌培養 ( Ad hoc )

1045 - A.細菌培養 | TIOJ INFOR Online Judge題意: 給矩形的座標,每次使矩形內的所有數字 * 2,初始時皆為 1,求所有操作後矩形內數字總和。資料規模: 座標 0 ≤ X, Y ≤ 10000 操作數 1 ≤ Q ≤ 200 時限 1000 ms 保證解 ≤ 8e18解法: 本來想用 imosu ( 前…

TIOJ 1418 交大都是雷 ( bits DP )

1418 - 交大都是雷 | TIOJ INFOR Online Judge 電人出的題目,本以為又是什麼無聊的優化,可被捏的主要兩個優化都算蠻有梗的(?)。 底而上的寫法第一個就是不要拿不會出現的狀態嘗試更新,因為以這題來說只有以三為倍數的pop_count的狀態才合理。接著就是…

TIOJ 1744 [APIO '09] ATM ( SCC + DP )

1744 - [APIO '09] ATM | TIOJ INFOR Online Judge 題意:給你 n ≤ 5e5 個節點,每個節點都有權重,有些節點是酒吧,接著給你 m ≤ 5e5 個有向邊。給你一個起點,求最後停在一個酒吧( 經過的酒吧可以不要理會 ) 的經過的節點權重總和最大值。同一個節點可以被…

TIOJ 1063 Area ( Deque Monotonicity )

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

TIOJ 1092 跳格子遊戲 ( DP + Game theory )

1092 - A.跳格子遊戲 | TIOJ INFOR Online Judge 看網上大家都是寫拓撲排序逆著遞推,我覺得沒必要。另外我換了一下題意,因為事實上第一個動作的是初期的後手,所以我調換一下,這樣比較容易思考。邊界是當目前這個節點沒有可移動的,就代表前一個人已經勝…

TOIJ 1014 打地鼠 ( bitset DP )

1014 - 打地鼠 | TIOJ INFOR Online Judge 挺水的。O( ( n ^ 2 ) * ( 2 ^ n ) ) #include <bits/stdc++.h> using namespace std; const int MAXN = 16 + 2; const int MAXA = 1e8 + 8; const int INF = 2e9; int n; int a[ MAXN ]; int dp[ MAXN ][ 1 << MAXN ]; // last hi</bits/stdc++.h>…

TIOJ 1291 N箱M球 ( DP )

1291 - G.N 箱M 球 | TIOJ INFOR Online Judge dp[ m ][ n ]: m顆球放入 n個箱子,每個箱子至少有一樣東西 這麼一來轉移就很明顯,因為只有球有序所以很好做,轉移要嘛就是丟進一個新的箱子,要嘛就選一個已經有球的箱子,這樣不會有重複計算。一開始我把邊…