%\documentclass{beamer} %\documentclass[slidestop,compress,mathserif]{beamer} \documentclass[slidestop,compress,mathserif,xcolor=dvipsnames]{beamer} \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}} \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 846\\ \fontsize{14pt}{20pt}\selectfont Steps} %\author{Author Name} \institute{} \frame{\titlepage} \section*{題意} \begin{frame} \frametitle{題意} \uncover<1-> {給你兩個點X、Y\\} \uncover<2-> {從X走到Y \\} \uncover<3-> {利用下列走法規則 \\} \begin{itemize} \uncover<4-> {\item 第一步和最後一步的距離一定是1\\} \uncover<5-> {\item 下一步走的距離與上一步走的距離相同\\} \uncover<6-> {\item 下一步走的距離與上一步走的距離多或少1單位\\} \end{itemize} \uncover<7-> {找出從X走到Y的最小步數即可\\} \end{frame} \section*{Input and Output} \begin{frame} \frametitle{Input and Output} Input \\ 3 //The number of test cases \\ 45 48 // 1 1 1 \\ 45 49 // 1 2 1 \\ 45 50 // 1 2 1 1 \\ Output \\ 3 \\ 3 \\ 4 \\ \end{frame} \section{思考路線} \subsection{} \begin{frame} \frametitle{怎樣才可以做到最少步數？} \begin{itemize} \uncover<1->{\item{一次能走越大的距離越好}} \uncover<2->{\item{單邊一直加1？}} \uncover<3->{\item{左右邊一直加1？}} \end{itemize} \end{frame} \begin{frame} \frametitle{$n^2$ trick} 1 + $\cdots$ + n-1 + n + n-1 + $\cdots$ + 1 = n$^{2}$ \end{frame} \section{解題方法} \subsection{} \begin{frame} \frametitle{演算法} \uncover<1->{d = X-Y // d 表示X到Y的距離 \\} \uncover<2->{n = $\lfloor\sqrt{d}\rfloor$ // n 表示取$\sqrt{d}$的整數部份\\ } \vspace{\baselineskip} \uncover<3->{if d == n$^2$ \\ \qquad return 2n-1 \\ \vspace{\baselineskip}} \uncover<4->{if 0 < d-n$^2$ <= n \\ \qquad return 2n \\ \vspace{\baselineskip}} \uncover<5->{if n < d-n$^2$ < 2n+1 \\ \qquad return 2n+1 \\ \vspace{\baselineskip}} \end{frame} \begin{frame} \frametitle{說明} \uncover<1->{第一種情況，當 d == n$^2$ \\ \qquad 最短的步數走法必然是1+$\cdots$+(n-1)+n+(n-1)+$\cdots$+1\\ \qquad $\therefore$ 最短步數為 2n-1 步\\ \vspace{\baselineskip}} \uncover<2->{第二種情況，當 d-n$^2$ <= n \\ \qquad 先利用第一種情況的解法，走n$^2$單位\\ \qquad 剩下還有一個小於等於n的值，插入可放置的位置即可\\ \qquad $\therefore$ 最短步數為 2n 步\\ \vspace{\baselineskip}} \uncover<3->{第三種情況，n < d-n$^2$ < 2n+1 \\ \qquad 先利用第一種情況的解法，走n$^2$單位，再插入n\\ \qquad 最後在插入小於等於n的值\\ \qquad $\therefore$ 最短步數為 2n+1 步\\} \end{frame} \subsection{} \begin{frame} \frametitle{小證明} \uncover<1->{proof: d-n$^2$ < 2n+1\\} \uncover<2->{\qquad \qquad $0 < n < \sqrt{d} < n+1$\\} \uncover<3->{\qquad \qquad $n^2 < d < n^2+2n+1$ \\ } \uncover<4->{\qquad \qquad $0 < d-n^2 < 2n+1$ \\} \end{frame} \end{document}PDF：UVA 846 Steps(Result)
2013年5月23日 星期四
Xelatex, beamer for persentation of UVA 846 Steps
2012年10月22日 星期一
使用XeLax與beamer來做pdf版的簡報
%\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)
訂閱：
文章 (Atom)