GCA

費式數列特性 //============================================================================ // Name : Fi-binary Number.cpp // Date : 2013/4/30 上午10:08:18 // 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( "%d " ,x[i]);Pln() #define De(x)printf(

換零錢問題 (加強版) //============================================================================ // Name : Making Change.cpp // Date : 2013/4/29 上午11:29:29 // 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( "%d " ,x[i]);Pln() #define De(x)print

SPFA AC //============================================================================ // Name : Number Maze.cpp // Date : 2013/4/29 下午4:56:03 // 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( "%d " ,x[i]);Pln() #define De(x)printf(#x &q

數學解，絕對不是博弈題 //============================================================================ // Name : Integer Game.cpp // Date : 2013/4/28 下午11:28:50 // 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( "%d " ,x[i]);Pln() #defi

染色+特殊的背包DP //============================================================================ // Name : The Joys of Farming.cpp // Date : 2013/4/27 下午12:20:56 // 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( "%d " ,x[i]);Pln()

瘋狂的WA 最後還是得參考網路，原來是要一直更新左邊跟右邊 //============================================================================ // Name : How Big Is It.cpp // Date : 2013/4/26 下午1:30:18 // 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( "%d "

特殊學習了連續和公式 (x+y)(y-x+1) = 2*n x+y = a y-x+1 = b y = (b+a-1)/2 , x = (b-a+1)/2 //============================================================================ // Name : Consecutive Integers.cpp // Date : 2013/4/24 下午9:52:34 // 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(

造表麻煩+特殊測資 //============================================================================ // Name : Recover Factorial.cpp // Date : 2013/4/23 上午7:19:33 // 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( "%d " ,x[i]);Pln() #d

DP永遠是我的弱點 1.  str[i]==str[j]   dp[i][j]+=dp[i+1[j-1]+1    刪除中間的部分 2.  刪除str[i]  dp[i][j]+=dp[i+1][j] 3.  刪除str[j]  dp[i][j]+=dp[i][j-1] 4.  刪除str[i]跟str[j] dp[i+1][j-1] 因為第2跟第3加過重複了 //============================================================================ // Name : Again Palindromes.cpp // Date : 2013/4/21 下午12:00:14 // 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

折騰了我三天之久 首先是BSGS策略 a^x ≡ b (mod m) gcd(a,m)=1 而要決定一個正整數n，思考了很久為何是sqrt(m) 假設使用普通的解法，暴力解x從0代到出現答案為止 出現了已經出現過的數字假設 2^x ≡3 (mod 5) x=0 (2^x)mod 5=1 x=1 (2^x)mod 5=2 x=2 (2^x)mod 5=4 x=3 (2^x)mod 5=3 答案 但是如果繼續找 x=4 (2^x)mod 5=1 發現重複 x=5 (2^x)mod 5=2 而這個式子也等於(1*2)mod 5也等於一開始的兩種情況 等於是進入迴圈了 所以最高的步數也只要m，在<=m的情況下 一定能找到重複，而進入迴圈 頂多就是0~m-1都有位置剛剛好補滿   所以BSGS也使用這個方法，不過也只是用模倒數的方式去算 BS需要時間是暴力的O(n) GS只需要O(m/n)因為是利用基數排序的想法 所以最快的方式也就是n=sqrt(m)，O(sqrt(m)) 傷腦筋的題目...... //============================================================================ // Name : Discrete Logging.cpp // Date : 2013/4/19 下午12:20: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> #inclu

LCS轉換成LIS 因為都是單一數字，否則LCS算法太慢 //============================================================================ // Name : Prince and Princess.cpp // Date : 2013/4/16 下午1:08:42 // 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( "%d &

最小全域數問題 //============================================================================ // Name : Re-connecting Computer Sites.cpp // Date : 2013/4/13 上午11:26:43 // 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( "%d " ,x[i])

很像以前聽過的有人住旅館，然後分手鐲去賣的問題，用2的次方算就可以了，因為可以組出所有的數 //============================================================================ // Name : Cut the Silver Bar.cpp // Date : 2013/4/12 下午9:40:49 // 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++)pri