Jan 23

汉字产生的扭曲错觉

Tiny Tricks 0 Comments

三支女大十一金三支女大十一金三支女大十一金三支女大十一金三支女大十一金三支女大十一

金一十大女支三金一十大女支三金一十大女支三金一十大女支三金一十大女支三三支女大十一

三支女大十一金三支女大十一金三支女大十一金三支女大十一金三支女大十一金三支女大十一

金一十大女支三金一十大女支三金一十大女支三金一十大女支三金一十大女支三三支女大十一

三支女大十一金三支女大十一金三支女大十一金三支女大十一金三支女大十一金三支女大十一

金一十大女支三金一十大女支三金一十大女支三金一十大女支三金一十大女支三三支女大十一

三支女大十一金三支女大十一金三支女大十一金三支女大十一金三支女大十一金三支女大十一

金一十大女支三金一十大女支三金一十大女支三金一十大女支三金一十大女支三三支女大十一

三支女大十一金三支女大十一金三支女大十一金三支女大十一金三支女大十一金三支女大十一

金一十大女支三金一十大女支三金一十大女支三金一十大女支三金一十大女支三三支女大十一

三支女大十一金三支女大十一金三支女大十一金三支女大十一金三支女大十一金三支女大十一

金一十大女支三金一十大女支三金一十大女支三金一十大女支三金一十大女支三三支女大十一

偶然看到的，这些字确实给人一种扭曲的感觉。

Jan 22

无限递降法

Art of Science 0 Comments

无限递降法就是一种特殊的反证法，它利用了最小自然数原理。先假设存在一个最小解，然后在这个最小解的基础上推出一个更小的解，再结合最小自然数原理得到矛盾，从而证明命题。

无限递降法经典的一个例子就是证明x4+y4=z2没有正整数解。

我们假定存在一个正整数解，那么其中必定存在一个解x0,y0,z0使得z0最小。我们得到必有(x0,y0)=1，否则会推出一个更小的解。由于$x_0^2,y_0^2,z_0$是方程x2+y2=z2的一个本原解，所以x0和y0必然是一奇一偶，不妨设2|y0，以及(y0,z0)=1。

我们有$(2z_0,2y_0^2)=2(z_0,y_0^2)=2$，由此及2不整除$z_0-y_0^2$即得$(z_0-y_0^2,z_0+y_0^2)=1$。我们又有

$(z_0-y_0^2)(z_0+y_0^2)=x_0^4$

令$z_0-y_0^2=u^4,\quad z_0+y_0^2=v^4$。这里v>u>0,(u,v)=1，u,v都是奇数。进而有

$y_0^2=(v^2-u^2)\frac{v^2+u^2}{2}$

我们又得到(v2-u2,(v2+u2)/2)=1，因为(v2-u2,v2+u2)|(2v2,2u2)=2(v2,u2)=2，又u,v都是奇数，所以2不整除(v2+u2)/2，所以(v2-u2,(v2+u2)/2)=1。

我们再令v2-u2=a2,(v2+u2)/2=b2，这里a>0,b>0,(a,b)=1,2|a,2不整除b。由u,v满足的条件及a,b得0<b<v<z0，及u,a,v是方程x2+y2=z2的本原解且2|a。因此得到u=r2-s2, a=2rs, v=r2+s2。所以r4+s4=b2，而b<z0，与z0的最小性矛盾，命题得证。

无限递降法对于构造的要求很高，确实不是一个很好用的方法。

Jan 21

转换音频文件ID3编码

Tips on Computer 0 Comments

Linux下面的播放器总是对GBK和UTF8处理的不够好，ID3还是统一转换成Unicode比较方便。 

sudo apt-get install python-mutagen
mid3iconv -e GBK *.mp3
mid3iconv -e GBK *.wma

上面是一种我喜欢的做法。其实也可以用比如EasyTag之类的Tag编辑器，到这里可以下载。

Jan 20

beamer+xeCJK设置

Tips on Computer 0 Comments

 我的模板，比较简单：

\def\version{XXXXXX}

\documentclass[dvipdfmx]{beamer}

\usepackage[CJKtextspaces]{xeCJK}
\input{xecjkfonts}

