GCA

    算滿水的題目，不過題意讀得很累 /* * GCA : "Computer is artificial subject absolutely,Math is God" */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> #include <ctime> using namespace std; #ifdef DEBUG #define VAR(a,b) decltype(b) a=(b) #define debug(...) printf( "DEBUG: " ),printf(__VA_ARGS__) #else #define VAR(a,b) decltype(b) a=(b) #define debug(...) #endif typedef unsigned int uint ; typedef long long int Int; typedef unsigned long long int UInt; #define Set(a,s) memset(a,s, sizeof (a)) #define Pln() printf( "\n" ) #define For(i,x) for ( int i=0;i<x;i++) #define CON(x,y) x##y #define M 50005 #define PB push_back #define oo (1<<29) #define FOR(a,b) for (VAR(a,(b).begin());a!=(b).end();++a)

  排列組合問題 參考官方題解   /* * GCA : "Computer is artificial subject absolutely,Math is God" */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> #include <ctime> using namespace std; #ifdef DEBUG #define VAR(a,b) __typeof(b) a=(b) #define debug(...) printf( "DEBUG: " ),printf(__VA_ARGS__) #else #define VAR(a,b) __typeof(b) a=(b) #define debug(...) #endif typedef unsigned int uint ; typedef long long int Int; typedef unsigned long long int UInt; #define Set(a,s) memset(a,s, sizeof (a)) #define Pln() printf( "\n" ) #define For(i,x) for ( int i=0;i<x;i++) #define CON(x,y) x##y #define M 1105 #define PB push_back #define oo INT_MAX #define FOR(a,b) for (VAR(a,(b).begin());a!=(b).end();++a) #define

  DP dp[i] i表示厚度，而dp[i]的值是這個厚度當中 寬度最大的為多少 之後再用總數去扣掉即可   貌似有greedy解法，分成厚度1跟2 具體內容要參考其他blog /* * GCA : Where is the Dp,there is the wall */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> #include <ctime> using namespace std; #ifdef DEBUG #define VAR(a,b) decltype(b) a=(b) #define debug(...) printf( "DEBUG: " ),printf(__VA_ARGS__) #else #define VAR(a,b) __typeof(b) a=(b) #define debug(...) #endif typedef long long int Int; #define Set(a,s) memset(a,s, sizeof (a)) #define Pln() printf( "\n" ) #define M 104 #define PB push_back #define oo (1<<29) #define FOR(a,b) for (VAR(a,(b).begin());a!=(b).end();++a) #define eps 1e-9 inline bool xdy( double x, double y){ return x>y+eps;} inline bool xddy

利用stl來做就可以了，在此發現algortihm的lower_bound不及set的   貌似set裡面已經有做處理了 /* * GCA : "Computer is artificial subject absolutely,Math is God" */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> #include <ctime> using namespace std; #ifdef DEBUG #define VAR(a,b) __typeof(b) a=(b) #define debug(...) printf( "DEBUG: " ),printf(__VA_ARGS__) #else #define VAR(a,b) __typeof(b) a=(b) #define debug(...) #endif typedef unsigned int uint ; typedef long long int Int; typedef unsigned long long int UInt; #define Set(a,s) memset(a,s, sizeof (a)) #define Pln() printf( "\n" ) #define For(i,x) for ( int i=0;i<x;i++) #define CON(x,y) x##y #define M 300005 #define PB push_back #define oo INT_MAX #define FOR(a,b) for (

