0w1

Entries from 2016-02-29 to 1 day

UVA 1025 A Spy in the Metro ( DP )

UVa Online Judge 令 dp( i, j ) 為時間點 i時在車站 j時的最短等待時間,邊界 dp( T, n ) = 0。另外預處理 hasTrain[ k ][ i ][ j ] 車站 j在時間點 i是否有往左 / 右的火車。 #include <bits/stdc++.h> using namespace std; const int MAXT = 200 + 2; const int MAXN = </bits/stdc++.h>…

TPC追いコン B - ライツアウト ( Binary Enumeration )

B: ライツアウト - TPC追いコン | AtCoder 定数倍で TLEしまくって諦めた。どうして時間がこんなにきついんだろう。。 1753 -- Flip Game 同じような問題だけど、今度のは bitによる状態の変化を加速するための前処理でやらないと通らない。以下のはギリギリ…

TPC追いコン A - 不完全迷路 ( BFS )

BFS

A: 不完全迷路 - TPC追いコン | AtCoder Short summary for statement: Given a graph where '.' indicates path and '#' indicates wall which shall not be penetrated, find the maximum distance from 'S' to 'G', where any but only one '#' can be ch…

CFR 635 D. Factory Repairs ( BIT )

Problem - D - Codeforces Notice that if the maintenance is made on day p, the maximum sum it could take is prefix sum of min( b, val[ i ] ) + suffix sum of min( a, val[ j ] ) Ɐ i and since the queries are forced to be solved online, we wil…

ATC MUJIN C. Orange Graph ( Bipartite + Union Find )

C: オレンジグラフ / Orange Graph - MUJIN プログラミングチャレンジ Programming Challenge | AtCoder It is already a well known fact that not to include any odd cycle is equivalent to having the graph bipartite. Since N is small ( ≤ 16 ), we …

UVA 10825 Anagram and Multiplication ( 暴搜 next_permutation )

UVa Online Judge 解題關鍵在於只要個位數確定,做完乘法後的個位數也會隨之確定,並且這個數會是做完乘法後的個位數的排列。因此只要枚舉個位數後判斷是否合法即可。比較挫的是,我很少用 std::next_permutation(),沒有意識它只會重新排列成比呼叫時字典序…