Browsed by
月份:2015年1月

[转]Emacs+ Latex 教程

[转]Emacs+ Latex 教程

Emacs + LaTeX 快速上手(原网址 http://cs2.swfc.edu.cn/~wx672/lecture_notes/linux/latex/latex_tutorial.html)

  • 本教程完全针对本校D215机房Ubuntu系统中的Emacs和LaTeX配置。关于如何配置,请看这里
  • 本教程中涉及的LaTeX源文件和图片都可以在这里找到。

目录

1 Emacs + AucTeX,60分钟快速入门

为什么非要推荐LaTeX?
这完全是出于个人喜好。从1996年开始接触计算机到现在,Windows、UNIX、MS-Word、LaTeX 我都用过了。我觉得我该把我认为优秀的东西推荐给你。即使你不感兴趣,但做为计科专业的学生你应该知道它的存在。
为什么非要推荐Emacs?
这不仅是出于个人喜好,也不仅是因为Emacs是最优秀的编辑器,我最基本的目的是,希望每一个计科专业的学生能熟练使用键盘。

1.1 放松心情

LaTeX很强大,但对于初学者来说,你不必关心它有多强大,因为最为常用的命令和环境不过就是那么几个。而且你也不必手工输入这些命令,只要你用Emacs+AucTeX,几个简单的快捷键就足以满足你的基本需求了。对于格式复杂的需求,通常你只要套用模版就可以解决问题了。所以,大家只要把Emacs用熟,一切迎刃而解。

1.2 用LaTeX写文章就是在编程

我们先回忆一下用Emacs写一个 hello.c 的过程:

  1. 打开Emacs;
  2. 开始编辑一个新文件,名字叫 hello.c:

    在Emacs窗口的最下面(也就是 mini buffer 里)写上新文件的名字 hello.c:
  3. 向文件里写东西:

    保存:

    编译:

    运行:

再来看一下用Emacs写一个 hello.tex 的过程:

  1. 打开Emacs;
  2. 开始编辑一个新文件,名字叫 hello.tex:

    在Emacs窗口的最下面(也就是 mini buffer 里)写上新文件的名字 hello.tex:
  3. 向文件里写东西:

    保存:

    编译:

    看结果:

怎么样? hello.c 和 hello.tex 的编辑过程没什么分别吧。只要把Emacs用熟练,不管写什么程序,都是这么个过程。你

  1. 不必学习VC去写C/C++,
  2. 不必学习eclipse去写Java,
  3. 不必学习MS-Word去写报告、幻灯片,
  4. 不必学习……

一句话,“Everything Emacs”,可以省下大量不必要的学习时间。人生苦短,何必让你的生活被 VC/eclipse/MS-Word 搞得头昏脑胀呢? 简单而强大,本就是计科专业学生和非专业学生应有的不同 。

如果你对Emacs操作还很陌生,那么现在就打开Emacs

重温一下那些基本操作吧。

1.2.1 什么是 C-x C-f ?

这么说,

  1. 把你的双手在标准键盘上放好,
  2. 左手小指稍向左移,按在 caps lock 键上。按住别动。(D215机房的 caps lock 键被我们改成 Control 键了)
  3. 小指按在 caps lock 上别放开,左手无名指稍向下移,在 x 键上按一下就放开,这就是 C-x 。
  4. 小指按在 caps lock 上别放开,左手食指在 f 键上按一下,这就是 C-f 。现在左手各指都可以放开了。

这就是 C-x C-f ,作用是要求打开一个文件, f 代表 file 。那么,告诉我

  • 什么是 C-x C-s ?
  • 什么是 C-x 2 ?什么是 C-x 3 ?什么是 C-x 0 ?什么是 C-x 1 ?什么是 C-x o ?
  • 什么是 C-x h ?什么是 C-w ?
  • 什么是 C-g ?
  • 什么是 C-j ?什么是 C-i ?
  • 什么是 C-/ ?
  • 什么是 C-k ?什么是 C-y ?
  • 什么是 C-d ?什么是 M-d ?(M 代表 Meta 键, 也就是 Alt 键)
  • 什么是 C-a ?什么是 C-e ?什么是 C-f ?什么是 C-b ?什么是 C-n ?什么是 C-p ?

【记住】使用Emacs的时候,一定要忘掉鼠标,两只手静静地放在 标准键盘 上!

1.3 生活可以更轻松

AucTeX是Emacs的一个功能模块,为LaTeX编程提供了巨大的便利。有了AucTeX,你的LaTeX生活可以象 Hello, world! 一样简单。现在就跟着我,手把手地领略一下简单的乐趣吧。

一切当然是从打开Emacs开始:

现在开始编辑一个新文件 simple.tex:

在Emacs窗口的最下方,也就是 mini buffer 里,会有提示,让你输入文件名。输入 simple.tex ,然后按 C-j 。

如果这时 mini buffer 里有如下提示:

直接按 C-j 就可以了。知道了吧, C-j 就是我们的“回车键”。如果你的手正放在【标准键盘】上,那么,左手小指向左一偏,按到的正是【Control】键(记得?CapsLock被我们改成Control了)。右手食指下不正是【j】键吗?怎么样,比回车键更方便吧。

现在,开始向 simple.tex 文件里写东西了,用AucTeX的方式:

e 代表 environment 。“环境”到底是什么呢?意会吧,用用就明白了。 在 mini buffer 里会有提示,

这是在问你是不是要写一篇文章啊?你当然该用 C-j 来告诉它“是”。

这时, mini buffer 又会提示,

这是在问你是不是要写一篇 article 类型的文件啊?还是 C-j 。

这时, mini buffer 又会提示,

这是在问你是否有什么特殊选项啊?用 C-j 来告诉它说“不需要”。

现在,你的 simple.tex 文件里应该有这么几行东西了:

在上一节里,你已经会写 Hello, world! 了。现在,我们要写点像模像样的东西,当然还是用简单的方式。为了更简单,我们直接套用Andrew Roberts写的 simple.tex 。我们把注意力放在用Emacs写文章的过程上。

确保你的光标在 begin{document} 和 end{document} 之间,也就是文章的第 4 行。然后按

这时 mini buffer 里会有如下提示:

这是系统在等待你输入一个 Macro ,说白了就是“命令”。输入:

这时你的文章多了一行 title{} (第4行)变成了这样:

光标停在 title{} 的花括号里。不用说你也知道,该输入文章的标题了。那么就给它一个标题:

发现了吗?凡是以反斜杠开头的都是命令, LaTeX{} 也是。它的唯一作用就是把 LaTeX 这五个字母输出成一副怪样子。

好了,在 title 下新起一行。再

你肯定知道 C-c C-m 是干什么用的了吧?就是要输入一个 Macro, 也就是 LaTeX 命令。 mini buffer 里又会有提示:

Emacs会把我们上次输入的Macro,也就是title,做为默认值提示出来。不用管它,输入:

不用我说了吧?在 author{} 的花括号里输入作者的名字。当然,也可以把自己的通信地址、email写在里面。就像下面这样:

注意, \ 代表“强制换行”。

再新起一行,加上日期:

其实,没有 date{today} 这一句系统会自动把今天的日期添加上的。而且 date{} 里面也不一定非要是当天的日期。

title, author, date 一般被叫做文章的 top matter 。

再新起一行,写

maketitle 自然是要排版 top matter 了。换句话说,不要标题的话可以省略掉这个命令。现在文章变成了这样:

好奇的话,现在可以编译一下,看看PDF文件的效果:

如果你的 xpdf 没出毛病的话,一个PDF文件应该显示在屏幕上了。如果 xpdf 不正常,那么就打开命令行,敲:

效果还满意吧?保持你的好奇心。在下面的操作中,你随时可以编译一下看看效果。

好了,回到Emacs。现在你的光标应该停在 maketitle 的下面一行。我们开始写“摘要”部分。敲键盘

前面我们已经见到过 C-c C-e 了,就是要开始一个“环境”。接着来, mini buffer 里现在又有提示了:

是在问你要开始那种环境啊?默认是开始 itemize 环境,因为它是最常用的环境。但我们现在要写的是“摘要”,告诉它:

abstract 就是“摘要”的意思。科技论文都是要有摘要的嘛。于是,你的文章变成了这样:

光标停在 begin{abstract} 和 end{abstract} 之间(第6行)。好,现在往摘要部分里填点东西:

现在,我们要接着上面的例子,写更多更长的东西了。为了编号方便,文章末尾的 end{document} 我也不再写出来了。

好, 按 C-n 把光标移到 end{abstract} 的下一行。让我们开始文章的第一节:

s 代表 section, “节”的意思。 mini buffer 提示:

也就是问你,是不是要起一个新 section 啊?没错,我就是要起一个新的章节,于是直接 C-j 。

mini buffer 又提示:

也就是问你,章节标题是……?那就给它个标题吧,就叫“ Introduction ”。 C-j 之后, mini buffer 继续提示:

这是在问你,要不要给这个新章节打个标签,比如 sec:introduction, 以后也许要索引到它呢?这个暂时无关紧要, C-j 就是了。(第18行)

给这一节添加内容:

注意到了吗?在这一节里有一个新命令 cite{} (我‘笔误’成了 citee{}, 以避开 org->html 转换的一个小bug), 这是在引用一个参考文献。先不管它,后面再说。

如法炮制,再添加几个章节:

注意到 emph{} 了吗?它代表 emphasize ,“强调”。英文习惯用斜体字来表示强调的东西,那么自然, emph{top matter} 就是把 top matter 排版成 top matter 了。

注意到 subsection{} 了吗?一会儿,我们还会看到 subsubsection 。不用解释吧,文章的章节次序是这样:

  1. chapter
  2. section
  3. subsection
  4. subsubsection
  5. paragraph
  6. subparagraph

其中, chapter 是给 book 和 report 用的,而 article 是从 section 开始。

现在我们就来一个 subsubsection 。不出所料的话,光标应该在第27行。那么就:

mini buffer 提示:

当然输入:

mini buffer 提示:

输入:

mini buffer 提示:

似曾相识吧?敲 C-j, 那么,你看到的是:

也就是说,我们有了一个 subsubsection (第28行) 。现在,我们再添加一个 environment:

mini buffer 提示:

我们当然不再需要 abstract 了,现在我们要的是 itemize ,也就是“不带序号的列表”。那么当然输入:

于是看到:

光标停在 item 的后面(第32行)。非常好,这正是我想要的。直接输入如下文字:

然后,

也就是,左手拇指按住 Alt 键,同时右手小指去敲回车键。你会看到这样的效果:

也就是说,不仅换了行,而且自动有了 item 等待你输入新的东西(第3行)。

你一定注意到了 verb|| 这个新命令。它的作用和bash命令行的单引号 () 是一样的。还记得吧,在命令行,单引号里的东西是原样输出的。 verb|| 里的东西也一样。 verb 是 verbatim 一词的缩写,就是“原样引用”的意思。好奇的话,就 C-c C-c 一下,看看效果。

好,继续输入:

得到:

没什么好说的。现在我们要在 itemize 环境里面再来一个 itemize 。光标现在应该在第3行的最后。敲:

于是得到:

简单吧?不用说了,你肯定知道下面这些是怎么来的了吧。

编译一下,看看效果吧。

好了,请你现在照猫画虎,再来一个 subsubsection ,标题叫 Author Information 。模仿上面的东西,来得到下面的东西:

怎么样,不太困难吧? 目前为止,我们用到的无非是下面这几个快捷键操作而已:

C-j C-c C-m C-c C-s C-c C-e M-return

下面让我们再起一个小节:

得到:

添加一些文字:

你应该能猜到,凡是跟在 % 后面的都是注释。

在这一小节,我们来尝试一下表格的输入。

先起一个新“环境”,叫 center :

得到:

center 当然是“居中”的意思了。在 center 环境里面,我们添加一个 tabular 环境:

这时你会看到这样的提示:

直接 C-j ,又看到提示了:

这是问你,表格的格式……有几列?每列之间要不要有竖线分割?……我的答案是这样:

也就是:竖线(|)小写L(l)竖线(|)小写L(l)竖线(|)。小写L代表 left ,也就是“左对齐”的意思。那么,你应该恍然大悟了,不就是……竖线-左对齐-竖线-左对齐-竖线嘛。那么,举一反三,除了小写L,我们还会见到r(右对齐)和c(居中)。现在,

得到如下结果:

表格环境里也是可以有注释的:

现在我们开始画表格,边画边体会一下上面几行注释的意思吧。光标现在应该在第(hline)行,先画一条横线:

所谓 hline ,顾名思义,就是 horizontal line 。

开始第一行:

那个 & 就是两列之间的分隔符, \ 我们见过,表示换行。

照猫画虎,把所有的行都加上,得到如下结果:

这张表格的效果应该类似于下面这样:

Command Level
part{} -1
chapter{} 0
section{} 1
subsection{} 2
subsubsection{} 3
paragraph{} 4
subparagraph{} 5

现在编译一下,看看效果,还过得去吧?

好了,表格画完了。再添加点文字:

现在我们讲讲“参考文献”。其实还是个 environment ,叫 thebibliography 。试试吧,

mini buffer 提示:

这是问你,在引用参考文献时,采用两个字符宽的标签是否合适?你知道, 参考文献在文章中被引用到的时候,不都是以 [1],[2]...[99] 这样的形式出现吗?所谓“两个字符的宽度”,也就是说方括号里的数字不超过两个,也就是说你的文章中最多可以有 [1]...[99]99个文献索引。这对于一篇普通的文章来说肯定是足够多了。

如果你还是不知道这合不合适,那么就假装合适, 按 C-jmini buffer 提示:

这是问你,要不要给每个参考文献条目加个标签?不理它, 按 C-jmini buffer 提示:

这是必须要理的。所谓 key ,实际上就是一条参考文献的“标识号”,它是和前面我们见到的 cite{} 命令配合使用的。在引用一条参考文献时,就必然要通过它的标识号来唯一地找到它。比如 citee{lamport94} 就是要从参考文献列表中找到 lamport94 所对应的那一条。没明白?那么我们先给它一个 key ,等会儿编译一下,看看效果就明白了。输入:

得到如下效果:

现在把参考文献写进去就行了:

再加一条:

得到:

一篇像模像样的科技论文到此就算是大功告成了。

编译一下,看看结果吧。

连看带写,把前面这些东西走一遍,应该不超过一个小时吧。现在我们总结一下你用到的东西:

  • LaTeX的基本命令和环境
    title{} author{} date{}
    section{} subsection{} subsubsection{}
    itemize tabular center
  • 最基本的Emacs快捷键(以 C-x 开头的比较多)
    文件操作 C-x C-f C-x C-s C-x C-c
    编辑操作 C-g C-j C-i C-/
    C-@ C-SPACE C-x h C-w C-INSERT
    C-k C-y
    C-d M-d
    移动光标 C-a C-e C-f C-b
    C-n C-p C-v
    窗口操作 C-x 2 C-x 3 C-x 0 C-x 1 C-x o
    帮助 C-h i C-h t C-h k C-h f C-h v
  • 最基本的AucTeX快捷键(以 C-c 开头的比较多)
    C-c C-e C-c C-s C-c C-m M-return
    C-c C-c C-c C-v

2 入门以后……

有了第一部分的基础,你可以自己看点参考资料了。

  1. AucTeX手册就在Emacs里面:
  2. 花两个小时看看lshort 。打开命令行窗口,敲:

后面,我们还会简要介绍

  1. 如何插入图片
  2. 如何写数学公式
  3. 如何插入程序代码
  4. 如何写中文
  5. 如何用毕业论文模版
  6. 如何做幻灯片
  7. emacs org-mode

2.1 如何插入图片


怎么样,能看明白吗?插入图片用到了三个新命令:

  1. usepackage{graphicx}, 这是在说“我要用到一个名字叫 graphicx 的package(宏包)”。似曾相识吧?它不是很类似#include<stdio.h> 吗? includegraphics{} 就是这个宏包提供的命令之一。想详细了解 graphicx, 敲:
  2. graphicspath{{./figs/}{./}}, 显然这是在指明graphics(图片)所在的path(路径,位置)。
  3. includegraphics[width=5cm]{tux}, 这当然就是插入图片了。
    1. 图片的名字叫 tux.pdf, 后缀(.pdf)可以被省略掉。显然 tux.pdf 应该被存放在 ./ 或者 ./figs/ 中,才能被找到。我喜欢PDF图片,因为它可以自由缩放。你当然可以插入jpeg、png图片。
    2. 宽度是5cm,也可以是相对宽度,比如 [width = .5textwidth] 就表示宽度等于0.5倍的行宽。

如果你希望图片“居中”摆放,那自然是要用到 center 了:

“哎,为什么没有图片说明?比如,【图1: Linux图标】?” 当然可以有,我们要用到一个新environment了,就叫 figure :

mini buffer 提示:

这是在问你图片放在那里比较好啊?是靠上?还是靠下?还是……懒得操心?那还是让LaTeX来决定吧, C-jmini buffer 提示:

这是在提示你输入图片的说明文字。那么输入:

mini buffer 提示:

当然是:

mini buffer 提示:

这是要你给图片打个标签,以后方便索引到它。那么就给个标签:

于是得到:

现在你建立了一个完美的图片环境,别忘了把图片放进去。当然放在第(fig)行:

来试试 label{} 的作用:

编译一下,看看效果吧。 label{} 和 ref{} 总是配合使用的,一个用来打标签,另一个用来找到它。

2.2 如何插入数学公式

举个简单的例子吧:

结果是这样:This is a simple math example: c2=a2+b2

  • 美元符号($)在LaTeX里面是特殊字符。夹在两个美元符号之间的东西,会被当做数学公式来排版。
  • 如果想让数学公式独占一行的话,就这样:

    也就是每边用两个美元符号。如果想给数学公式排序号的话,就把它放进 equation 环境里:

    结果就是这样:

    编译一下看看,公式右边是不是有序号了?简单吧。

    数学公式排版是LaTeX的强项,各式各样的数学符号、怪异字符无所不及。当然用不着都记住。你只要记住上面这点东西,剩下的,知道查手册就行了:

    1. lshort, chapter 3
    2. The LaTeX Companion, chapter 8

2.3 如何插入程序代码

看个例子就了然了:

  1. 首先要 usepackage{minted} 。在LaTeX文件中插入代码的工具包有不少,比较传统的是 listings, 比较新潮的是 minted。我们当然选用新潮的。想详细了解 minted 的用法,就
  2. 开始一个新环境 minted ,把你的程序拷贝进来。怎么?程序太长,拷贝起来太麻烦?那么可以这样:

    简单吧? hello.c 当然要和你的 TeX 文件在同一个目录下,否则你要指明详细路径。

    minted 宏包提供了丰富的命令,可以支持数十种编程语言,后台调用强大的 pygments 来打扮你的程序代码,可以把程序以各种你能想到的方式排版出来。

    当然,使用 minted 的前提条件是,系统里已经安装好了 python 和 pygments 。这一点在 minted 的手册里已经说得很清楚了。

    关于强大的 pygments, 你该去它的网站看看:http://pygments.org/

2.4 如何输入中文

如果你的Ubuntu配置和D215机房是一致的,那么输入中文就是“piece of cake”:

一个现成的LaTeX模版立时展现在你面前:

这个模版里有你写一篇漂亮中文文章所需要的一切。光标就停在 title{} 的花括号里,那么就开始用中文填空吧。Happy TeXing!

2.5 完美的毕业论文

  • 写普通文章要用 documentclass{article} ;
  • 写报告要用 documentclass{report} ;
  • 写书要用 documentclass{book} ;
  • 写信要用 documentclass{letter} ;
  • 那么写毕业论文自然要用毕业论文模版了:

    写毕业论文是个庄严的大事情,当然要为它专门建立一个目录吧。目录建好了,把 swfcthesis.cls 文件拷贝到这个目录里。然后就可以用它来写你的论文了。

简而言之,swfcthesis.cls 就是我们的论文模版,它提供了如下一些基本命令:

  1. Title{论文标题}
  2. Author{作者}
  3. Advisor{指导教师姓名}
  4. AdvisorTitle{指导教师职称}
  5. AdvisorInfo{指导教师简介}
  6. Month{这里填月份}
  7. Year{这里填年份}
  8. Univ{这里填校名}
  9. School{这里填院名}
  10. Subject{这里填专业}
  11. Docname{本科毕业(设计)论文} :目前我们只关心本科毕业论文
  12. Abstract{这里填上中文摘要}
  13. Keywords{这里填上关键字}
  14. Acknowledgments{这里填上鸣谢某某某}
  15. enTitle{这里填上英文标题}
  16. enAuthor{这里填上你的洋名字}
  17. enUniv{这里填上英文校名}
  18. enSchool{这里填上英文院名}
  19. enAbstract{这里填上英文摘要}
  20. enKeywords{这里填上英文关键字}
  21. makepreliminarypages{} :生成封面、摘要、英文摘要……
  22. Appendix{} : 附录部分由此开始
  23. advisorinfopage{} : 生成【教师简介】
  24. acknowledgmentspage{} : 生成【鸣谢】

具体如何来用这些命令呢?简而言之,

现在一个论文模版就呈现在你的眼前了。

你要做的就是用你前面学到的那些LaTeX命令来填空。别忘了,你随时可以编译一下,看看效果。

还不明白?再看个例子来找找感觉吧:

  • thesis2.tex

上面的例子中,用到了三个 include{} 命令,分别把 bibliography.texappendix.tex, 和 source.tex 三个文件的内容包含了进来。也就是说,你事先写好了三个文件:

  1. bibliography.tex: 用来存放参考文献
  2. appendix.tex: 用来存放附录内容
  3. source.tex: 用来存放程序代码

下面是这三个文件的例子:

  • bibliography.tex

  • appendix.tex

  • source.tex

关于论文模版的实现细节、应用实例等信息都可以在这里找到。

2.6 LaTeX Beamer — 完美的幻灯片

2.6.1 Hello, world!

让我们还是先拿英文来举例子,最后再说怎么写中文。

一套幻灯片是由若干幅画面(frame)组成的,每个 frame 可以有一个标题(frametitle)。Easy? 编译一下,看看效果,还不坏吧?

frame 里面可以放任何东西,比如

  • itemizeenumerate
  • exampleexampleblock
  • columns
  • 逐行显示:

白加黑太单调了?那么,尝试一下七色阳光:

LaTeX beamer提供了大量现成的花哨式样,你只要

就行了。去哪里找?

2.6.2 中文幻灯片

如果你的Ubuntu配置和D215机房是一致的,那么输入中文就是“piece of cake”:

一个现成的LaTeX beamer模版立时展现在你面前:

这个模版里有了你做漂亮幻灯片所需要的一切。光标就停在 title{} 的花括号里,那么就开始用中文填空吧。我所有的课程讲义都是从这个模版产生的。

如果你嫌它不好看,那么尽管自由发挥,参考《Beamer用户手册》就可以了:

Happy TeXing!

2.7 Emacs Org-mode — 自动生成LaTeX和PDF

Org-mode是Emacs的一个功能模块,它是用来写org文件的。

  • 那什么是org文件?就是以 .org 结尾的文件。
  • 那org文件长什么样?用Emacs打开这个文件,看看就明白了。

换言之,你正在看的这篇小教程就是用org文件生成的。写好的org文件不仅可以生成漂亮的html文件,还可以生成不错的LaTeX文件PDF文件纯文本文件……

  • 如你所看到的,org文件的语法极其简单,基本上不用学就能用了。
  • Org-mode也有一套方便的快捷键,自己试试吧。
    • 针对标题的操作:
      C-return C-c C-n C-c C-p
      M-up M-down M-left M-right
      tab shift-tab C-tab
    • 针对列表的操作:
      M-return C-j
      M-up M-down M-left M-right
      shift-left shift-right
      alt-shift-left alt-shift-right
      tab
    • 针对文章输出的操作:
      • C-c C-e t : 修改默认的输出参数
      • C-c C-e h : 输出HTML
      • C-c C-e l : 输出LaTeX
      • C-c C-e p : 输出PDF
      • C-c C-e a : 输出ascii(纯文本)
  • 除了写点简单的文章,Org-mode最强大的地方是它的“管理”功能,org本就代表 organization
    • 项目管理,任务管理,日程管理,账务管理……
  • Org-mode手册就在Emacs里面:
  • 更多参考资料:
总结 The 9th Zhejiang Provincial Collegiate Programming Contest

总结 The 9th Zhejiang Provincial Collegiate Programming Contest

题目链接

http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=337

代码神马的还没有写完 ,先把思路放上来 等到代码写好之后再贴代码

Taxi Fare

水题,注意精度问题 求出来的两个费用都要四舍五入 如果只对最后一次进行四舍五入的话会WA

Unrequited Love

这个题是想法+STL搞 首先 根据名流问题的思想 我们可以通过O(N)的算法排除掉不可能是答案的人 最后剩下一个人判断一下他是不是喜欢宴会上的所有人即可。 具体思想如下:如果A喜欢B,那么B就不可能是Unrequited Love King or Queen (以下简称ans)反之,如果A不喜欢B 那么A就不可能是 ans 因此每次判断都会使问题的规模缩小1 这样就可以把问题规模在O(N)时间内缩小到 1,这样就只用判断一下这个人是不是ans即可,具体实现的时候 用 set存所有的喜欢关系 每个关系用一个二元组 pair<int,int>来表示,每一个名字映射到一个map<string,int>上 ,在具体实现时可以对上面的名流问题的解法进行优化,我们只需要一重循环从1—>N初值ans=1 然后去判断 如果ans不喜欢 i 或者 i喜欢ans 那么我们就更新ans 为 i 这里我们只判断了两种情况 实际上,ans 和 i之间的关系有四种 :

  1. ans喜欢i
  2. ans不喜欢i
  3. i喜欢ans
  4. i不喜欢ans

我们需要说明一下 循环中 既不满足 2 也不满足 3的i值一定不会是ans  ,很明显可以看出,这时,i和ans的关系一定是 1 4的任意一种,而这两个关系的任何一个 都说明了 i不可能是ans 所以我们这时候不去更新ans是正确的。因此这个算法的具体实现也没有问题了。 然后最后得到的ans我们还要判断一下他是不是喜欢所有人 。

—ps 这个题和性别无关哦~~~  heterosexuals 男男之间也可以互相喜欢哒 。有些人没看到这个地方以为是只有异性之间才可以互相喜欢 那么就会把问题搞错搞复杂

Count the Trees

还是用hash的思想来稿 具体实现可以用map 这个题让我们判断有多少相同的子树,每个子树的样式可以用一个标号唯一确定 一棵树总共有n棵子树,同时 每个子树的结构可以用它的左右子树来唯一表示 ,这样的话 就建立了对应关系 我们用 pair<a,b>表示一个左子树样式标号为a右子树样式标号为b的树,用 map<pair<a,b> k>表示 这棵树的样式标号映射为k 然后再用一个一维数组tree[1-N]保存每颗子树的样式标号 ,特殊处理叶子节点 叶子节点的样式标号全部为 0 然后map[pair<-1,-1>]=0即可。通过上面的方式,我们建立起第一棵树之后,用同样的方式建立第二棵树,并且每次进行合并操作的时候遇到一个pair 就去左边查询是否存在这个pair 存在的话 取出它的标号 然后去tree这个数组里循环一次,统计所有样式标号与之相同的,这些子树的结构都与其同构。然后输出总的同构树即可。

Draw Something Cheat

水题,用二维数组 a[N] [26]保存一下第i 次输入中 每个字母出现的次数(0–25表示字母) 并且,找出每个字母出现的最少次数 按照顺序输出即可

Tunnel Network

这个题属于数学题 如果不知道Cayley公式和Prufer编码这个题真的就几乎无解了,Prufer编码的详细知识可以参看这个文章,matrix巨巨写的。下面只说明本题的思路,这个题里面N个节点的图 有S个 联通分量而且 第i个联通分量一定有i这个节点,而且判断联通分量是否相同时和标号有关 即 10 11 联通 与 9 8 联通是不同的两个情况 ,我们要求的是总共有多少种可能的连通方式。我们给图中加一个根节点 0 并让 0与每个联通分量相连,这样的话 就构成了一个由n+1个节点构成的有序号的无向树,这里需要改变一下Prufer编码的方式 我们让Prufer编码从节点标号最大的叶子开始删除 其它的不变,显然这样的Prufer编码还是与无向树一一对应,然后 注意到 这个Prufer序列的最后s-1个元素一定是0 (因为最后s-1个删除的节点一定是s—–2这些节点) 然后 倒数第s个元素一定是 1–s中的某一个值 (因为在这棵树变成只含有0—–s这些节点的树之前的状态,一定有一个叶子节点与1—s中的某一个相连,则删除它的时候会添加进来1—s中的某个值) 然后 问题就解决了 根据Prufer公式 本题中有N+1个节点 ,Prufer序列的长度为 N+1-2=N-1,排除掉有特殊情况的Prufer编码序列中最后S位 剩下的n-1-s位每一位都可以取1—N的任意值构成Prufer序列 所以 总数为 N^(N-S-1)*S ,然后用快速幂搞一下即可

Find the Marble

DP到现在为止知识储备还几乎是零,队友讲解了这个题之后总算明白了 这个题由于求概率的话 数字小到double会丢精度,因而我们存频数 并且使用三维来存储状态

dp[n][m][k]表示的是: 第m次交换时,看到k次交换的情况下 球在n号杯子里的频数,它的值就是 dp[n][m-1][k]+dp[CC][m-1][k-1]  ,即 前m-1次交换时,看到了k次 (即这次没看到)  看到球在n号盒子里的频数,以及 前m-1次交换时,看到了k-1次 (即这次看到了)看到球在CC号盒子里的频数 (这里有一个判断 如果 第m-1次交换的序列中 有 (n,CC) 或 (CC,n)这样的交换 ,那么球所在的盒子就会变,否则的话,球所在的盒子还是n 所以 CC要么是 n 要么是第m-1次交换的另一个杯子的编号) 。

初始状态 要把 dp[s][0][0]置为1 其它全部置零即可 然后循环的时候,三重循环的顺序如下:

i=1 To m

j=1To i

k=1 To n

然后 最后找出 dp[1–N][m][k]中的最大值对应的N 就是我们要求的结果

Lazy Salesgirl

广告位出租…

Lazier Salesgirl

广告位出租… 简单的模拟 不过我还没做

Signal Detection

广告位出租…

Modular Inverse

本来是扩展欧几里德 不过数据很水,用一下暴力就解决了 注意特殊情况的判断 m=1的时候会有特殊情况

Yet Another Story of Rock-paper-scissors

这个故事告诉我们 做人要心怀善心为他人着想。

在题目描述下 每次都是女的会赢,所以只要输出一个字串即可