GCA

有點無聊的公式解 正 n 邊形的面積為 邊長為 a 的正多邊形的內切圓半徑為： 邊長為 a 的正 n 邊形外接圓的半徑為： 參考自維基百科 //====================================================================|| // Name : Ancient Village Sports.cpp || // Date : May 31, 2013 8:09:14 PM || // Author : GCA || // 6AE7EE02212D47DAD26C32C0FE829006 || //====================================================================|| #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> using namespace std; #ifdef ONLINE_JUDGE #define ll "%lld" #else #define ll "%I64d" #endif typedef unsigned int uint; typedef

屌思路題，像是BFS暴搜 不過不太像 因為條件是要滿足所有的老師都有人 所以用狀壓DP紀錄，並且每次更新都要排序過，由目前最多老師的狀態去增加狀態 因為如果由最小的老師去更新，有可能會更新到大的，更新到大的之後，大的在更新一次 等於一個老師用了兩次 //====================================================================|| // Name : Headmaster's Headache.cpp || // Date : May 30, 2013 11:44:48 AM || // Author : GCA || // 6AE7EE02212D47DAD26C32C0FE829006 || //====================================================================|| #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> using namespace std; #ifdef ONLINE_JUDGE #define ll "%lld" #else #define ll "%I6

考驗printf功力，史上水題 //====================================================================|| // Name : Draw Grid.cpp || // Date : 2013/5/28 下午7:46:16 || // Author : GCA || // 6AE7EE02212D47DAD26C32C0FE829006 || //====================================================================|| #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> using namespace std; #ifdef ONLINE_JUDGE #define ll "%lld" #else #define ll "%I64d" #endif typedef unsigned int uint; typedef long long int Int; #define Set(a,s) memset(a,s, sizeof (a)) #define Write(w

首次學習字典所有排序用法 //====================================================================|| // Name : Lexicographic Order.cpp || // Date : 2013/5/27 下午8:57:00 || // Author : GCA || // 6AE7EE02212D47DAD26C32C0FE829006 || //====================================================================|| #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> using namespace std; #ifdef ONLINE_JUDGE #define ll "%lld" #else #define ll "%I64d" #endif typedef unsigned int uint; typedef long long int Int; #define Set(a,s) memset(a,s, sizeof (a)) #define Write(w) freopen(w,

實作題 //====================================================================|| // Name : Rectangle Puzzle II.cpp || // Date : 2013/5/25 下午5:16:50 || // Author : GCA || // 6AE7EE02212D47DAD26C32C0FE829006 || //====================================================================|| #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> using namespace std; #ifdef ONLINE_JUDGE #define ll "%lld" #else #define ll "%I64d" #endif typedef unsigned int uint ; typedef long long int Int; #define Set(a,s) memset(a,s, sizeof (a)) #define Write(w) freopen(w, &q

此證明參考至 http://www.algorithmist.com/index.php/UVa_10120 M=k 2  1+3+5+7+…+(2k-1)=k 2 Frank 可以輕易地走到k 2 的位置，只要一直往前就可以了 而當Frank在R[x]的位置，下一次跳躍的距離就是2k+1 Proof 1.1 “如果x-(2k+1)>=1(代表往回跳不會超過邊界)，Frank可以到達R[x+2](x+2<=M)” 如果Frank往回跳(2k+1)的值，再跳回來(2k+3)，公式會是(x-(2k+1)+(2k+3))=(x+2) 而且x-(2k+1)>=1 && (x+2)<=N 總之就是邊界別超過   Proof 1.2 “如果Frank在R[x]，然後下一次跳躍的距離是2k+1，只要x-((2k+1)+(y-1)*2)>=1 Frank就可以從R[x]到R[x+2y](0<=y and x+2y<=N)” 假設x-((2k+1)+(y-1)*2)>=1(0<=y && x+2y<=N) 當y=0的時候，x=x+2y  ，理所當然 我們就在x上 當y=1的時候，x - (2k+1) = x-((2k+1)+(y-1)*2) >= 1由(proof 1.1)可以得知可從x到x+2 當y>1的時候，使用歸納法，假設我們可以旅行x到x+2(y-1)=x+2y-2 而假設的限制是x-((2k+1)+(y-1)*2)>=1，如果目前在x而下一步是2k+1，就好比目前在x+2(y-1) 而下一步是2*(k+(y-1))+1，因為我們需要兩次的跳躍才會讓x到x+2。為了讓歸納法有效， 我們需要有一些限制，目前的點-下一步要走的距離>=1，在這種情況下，就好比是 (x+2(y-1)) - (2*(k+2(y-1))+1) >=1 做一些處理轉換之後 就會變成這樣 x - (2 k + 1 + 2( y - 1)) > = 1，跟我們一開始的假設一樣，所以這個歸納法成立   證明證完了 再來就是實作這題的部分，我們需要一些方法來走道R[M] 這些石頭是這樣擺設的 R[1], R[2], ... ,R[M]