有點麻煩的題目，算出overlap，然後再計算有沒有子字串在裡面，子字串可以直接不用考慮 那麼把剩餘的點拿來做Hamilton Path最小成本即可 /* * GCA : "Computer is artificial subject absolutely,Math is God" */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> #include <ctime> using namespace std; #ifdef DEBUG #define VAR(a,b) __typeof(b) a=(b) #define debug(...) printf( "DEBUG: " ),printf(__VA_ARGS__) #else #define VAR(a,b) __typeof(b) a=(b) #define debug(...) #endif typedef unsigned int uint ; typedef long long int Int; typedef unsigned long long int UInt; #define Set(a,s) memset(a,s, sizeof (a)) #define Pln() printf( "\n" ) #define For(i,x) for ( int i=0;i<x;i++) #define CON(x,y) x##y #define M 25 #define PB push_back #define oo INT_MAX #define FOR(a

  全部列舉出來 然後暴力的放進去hash 搞定 /* * GCA : "Computer is artificial subject absolutely,Math is God" */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> #include <ctime> using namespace std; #ifdef DEBUG #define VAR(a,b) __typeof(b) a=(b) #define debug(...) printf( "DEBUG: " ),printf(__VA_ARGS__) #else #define VAR(a,b) __typeof(b) a=(b) #define debug(...) #endif typedef unsigned int uint ; typedef long long int Int; typedef unsigned long long int UInt; #define Set(a,s) memset(a,s, sizeof (a)) #define Pln() printf( "\n" ) #define For(i,x) for ( int i=0;i<x;i++) #define CON(x,y) x##y #define M 25 #define PB push_back #define oo INT_MAX #define FOR(a,b) for (VAR(a,(b).begin());a!=(b).end();++a) #de

二分法答案即可   /* * GCA : "Computer is artificial subject absolutely,Math is God" */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> #include <ctime> using namespace std; #ifdef DEBUG #define VAR(a,b) __typeof(b) a=(b) #define debug(...) printf( "DEBUG: " ),printf(__VA_ARGS__) #else #define VAR(a,b) __typeof(b) a=(b) #define debug(...) #endif typedef unsigned int uint ; typedef long long int Int; typedef unsigned long long int UInt; #define Set(a,s) memset(a,s, sizeof (a)) #define Pln() printf( "\n" ) #define For(i,x) for ( int i=0;i<x;i++) #define CON(x,y) x##y #define M 100005 #define PB push_back #define oo INT_MAX #define FOR(a,b) for (VAR(a,(b).begin());a!=(b).end();++a) #define eps 1e

偏向於思考題   題目看似很麻煩，不過可以想想floyd的原理   就是枚舉中間點，然後開始倆倆比對取最短   而這個問題就可以看成一張空圖然後一個點一個點加上去   然後把那個點當作中間點去做floyd   所以floyd只需要做一次即可搞定 // ############# ## ##### ## ############ // #### #### ## ####### ### #### #### // ## ##### ## ## ## ### #### ### ###### ## // ## ###### ## #### ######## ### ###### ## // ## ###### ## ## #### ## ### ###### ## // ## ## ## ######### ## ### ### // ############# ## ## ## ## ## ############## // ####### #### // ### ## ########## ## ## #### ###### // ################# ## ######## ############### // ################ ############## ###### # // ## ################## ######### ## # // ## ############## #### ########## #### // ############# ## ## ## ### ######## // ####### ###### #### ##### ##### // ########## ### ## #### ######### ## // ###### ### ## ## ## ### // ###

利用兩個線段樹更新即可 雖然不是正解 速度有待加強，不過練練線段樹也不錯 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A

  這題官方題解說要用ST+GCD   可惜我不太會用ST解這題   看Standing發現有人用類似Greedy解掉這題   直接搜尋每個點的左右方，看最遠能到多少   然後再枚舉下一個點，枚舉點的時候可以加快速度   上一個點i的右方到達距離代表i~r之間都可以被i整除   所以也不用再枚舉i~r之間了因為她的因數能枚舉的一定跑得比較遠   假設 4 12 8 2 如果上一點是枚舉4開始，那麼下一點就可以從2開始 因為可以保證上述所說的，12跟8往右往左跑都不會比4跑得遠 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::

  可惜了 方向想對了  可惜沒做出來 參考至  Code // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A

滿水的，把每一行的不同字元算出來 然後全部邊乘邊mod就是答案了 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A

  一開始誤解題意，完全做錯.. 只是個實作題 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A A::::