Subscribed unsubscribe Subscribe Subscribe

0w1

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

Yuki 416 旅行会社 ( Union Find, Smaller to Larger, Time Reverse )

No.416 旅行会社 - yukicoder題意: 給一個圖,和破壞邊的順序 ( 不一定會將所有橋破壞 )。對於所有大於 0 的節點,求哪一次破壞後無法從 0 達到。若一開始就不能到達,輸出 0,若破壞完依然能到達,輸出 -1。資料規模: 節點數 2≤N≤1e5 初始橋的數量 1≤M≤2e…

Yuki 351 市松スライドパズル ( Time Reverse )

No.351 市松スライドパズル - yukicoder 最後の盤面から最初の位置を辿ればいい。その最初の位置を知れば、対応する色も当然に一意に定まる。 #include <bits/stdc++.h> using namespace std; const string msg[] = { "white", "black" }; signed main(){ int H, W; cin >> </bits/stdc++.h>…

CFR 637 D. Running with Obstacles ( DP, Reverse Thinking )

Problem - D - Codeforces題意: 初始時在 x = 0,要到 x = M,一路上會有若干個地雷。有兩種移動方式,跑步可以一次跑無窮遠,但不能越過地雷,跳躍可以越過地雷,但必須先跑連續至少 S 格,才能進行一次至多 D 格移動的跳躍。所有移動都只能向右。求是否存…

CFR 295 1B. Greg and Graph ( DP = Floyd Warshall + Reverse Thinking )

Problem - B - Codeforces 如果順著做,逐一破壞。。嗯,看到逐一破壞就可以開始想反著觀察就是逐一增加了。 因為問題是Multiple Source Shortest Path,所以可以馬上想到Floyd Warshall演算法了。 想起以前學長和我提過,為什麼三層迴圈的中繼點要在最外圈…

TimOJ 1671 Anansi's Cobweb ( Union Find + Time Reverse )

1671. Anansi's Cobweb @ Timus Online Judge If we simulate it from the back instead, thinking the original edge destroying operation as adding, it will be possible to solve using elementary union find. #include <bits/stdc++.h> using namespace std; const i</bits/stdc++.h>…