我用二分法~ //====================================================================|| // Name : Eugeny and Array.cpp || // Date : 2013/5/21 下午1:09:31 || // Author : GCA || // 6AE7EE02212D47DAD26C32C0FE829006 || //====================================================================|| #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> using namespace std; #ifdef ONLINE_JUDGE #define ll "%lld" #else #define ll "%I64d" #endif typedef unsigned int uint ; typedef long long int Int; #define Set(a,s) memset(a,s, sizeof (a)) #define Write(w) freopen(w, "w" ,std

SPFA //====================================================================|| // Name : Gopher and Hawks.cpp || // Date : 2013/5/21 下午11:58:55 || // Author : GCA || // 6AE7EE02212D47DAD26C32C0FE829006 || //====================================================================|| #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> using namespace std; #ifdef ONLINE_JUDGE #define ll "%lld" #else #define ll "%I64d" #endif typedef unsigned int uint; typedef long long int Int; #define Set(a,s) memset(a,s, sizeof (a)) #define Write(w) f

模擬神題 神模擬題 模神擬題 //====================================================================|| // Name : sdfsdf.cpp || // Date : 2013/5/20 下午11:13:32 || // Author : GCA || // 6AE7EE02212D47DAD26C32C0FE829006 || //====================================================================|| #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> using namespace std; #ifdef ONLINE_JUDGE #define ll "%lld" #else #define ll "%I64d" #endif typedef unsigned int uint; typedef long long int Int; #define Set(a,s) memset(a,s, sizeof (a)) #define Write(w)

暴力剪枝   //====================================================================|| // Name : Sticks.cpp || // Date : 2013/5/19 下午6:30:00 || // Author : GCA || // 6AE7EE02212D47DAD26C32C0FE829006 || //====================================================================|| #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> using namespace std; #ifdef ONLINE_JUDGE #define ll "%lld" #else #define ll "%I64d" #endif typedef unsigned int uint; typedef long long int Int; #define Set(a,s) memset(a,s, sizeof (a)) #define Write(w) freopen(w

需要構兩次圖，一個是原本的，一個是只有旅館跟起點終點的(最小化) 一樣使用SPFA，耍白癡TLE好幾次 //============================================================================ // Name : Hotel booking.cpp // Date : 2013/5/12 下午7:02:55 // Author : GCA //============================================================================ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> using namespace std; #ifdef ONLINE_JUDGE #define ll "%lld" #else #define ll "%I64d" #endif typedef unsigned int uint; typedef long long int Int; #define Set(a,s) memset(a,s, sizeof (a)) #define Write(w) freopen(w, "w" ,stdout) #define Read(r) freopen(r, "r" ,stdin) #define Pln() printf( "\n" ) #define I_de(x,n) for ( int i=0;i<n;i++)p

兩個優先佇列，再用兩個陣列各存已經被pop的值，在互相檢查pop掉 lld WA了一次 //============================================================================ // Name : Hoax or what.cpp // Date : 2013/5/12 下午1:56:32 // Author : GCA //============================================================================ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> using namespace std; #ifdef ONLINE_JUDGE #define ll "%lld" #else #define ll "%I64d" #endif typedef unsigned int uint; typedef long long int Int; #define Set(a,s) memset(a,s, sizeof (a)) #define Write(w) freopen(w, "w" ,stdout) #define Read(r) freopen(r, "r" ,stdin) #define Pln() printf( "\n" ) #define I_de(x,n) for ( int i=0;i<n;i++)printf( &q