GCA

From Evernote: uva 216 先使用最小生成樹試試看，發現這不能用分岔，所以只能用暴力剪枝 [sourcecode language="cpp"] //============================================================================ // Name : Getting in Line.cpp // Date : 2013 2013/1/31 下午6:50: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; typedef long long ll; typedef unsigned int uint; #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"%d\n",x) #define For(i,x)for(in

From Evernote: uva 10608 disjoint 複習 [sourcecode language="cpp"] //============================================================================ // Name : Friends.cpp // Date : 2013 2013/1/30 上午12:47:05 // 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; typedef long long ll; typedef unsigned int uint; #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"%d\n",x) #define For(i,x)for(int i=0;i<x;i++) #defin

From Evernote: uva 11513 bfs，做法可以先用九格基本的狀態衍生出所有的狀態，在用map存起來，之後在把所有的狀態存進去 Input: 2 3 1 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 7 3 9 2 5 1 4 8 6 1 2 3 4 5 6 7 9 8 0 [sourcecode language="cpp"] //============================================================================ // Name : 9 Puzzle.cpp // Date : 2013 2013/1/29 下午2:40: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; typedef long long ll; typedef unsigned int uint; #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

From Evernote: uva 10002 題目要找質心，重力均勻的話也就是找重心。 多邊形找重心的方式:先取有序的凸邊形的點，利用任意一個點(我用(0.0,0.0))與有序多邊形的點組成多個三角形 每個三角形的點x乘上面積，y乘上面積，各別加在紀錄ansx,ansy上 也把每個三角形的面積ansa紀錄並累加起來 之後ansx/(ansa*3)，ansy/(ansa*3) 即是答案 差積順時針為負，逆時針為正 [sourcecode language="cpp"] //============================================================================ // Name : Center of Masses.cpp // Date : 2013 2013/1/29 上午10:50:27 // 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; typedef long long ll; typedef unsigned int uint; #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() prin

From Evernote: uva 10078 判斷是否為凸多邊形 (叉乘) [sourcecode language="cpp"] //============================================================================ // Name : The Art Gallery.cpp // Date : 2013 2013/1/28 下午10:26: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; typedef long long ll; typedef unsigned int uint; #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"%d\n",x) #define For(i,x)for(int i=0;i<x;

From Evernote: uva 11624 幫助Joe別被火燒到然後跑出去，標準BFS作法 浪費了一整天 RTE跟TLE交錯顯示.... 最後原來是界線沒考慮好 input: 4 10 10 ########## #.....JFF# #........# #........# #........# #........# #........# #........# #........# ..######## 3 1 # J F 1 2 .J 5 5 ##### #..F# #.J.# ....F ##### [sourcecode language="cpp"] //============================================================================ // Name : Fire!.cpp // Date : 2013 2013/1/28 下午6:23:57 // 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; typedef long long ll; typedef unsigned int uint; #define Set(a,s) memset(a,s,sizeof(a)) #define Write(w) freopen(w,"w",stdout) #define Read(r) freopen(r,&

From Evernote: uva 10066 看起來像是LCS問題 [sourcecode language="cpp"] //============================================================================ // Name : The Twin Towers2.cpp // Date : 2013 2013/1/28 上午10:41:53 // 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; typedef long long ll; typedef unsigned int uint; #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"%d\n",x) #define For(i,x)for(int i=0;i<x;i++

From Evernote: 594 貌似是印地安的INT轉換方式 四個位元組全部倒反 一開始卡住不過還是AC [sourcecode language="cpp"] //============================================================================ // Name : One Little, Two Little, Three Little Endians2.cpp // Date : 2013 2013/1/28 上午12:08:13 // Author : GCA //============================================================================ #include &lt;iostream&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;climits&gt; #include &lt;vector&gt; #include &lt;set&gt; #include &lt;map&gt; #include &lt;queue&gt; #include &lt;cctype&gt; #include &lt;utility&gt; using namespace std; typedef long long ll; typedef unsigned int uint; #define Set(a,s) memset(a,s,sizeof(a)) #define Write(w) freopen(w,&quot;w&quot;,stdout) #define Read(r) freopen(r,&quot;r&quot;,stdin) #define Pln() printf(&quot;