\newcommand{\roma}[1]{\romannumeral #1}
\newcommand{\Roma}[1]{\expandafter\@slowromancap\romannumeral #1@}

\newcommand{\bbold}[1]{\textbf{#1}}

\newcommand{\aabs}[1]{{ \left| #1 \right| }}
\newcommand{\ffloor}[1]{{ \left\lfloor #1 \right\rfloor }}
\newcommand{\N}{\boldsymbol{N}}
\newcommand{\Z}{\boldsymbol{Z}}

\newtheorem{thrm}{定理}[section]
\newtheorem{prop}{性质}[section]
\newtheorem{exmp}{例题}[section]
\newtheorem{defn}{定义}[section]
\newtheorem{lemm}[thrm]{引理}
\newtheorem{coro}[thrm]{推论}

\renewenvironment{proof}[1][证]{\noindent \textbf{#1.} }{\hfill$\Box$}

\usefonttheme{serif}

\usetheme{Berkeley}
\usecolortheme{seahorse}

\begin{document}
\title{}
\author{}
%\institute{}
\date{\version}

\begin{frame}
\titlepage
\end{frame}

%\begin{frame}{主要内容}
%\tableofcontents[currentsection,currentsubsection,subsectionstyle=show/show/hide]
%\end{frame}

\end{document}

xecjkfonts的内容在《xeCJK的字体配置》里面可以找到。

Overlay Specification就是一个显示的问题，无论是什么命令，\XXX<a-b>都可以控制内容在当前frame的第几个slide上面显示。比如\textbf<2>{TEST}就是在第2张slide上使用\textbf效果。\color<2->{}表示从第2张slide开始，以后的所有slide上面都有\color效果。\texttt<-4>表示内容一直存在到第4张slide为止。\only命令可以帮助显示无效果的内容，比如\only<2-3>{TEST WORDS}，表示从第2个slide显示到第3个slide。overlayarea环境也可以帮助显示上面所说的\XXX<a-b>的效果。

\pause命令就是一个暂停的指令，一个\pause可以使得后面的内容推迟一个slide显示。\onslide则是直接显示后面的内容，无视\pause。

下面附送常用设置： 

\setbeamertemplate{theorems}[numbered] %使用定理编号
\setbeamertemplate{caption}[numbered] %图和表格编号
\setbeamertemplate{navigation symbols}{} %取消导航条

%使用MetaPost
\usepackage{xmpmulti}
\DeclareGraphicsRule{*}{mps}{*}{}  

\begin{enumerate}
\addtocounter{enumi}{3} %改变列表标号计数器
\end{enumerate}

%整体缩小表格
\usepackage{graphicx}
\newsavebox{\tablebox}
\begin{lrbox}{\tablebox}
\end{lrbox}
\scalebox{0.5}{\usebox{\tablebox}}
%或者\resizebox{0.8\textwidth}{!}{\usebox{\tablebox}}

%设定“结构”的前景色
\setbeamercolor{structure}{fg=beamer@blendedred}

%批量改变block标题颜色和block主干颜色，利用“<颜色>!<数字>!<颜色>”来进行混合
\setbeamercolor{block title}{use=structure,fg=structure.fg,bg=structure.fg!20!bg}
\setbeamercolor{block title alerted}{use=alerted text,fg=alerted text.fg,bg=alerted text.fg!20!bg}
\setbeamercolor{block title example}{use=example text,fg=example text.fg,bg=example text.fg!20!bg}
\setbeamercolor{block body}{parent=normal text,use=block title,bg=block title.bg!50!bg}
\setbeamercolor{block body alerted}{parent=normal text,use=block title alerted,bg=block title alerted.bg!50!bg}
\setbeamercolor{block body example}{parent=normal text,use=block title example,bg=block title example.bg!50!bg}
\setbeamercolor{titlelike}{parent=structure,bg=white!90!red}

%设置使用衬线字体做正文（默认全是无衬线，按这个设置，仅标题是无衬线）
\usefonttheme[stillsansseriflarge,stillsansserifsmall]{serif}

%设置半透明化尚未出现的内容（方便提醒自己下面要讲什么）
\setbeamercovered{transparent}

%取消导航条
\setbeamertemplate{navigation symbols}{}

%以下命令中通过选择show或者hide控制相应节的显示
\tableofcontents[currentsection,currentsubsection,subsectionstyle=show/show/hide]
Jan 19

SRM 410 Div1 - WifiPlanet

Art of Science 1 Comments

题目在这里可以找到。

题目的大概意思是说，在整数格点的平面上有一个简单多边形（顶点坐标均为有理数），问其内部有多少格点。题目保证不会有格点出现在边界上。

三角剖分是不现实的，我们只能选择简单一些的梯形剖分。进而，我们需要计算一条直线下方的格点数目。这里的转化都比较简单，直接略过。接着，我们就把问题转化为了求一个这样的式子：

$\displaystyle\sum_{i=0}^{n-1}\left\lfloor\frac{a+di}{m}\right\rfloor$

这是一个相当有趣的求值。显然，O(n)的算法并不能让我们满意。对于这个经典的问题，我们有$O(\sqrt{n})$和$O(\log n)$两种算法。$O(\sqrt{n})$由于细节问题很多，我介绍的是$O(\log n)$的算法。对$O(\sqrt{n})$算法有兴趣的同学可以查看相关的论文。

考察这个式子，首先，a和d都应该满足大于等于0，小于m的条件。否则我们可以通过变形得到新的a'和d'。我们如果要在$O(\log n)$时间内计算出它的值，一定要设法缩小它的规模。我们将这个式子呈现在平面坐标系中，发现这其实就是求下面的一个图中

所有蓝色点的数目。所有的水平直线表示用来截取的y=km的常函数，红色的点则是(i,a+di)。问题到现在就是求每个点向下引射线，一共和这些直线能够有多少交点。显然，这些直线一共有$l=\left\lfloor\frac{a+dn}{m}\right\rfloor$条。那么，我们对每条直线进行观察，发现如果我们只是求一条直线上有多少交点，是可以在O(1)的时间之内计算的。对于一条直线y=km，我们可以求出所有的交点数是$\left\lfloor\frac{a+dn-km}{d}\right\rfloor$。

至此，问题的规模已经被缩小了，我们得到新的式子：

$\displaystyle\sum_{i=0}^{n-1}\left\lfloor\frac{a+di}{m}\right\rfloor=\sum_{k=0}^{l-1}\left\lfloor\frac{a+dn-km}{d}\right\rfloor$

这里，我们需要对等式的右边进行一些细节处理，因为a+dn和m可能大于d。这样，我们成功的把问题规模缩小了，而这是一个类似取模的缩小方式，我们自然得到每次问题的规模至少被缩小到原来的一半，那么算法的复杂度就是$O(\log n)$级别的。