Entries from 2016-04-05 to 1 day
Problem - D - Codeforces First we will have to take away apparently wrong cases, where dis[ i ][ i ] != 0 or dis[ i ][ j ] == 0 for i != j, or if dis[ i ][ j ] != dis[ j ][ i ]. We will find that we are willing to make a tree, so the short…
Problem - 25C - Codeforces 先做完一次MSSP之後,對於每個動態操作可以直接詢問每個兩端,是否用了這條邊之後會更好。 注意題目是說額外新增路,所以是不一定要取的。 #include <bits/stdc++.h> using namespace std; const int MAXN = 300 + 3; const int MAXK = 300 + 3;</bits/stdc++.h>…
Problem - B - Codeforces 如果順著做,逐一破壞。。嗯,看到逐一破壞就可以開始想反著觀察就是逐一增加了。 因為問題是Multiple Source Shortest Path,所以可以馬上想到Floyd Warshall演算法了。 想起以前學長和我提過,為什麼三層迴圈的中繼點要在最外圈…
Problem - A - Codeforces 二回べつべつに区間操作するのは自明。まずどの操作が何回使われるかを統計して終えてから操作毎に区間addをすればいい。 Range add と Single query しかないので BITの方がかなり楽。 追記:いや、普通にarrayの上でいもすすれば…
Problem - B - Codeforces Dijkstraみたいな感じでやればいいね。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXK = 1e5 + 5; int n, k; char w[ 2 ][ MAXN ]; struct State{ int t, x, lv; State( int _t = -1, int _x = -1, in</bits/stdc++.h>…
Problem - A - Codeforces f( x ) = k * x + b f^n( 1 ) ≤ f^a( t ) となるような最小な aを求める。 始めは matrix fast power で二分探査しようと頑張ってみたがオーバーフローが出るみたいで失敗した。 ちゃんと考えると、単調増加関数なので両方に f^( -…
wakatake-topics.com 久しぶりにいい映画に感動されたQQ いつか忘れたらまたもう一度見たいな。 明日また沢山CFR virtualして頑張ろOrz