網頁

2012年10月22日 星期一

使用XeLax與beamer來做pdf版的簡報

~/Desktop/uva10157.tex.html
%\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月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/)

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日 星期六

開張大吉

原部落格在monkey413.wordpress.com,但是我覺的wordpress.com的東西完全不能修改,讓我覺得有點無聊,所以我就將部落格搬到monkey413.blogspot.tw。:)

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)

~/Desktop/kk.cpp.html
/**********************************************************************************/
/*  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;
}

暑假努力學習中!!!

暑假好長,想自己寫網頁,可是又找不到什麼好的免費網頁空間,只能用自己的電腦架一個apache伺服器來寫網頁,寫的好累~~,想想還是來做部落格,一個屬於自己的日記。