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>…

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

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…

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…

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

Problem - D - Codeforces It is easy to realize that once the first two elements are determined, the rest in the Fibonacci sequence are determined as well. Another important property is that Fibonacci sequence expands exponentially, and giv…

Problem - C - Codeforces Reverse the text, and perform dynamic programming to mark if some index i is possible to be reached from some index j, and the word it should use to reach from j to i. Make use of Rabin-Karp hashing to accelerate w…

UVa Online Judge 移項一下就能得到方程式 h[ i ] = ( h[ i - 1 ] + 1 ) * 2 - h[ i - 2 ]，所以只要前兩項確定，後面所有都會跟著唯一確定。前面的項越小，後面的項一定就成關係的一齊變小，所以二分枚舉第二項可不可行就好了。 注意輸出前要再呼叫一次 ok(…

UVa Online Judge 先想像一個最佳排列已經出來了。那麼任意相鄰的工作交換後不會影響其他工作，所以我們考慮這個已經是最優的排列中的相鄰工作是怎麼排出來的。假設現在這兩個工作分別是 a和 b，那麼 先排 a再排 b的總花費是 ( a.duration * a.fine + ( a.du…

UVa Online Judge 和這題是一樣的算法： h0rnet.hatenablog.com 即使變二維，可以將水平座標和鉛直座標做拆解成為兩個相互獨立的置點問題。比較雷的是我忘記判斷優先佇列是空的時候，代表這個位置不能放任何東西，需要跳過，就吃了RE。 #include <bits/stdc++.h> using name</bits/stdc++.h>…

UVa Online Judge 馬上會想到二分搜最大速度，而判斷的部分就會變成經典的置點問題。每個點 ( 作業 )都有左界和右界，只能將它置於其中。一個經典的算法是先將每個點以其左界限制做排序，然後由左到右依次考慮每個位置該放置哪個點，這部分可以利用優先佇列…

UVa Online Judge 挺有趣的一道題。一開始很直覺的直接比較字典序，WA了一波才想到問題在於長度相異的時候比較時，像是 cmp( 2, 27 ) 和 cmp( 2, 21 ) 是不同的，前者要回傳 false使成為 272，而後者要回傳 true使成為 221才會對。所以這時候應該要直接比較 …

UVa Online Judge 題目大意是給 n ≤ 10000個五元組，求取 k個的情況下每個位置的最大值相加的值最大。 感覺就只能暴搜，但五元組數量太多，裸裸的 2^10000剪枝也沒有希望。想一下，浪費時間是因為其實真正會用到的五元組不多，更仔細想想，會用到的定義是將…

Haven't yet tested well, might have some bugs. #include <bits/stdc++.h> using namespace std; const double EPS = 1e-10; const double PI = acos( -1.0 ); int dcmp(double x){ if( fabs( x ) < EPS ) return 0; return x < 0 ? -1 : 1; } struct Vector{ double x, y</bits/stdc++.h>…

UVa Online Judge 很明顯長度越長且頻率越小放在前面一定比較好，但我只會直覺上想到應該會是以其中一個數乘上另一個數的倒數為基準做排序。證明是查了別人的文章 http://blog.csdn.net/synapse7/article/details/17160607 看到這位大神的 code我還另外學到…

UVa Online Judge 用畢氏定理把輸入轉換成單純的區間覆蓋問題就可以了。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e4 + 4; int n; double l, w; double x[MAXN], r[MAXN]; typedef pair<double, double> pdd; pdd p[MAXN]; void solve(){ int m = 0; w /= 2.0; for</double,></bits/stdc++.h>…

UVa Online Judge 很單純的區間覆蓋問題。注意覆蓋的是端點而非區間。 #include <bits/stdc++.h> using namespace std; const int MAXLR = 5e4 + 4; const int MAXM = 5000 + 3; const int MAXP = 1e6 + 5; int m; typedef pair<int, int> pii; int n; pii p[MAXP]; void solve(){ sor</int,></bits/stdc++.h>…

UVa Online Judge 給一個 n * m的巧克力，問最少要切幾刀才能全部變成 1 * 1的巧克力，一次只能切在一塊的整數線上。 直覺上把巧克力變成 n條 m個巧克力的條或 m條 n個巧克力的條不會比縱橫亂切差，簡化一下代數又發現這兩種都必須要切 n * m - 1次。。如果…

Problem - E - Codeforces For a range query [ ql, qr ], we are asked to find the number of distinct pairs that XOR to a given number K. Since it is a range XOR problem, we will consider precomputing prefix XOR pa for the original array a. N…

Problem - D - Codeforces We should notice that it is necessary to somehow maximize the largest number, so all the x should be multiplied on the same number, otherwise the most significant digit could be pushed even further. However we cann…

UVa Online Judge 不太懂告訴我們一個點是否在凸包上到底有何意義。。嘛反正也是無恥水過去。注意座標會過大要用ll。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; typedef long long ll; struct Vector{ int x, y; Vector(){} Vector(int _x,</bits/stdc++.h>…

UVa Online Judge 沒有變化的單純求凸包。比較特別的要求是起點要印兩次，且必須是 y值最小的，若有多個相同則 x值最小的。這部分很容易解決，將點排序的時候照他要求排就行了。 碎念：以為每次後面都要吐出 -1，沒想到是測資與測資之間啊。。。 #include <bits/stdc++.h> u</bits/stdc++.h>…

UVa Online Judge 題目要求圓內選擇 m個點時最大的 m多邊形面積。由於點是給逆時針排序的，所以省掉了做一次凸包的麻煩。以 dp[ i ][ j ][ k ]為 [ i, j ] 中選了 k個點( 包含 i 和 j )時的最大面積動態規劃下去就行了。 #include <bits/stdc++.h> using namespace std; con</bits/stdc++.h>…

Problem - E - Codeforces We are to find x that will give minimum for max{ ABS( SUM( a[ k ] - x Ɐ i ≤ k ≤ j ) ) Ɐ 1 ≤ i ≤ j ≤ n }. Let us first remove absolute and get max{ max{ SUM( a[ k ] - x Ɐ i ≤ k ≤ j ) Ɐ 1 ≤ i ≤ j ≤ n }, max{ - SUM( a…

dp( a, b ) = the number of combinations, having a characters of valid prefix bracket sequence, and the opening bracket - closing = b dp2( a, b ) = the number of combinations, having a characters of valid suffix bracket sequence, and the cl…

F: レシート - 東京工業大学プログラミングコンテスト2015 | AtCoder A(1≤A≤10^100)円の商品に対し、X円でそれを購入することができる。買い物の金額A、支払額X、お釣り(X−A)の3つの整数について10進数表記にしたとき、3つの数字が揃う桁の数を最大にしたい…

Zig-Zag Numbers | Aizu Online Judge 一桁の場合はなんだとあれ必ずZig-Zag数という性質上、「今有効一桁だけ」、「今全部０」、「それ以外の状態」と三つに分けてそれぞれ別に判断しなけらばならない。桁dpをする時はleading zeroが方法数にどんな影響を与…

No.315 世界のなんとか3.5 - yukicoder これは世界のなんとか３のハードバージョン、桁数と余りを取る値が大きすぎて普通にやると状態数がやばい。でもよく考えると、８、８０、８００の倍数かどうかが決められるのは最後の５桁しかない。よって、最後の５桁…

Problem - C - Codeforces The key is to realize that the largest area is the largest width * largest height. They can be maintained with STL set / multiset separately. For each of them, prepare a set to keep record of the existing lines. Wh…