From Evernote: 11231 有人想要塞棋盤在畫裡面 看能塞幾個 無想法，ad hoc GOOGLE完發現 長跟列各-7相乘在除2 如果是偶數，看右下角是不是白色的，是的話+1不是不用加 [sourcecode language="cpp"] //============================================================================ // Name : Black and white painting.cpp // Date : 2013 2013/1/27 下午9:41:09 // 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; typedef long long ll; typedef unsigned int uint; #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 D

From Evernote: 11506 員工報仇剪斷BOSS的線路 M=machines W=wires boss id=1 central server id=M c=cost of destroying the machine d=cost of destroying the wire all wire are bidrectional!! input: 4 4 3 5 2 2 1 2 3 1 3 3 2 4 1 3 4 3 4 4 3 2 2 2 1 2 3 1 3 3 2 4 1 3 4 3 0 0 遇到一個問題，點有權重，而且又是流的問題 GOOGLE找到一個方法，把點分成兩個點:入點跟出點 out->in 而自己的in到自己的out就是點的權值 本來TLE，發現好像是因為M設太大讓STL跑太久的緣故 結論AC [sourcecode language="cpp"] //============================================================================ // Name : Angry Programmer.cpp // Date : 2013 2013/1/27 下午5:38:26 // 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; typedef long long ll; typedef unsigned int

From Evernote: 10364 未寫1:使用DFS試試看 結論:TLE... 未寫2:排序在DFS，突然想到狀態壓縮，先不使用做做看 Input: 1 8 1 1 2 2 3 4 5 6 結論:Bitmask不會用，使用sort後的dfs AC -- [sourcecode language="cpp" htmlscript="false"] //============================================================================ // Name : Square.cpp // Date : 2013 2013/1/27 上午11:33: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; typedef long long ll; typedef unsigned int uint; #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

From Evernote: 482 482 水題水過 [sourcecode language="cpp" htmlscript="false"] //============================================================================ // Name : Permutation Arrays.cpp // Date : 2013 2013/1/27 上午1:23:38 // 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 ; typedef long long ll; typedef unsigned int uint; #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"%d\n" ,x)

From Evernote: 線段樹題 Clipped from: file:/// uva 12501 need pratice T=test case N=cities Q=operations change i j u增加卡路里消耗，也有可能減少卡路里，更會減到變負的(越跑越多卡路里) query查詢 1 5 5 query 1 3 change 2 3 4 query 1 3 query 2 3 query 3 3 極難.... 每個node維護兩個數值a,sum a[1~2]=a[1~1]+a[2~2] a[1~3]=a[1~2]+a[3~3] sum[1~1]=a[1~1] sum[2~2]=a[2~2] sum[3~3]=a[3~3] sum[4~4]=a[4~4] sum[5~5]=a[5~5] sum[1~2]=sum[1~1]+(1)*a[2~2]+sum[2~2] sum[1~3]=sum[1~2]+(2)*a[3~3]+sum[3~3] sum[4~5]=sum[4~4]+(1)*a[5~5]+sum[5~5] sum[1~5]=sum[1~3]+(3)*a[5~5]+sum[4~5] m=(l+r)/2  id=(r-l+1)-(r-l+1)/2 sum[l~r]=sum[l~m]+id*a[m+1~r]+sum[m+1~r] m-m/2代表左子樹的個數 m/2代表右子樹的個數 這題很雷，根本就是死亡線段樹

From Evernote: BFS題 UVA 532 未寫:水題認知，2D改3D，BFS暴搜 寫完:根本鬼打牆，TLE10幾次，感覺上是STL的queue在雷我