%\documentclass{beamer} %\documentclass[slidestop,compress,mathserif]{beamer} \documentclass[slidestop,compress,mathserif,xcolor=dvipsnames]{beamer} \usepackage{pgfpages} \usetheme{Berlin} \usecolortheme{seahorse} %\usecolortheme[named=black]{structure} \setbeamercolor{section in head/foot}{fg=white,bg=gray!20!black} \setbeamertemplate{items}[ball] %\setbeamertemplate{blocks}[rounded][shadow=true] \setbeamertemplate{navigation symbols}{} %\setbeamertemplate{headline}{} %<= to suppress the headline otherwise % section and subsection will be displayed in the navigation bar \setbeamertemplate{footline}{} %\beamersetuncovermixins{\opaqueness<1>{25}}{\opaqueness<2->{15}} \usepackage{graphicx}% http://ctan.org/pkg/graphicx \usepackage{booktabs}% http://ctan.org/pkg/booktabs \let\Tiny=\tiny \usepackage{fontspec} \setmainfont{WenQuanYi Micro Hei} \setsansfont{WenQuanYi Micro Hei Mono} \setmonofont{WenQuanYi Micro Hei Mono} \XeTeXlinebreaklocale "zh" \XeTeXlinebreakskip = 0pt plus 1pt \begin{document} \setbeamerfont{subsection in sidebar}{size=\tiny} \setbeamerfont{title in sidebar}{size=\tiny} \title{\fontsize{28}{35}\selectfont UVA 10157\\ \fontsize{14pt}{20pt}\selectfont Expression} %\author{Author Name} \institute{} \frame{\titlepage} \section{題意} \subsection{} \begin{frame} \frametitle{題意1} \uncover<1-> {給你 n 和 d ，你的任務是找出長度為 n，且深度為 d 正確之括號表示式共有多少個。\\} \uncover<2-> {\vspace{\baselineskip}} \uncover<2-> {令 X 表示正確的括號表示式。X 的內容為僅含 '(' 和 ')' 的字串。定義如下：\\} \begin{itemize} \uncover<3-> {\item 空字串屬於 X。\\} \uncover<4-> {\item 假如 A 屬於 X ，那麼 (A) 也屬於 X。\\} \uncover<5-> {\item 假如 A 和 B 都屬於 X ，那麼 AB 也屬於 X。\\} \end{itemize} \end{frame} \subsection{} \begin{frame} \frametitle{題意2} \uncover<1-> {令 E 是一個正確的括號表示式（因此 E 屬於 X）。\\} \uncover<2-> {\vspace{\baselineskip}} \uncover<2-> {E 的長度為字串的長度。\\} \uncover<3-> {\vspace{\baselineskip}} \uncover<3-> {而 E 的深度 D(E) 被定義如下：\\} \uncover<4-> {\vspace{\baselineskip}} \uncover<4-> {$ D(E)=\left\{ \begin{aligned} & 0 \qquad 如果 E 是 \varnothing \\ & D(A)+1 \qquad 如果 E = (A), 並且 A\in{X} \\ & max(D(A),D(B)) \qquad 如果 E = AB, 並且 A,B\in{X} \end{aligned} \right.$} \end{frame} \section*{Input and Output} \begin{frame} \frametitle{Input and Output} Input \\ 6 2\\ 300 150\\ Output \\ 3 \\ 1 \\ \end{frame} \section{思考路線} \subsection{} \begin{frame} \frametitle{要用何種演算法？} \begin{itemize} \uncover<1->{\item{DP}} %\uncover<2->{\item{單邊一直加1？}} %\uncover<3->{\item{左右邊一直加1？}} \end{itemize} \end{frame} \section{解題方法} \subsection{} \begin{frame} \frametitle{遞迴公式} \uncover<1->{$ F(n,d)=\left\{ \begin{aligned} & 1 \ if\ n=0\ \\ & \mathop{\sum_{k=0}^{n-2}}_{k\;is\;even} F(k,d-1)\times{F(n-k-2,d)}\;otherwise \end{aligned} \right.$\\ \vspace{\baselineskip}} \uncover<2->{F(n,d)之值為長度n的情況，深度不超過d之正確括號總數\\ \vspace{\baselineskip}} \uncover<3->{因此，F(n,d)-F(n,d-1)便是長度n深度為d的正確括號總數 \\ \vspace{\baselineskip}} \end{frame} \begin{frame} \frametitle{遞迴公式想法部份} \uncover<1->{$ F(n,d)=\left\{ \begin{aligned} & 1 \ if\ n=0\ \\ & \mathop{\sum_{k=0}^{n-2}}_{k\;is\;even} F(k,d-1)\times{F(n-k-2,d)}\;otherwise \end{aligned} \right.$\\ \vspace{\baselineskip}} \uncover<1->{令E是一個長度為n深度為d之合法的表達式，且不為$\varnothing$,\\ 而A、B為合法表達式 \\ \vspace{\baselineskip}} \uncover<2->{E=(A)B \\ \vspace{\baselineskip}} \uncover<3->{根據上式可得知，\\A的深度等於d-1或B的深度等於d，且A的長度加B的長度為n-2 \\ \vspace{\baselineskip}} \end{frame} \begin{frame} \frametitle{遞迴公式實踐} \uncover<1->{根據上一張投影片的想法，\\便可以得知，任意一個不為$\varnothing$的E都可拆成(A)B且不重覆，\\ \vspace{\baselineskip}} \uncover<2->{$ F(n,d)=\left\{ \begin{aligned} & \mathop{\sum_{k=0}^{n-2}}_{k\;is\;even} F(k,d-1)\times{F(n-k-2,d)} \end{aligned} \right.$ \\ \vspace{\baselineskip}} \uncover<3->{最後加上空集合後，得到，\\ \vspace{\baselineskip}} \uncover<4->{$ F(n,d)=\left\{ \begin{aligned} & 1 \ if\ n=0\ \\ & \mathop{\sum_{k=0}^{n-2}}_{k\;is\;even} F(k,d-1)\times{F(n-k-2,d)}\;otherwise \end{aligned} \right.$\\ \vspace{\baselineskip}} \end{frame} \begin{frame} \frametitle{Result DP table} \begin{tabular}{c||c|c|c|c|c|c|c|c|c|c} {n$\setminus$d}&\textbf{0}&\textbf{1}&\textbf{2}&\textbf{3} &\textbf{4}&\textbf{5}&\textbf{6}&\textbf{7}&\textbf{8}&\textbf{9}\\ \hline \hline \textbf{0}&1&1&1&1&1&1&1&1&1&1 \\ \hline \textbf{2}&0&1&1&1&1&1&1&1&1&1 \\ \hline \textbf{4}&0&1&2&2&2&2&2&2&2&2 \\ \hline \textbf{6}&0&1&4&5&5&5&5&5&5&5 \\ \hline \textbf{8}&0&1&8&13&14&14&14&14&14&14 \\ \hline \textbf{10}&0&1&16&34&41&42&42&42&42&42\\ \end{tabular} \end{frame} \end{document}PDF：UVA 10157 Expression(Result)
2012年10月22日 星期一
使用XeLax與beamer來做pdf版的簡報
2012年10月1日 星期一
linux make command learning
My first Makefile
#example 1:
#usage: make main OR make
#main: nerve.o
# g++ nerve.o -o main
#nerve.o:
# g++ nerve.cpp -c
#clean:
# rm -rf nerve.o
#main: nerve.py
# python nerve.py
main: nerve.cpp
g++ nerve.cpp -o main
若使用vim的make指令時，要注意所在的資料夾位置，可以使用make -C來指定資料夾位置，或是在.vimrc裡面加入:cd 資料夾位置(如:cd ~/program/)
#example 1:
#usage: make main OR make
#main: nerve.o
# g++ nerve.o -o main
#nerve.o:
# g++ nerve.cpp -c
#clean:
# rm -rf nerve.o
#main: nerve.py
# python nerve.py
main: nerve.cpp
g++ nerve.cpp -o main
若使用vim的make指令時，要注意所在的資料夾位置，可以使用make -C來指定資料夾位置，或是在.vimrc裡面加入:cd 資料夾位置(如:cd ~/program/)
2012年8月3日 星期五
d546: 3. 剪多邊形（molding）
/**********************************************************************************/ /* Problem: d546 "3. 剪多邊形（molding）" from 北市 98 資訊學科能力競賽*/ /* Language: CPP (1642 Bytes) */ /* Result: AC(4ms, 442KB) judge by this@ZeroJudge */ /* Author: monkey413 at 2012-08-02 14:51:55 */ /**********************************************************************************/ /*利用外積得知凸多邊形還是凹多邊形與凹點+多邊形面積公式*/ #include<iostream> #include<cmath> using namespace std; int n,a,start,end; float area=0 ; int main() { while(cin>>n>>a) { int coor[n][2],vec[n][2],cross[n]; /*坐標、向量、外積*/ for(int i=0 ; i<n ; ++i) for(int j=0 ; j<2 ; ++j) cin >> coor[i][j] ; for(int i=0 ; i<n ; ++i) { if(i+1<n) vec[i][0]=coor[i+1][0]-coor[i][0],vec[i][1]=coor[i+1][1]-coor[i][1] ; else vec[i][0]=coor[0][0]-coor[i][0],vec[i][1]=coor[0][1]-coor[i][1] ; } for(int i=0 ; i<n ; ++i) { if(i+1<n) cross[i]=vec[i][0]*vec[i+1][1]-vec[i+1][0]*vec[i][1] ; else cross[i]=vec[i][0]*vec[0][1]-vec[0][0]*vec[i][1] ; } /*凹多邊形面積要補滿，才可以成為凹多邊形*/ for(int i=0 ; i<n ; ++i) { if(cross[i]<0) { start=i ; end=i+2 ; for(int j=i+1 ; j<n ; ++j) { if(cross[j]<0) end++ ; } for(int k=start ; k<=end ; ++k) { /*cout << start << " "<< end << endl ;*/ if(k+1<n) area += (coor[k][0]*coor[k+1][1]-coor[k][1]*coor[k+1][0])/2 ; else area += coor[k][0]*coor[k+1-n][1]-coor[k][1]*coor[k+1-n][0] ; } /*cout << area << endl;*/ } } cout << ceil(area/a) << endl ; area=0 ; } return 0; }
2012年7月23日 星期一
b210. C. 咒語
/**********************************************************************************/ /* Problem: b210 "C. 咒語" from 2008 NPSC 高中組決賽 */ /* Language: CPP (1187 Bytes) */ /* Result: AC(2.8s, 8.3MB) judge by this@ZeroJudge */ /* Author: monkey413 at 2012-07-23 15:10:08 */ /**********************************************************************************/ //參考自：https://sites.google.com/a/hpsh.co.cc/code/ti-mu/b210-c #include<iostream> #define N 10001 #define swap(a,b){t=a,a=b,b=t;} using namespace std; class edge // 每個點連結出去的邊 { public: int from ; int value ; }; class node { public: edge passage[100] ; }; node map[N] ; int top[N]={0} ; // 點的連結個數 unsigned long long int ans[N] ; int n,m,x,y,z,t,newp; int main() { while(cin>>n>>m) { if(!n&&!m) break ; for(int i=0 ; i<m ; ++i) { cin >> x >> y >> z ; if(x>y) swap(x,y) ; top[y]++ ; map[y].passage[top[y]].from=x ; map[y].passage[top[y]].value=z ; } for(int i=1 ; i<=n ; ++i) { ans[i]=ans[i-1] ; //當沒有點連結到i點時 for(int j=1 ; j<=top[i] ; ++j) { newp=ans[map[i].passage[j].from]+map[i].passage[j].value ; ans[i]=(ans[i]>newp?ans[i]:newp) ; } } cout << ans[n] << endl ; for(int i=0 ; i<=n ; ++i) top[i]=0 ; } return 0 ; }
a293. A 百年國慶
/**********************************************************************************/ /* Problem: a293 "A 百年國慶" from 2011 NPSC 國中組初賽 */ /* Language: CPP (1081 Bytes) */ /* Result: AC(108ms, 372KB) judge by this@ZeroJudge */ /* Author: monkey413 at 2012-07-23 15:54:02 */ /**********************************************************************************/ #include<iostream> #define N 5 using namespace std; int n,sum=0; int arr[N][N]; int tmp[N][N]; int main() { while(cin>>n) { for(int i=0 ; i<n ; ++i) { for(int j=0 ; j<N ; ++j) for(int k=0 ; k<N ; ++k) cin >> arr[j][k] ; if(i) { for(int a=0 ; a<N ; ++a) { for(int b=0 ; b<N ; ++b) { if(tmp[a][b]==1 && arr[a][b]==1) sum+=1 ; else if(tmp[a][b]==1 && arr[a][b]==8) sum+=7 ; else if(tmp[a][b]==8 && arr[a][b]==1) sum+=2 ; else if(tmp[a][b]==8 && arr[a][b]==8) sum+=5 ; } } cout << sum << endl ; } for(int j=0 ; j<N ; ++j) for(int k=0 ; k<N ; ++k) tmp[j][k]=arr[j][k] ; sum=0 ; } } return 0 ; }
a241. 第二題：1 / x 是有限小數
/**********************************************************************************/ /* Problem: a241 "第二題：1 / x 是有限小數" from 板橋高中2011能力競賽*/ /* Language: CPP (779 Bytes) */ /* Result: AC(4ms, 380KB) judge by this@ZeroJudge */ /* Author: monkey413 at 2012-07-23 11:20:59 */ /**********************************************************************************/ #include<iostream> #include<algorithm> using namespace std; int m,n,top=0,upper; int arr[1000] ; long long int t=1 ; int power(int base, int exp) { int tmp=1 ; while(exp) { if(exp&1) tmp*=base ; base*=base ; exp>>=1 ; } return tmp ; } int main() { for(int i=0 ; i<=13 ; ++i) { t=power(5,i); for(int j=0 ; j<=30; ++j) { if(t>1000000000) break ; else arr[top++]=t ; t*=2 ; } } sort(arr,arr+top) ; while(cin>>m) { for(int i=0 ; i<m ; ++i) { cin >> n ; upper=upper_bound(arr,arr+top,n)-arr; cout << upper-1 << endl ; } } return 0 ; }
2012年7月22日 星期日
2012年7月21日 星期六
a251: 假費波那契數
/**********************************************************************************/ /* Problem: a251 "假費波那契數" from 成功高中校內賽初賽 第一題 */ /* Language: CPP (365 Bytes) */ /* Result: AC(4ms, 374KB) judge by this@ZeroJudge */ /* Author: monkey413 at 2012-07-21 11:10:34 */ /**********************************************************************************/ #include<iostream> #include<algorithm> using namespace std; int T,N; int table[20]; int main() { while(cin>>T) { for(int i=0 ; i>N ; for(int j=0 ; j> table[j]; for(int j=4 ; j<N ; ++j) table[j]=table[j-4]+table[j-1] ; sort(table,table+N) ; cout << table[N/2] << endl ; } } return 0; } 簡易DP
d501. 第二題：數列最小值
/**********************************************************************************/ /* Problem: d501 "第二題：數列最小值" from 高雄市98資訊學科能力競賽*/ /* Language: CPP (414 Bytes) */ /* Result: AC(516ms, 4.3MB) judge by this@ZeroJudge */ /* Author: monkey413 at 2012-07-21 09:59:22 */ /**********************************************************************************/ #include<iostream> #include<algorithm> using namespace std; int n ; int main() { while(cin>>n) { int num[n] ; for(int i=0 ; i<n ; ++i) cin >> num[i] ; sort(num,num+n) ; if(n%2) cout << "A=" << num[n/2] ; else { cout << "A=" ; for(int i=num[n/2-1] ; i<=num[n/2] ; ++i) { cout << i ; if(i!=num[n/2]) cout << "、" ; } } cout << endl ; } return 0; }
2012年7月20日 星期五
a227. 三龍杯 -> 河內之塔
/**********************************************************************************/ /* Problem: a227 "三龍杯 -> 河內之塔" from 2011三龍杯 (成附建杯) */ /* Language: C (429 Bytes) */ /* Result: AC(9ms, 298KB) judge by this@ZeroJudge */ /* Author: monkey413 at 2012-07-20 21:16:26 */ /**********************************************************************************/ #include<iostream> void hanoi(int n, char A, char B, char C) { if(n==1) printf("Move ring %d from %c to %c\n",n,A,C) ; else { hanoi(n-1,A,C,B) ; printf("Move ring %d from %c to %c\n",n,A,C) ; hanoi(n-1,B,A,C) ; } } int n; int main() { while(scanf("%d",&n)==1) { hanoi(n,'A','B','C'); printf("\n") ; } return 0; } 這題讓我瞭解到了遞迴的強大了！！
2012年7月19日 星期四
d526: Binary Search Tree (BST)
/**********************************************************************************/ /* Problem: d526 "Binary Search Tree (BST)" from BST */ /* Language: CPP (950 Bytes) */ /* Result: AC(80ms, 1.6MB) judge by this@ZeroJudge */ /* Author: monkey413 at 2012-07-19 13:32:31 */ /**********************************************************************************/ #include<iostream> #include<cstdlib> using namespace std ; class Node { public: int value ; Node* left; Node* right; }; Node* root; void Add_Node_To_Tree(Node** curr, int data) { if(*curr==NULL) { Node* tmp=new node ; //tmp=(Node*)malloc(sizeof(Node)); tmp->value=data,tmp->left=NULL,tmp->right=NULL ; *curr=tmp ; } else if(data<(*curr)->value) Add_Node_To_Tree(&((*curr))->left,data) ; else if(data>(*curr)->value) Add_Node_To_Tree(&((*curr))->right,data); } void pre(Node* ptr) { if(ptr!=NULL) { cout << ptr->value << " " ; pre(ptr->left) ; pre(ptr->right) ; } } int n ; int main() { while(cin>>n) { int num[n] ; root=NULL ; for(int i=0 ; i<n ; ++i) cin >> num[i], Add_Node_To_Tree(&root,num[i]) ; pre(root) ; cout << endl ; } return 0; }
訂閱：
文章 (Atom)