C++ FAQ Digest

Following the exciting news of the launch of C++14, I found a FAQ page of C++ standard.

It's time to learn some interesting new features now, so I plan to read FAQ first.

Here I will record some interesting and useful (I think) digests from those FAQ pages.

Why is C++ so big?

Are virtual functions (dynamic binding) central to OO/C++?

I’m from Missouri. Can you give me a simple reason why virtual functions (dynamic binding, dynamic polymorphism) and templates (static polymorphism) make a big difference?

What is the best book to learn C++ from?

Should I buy one book, or several?

What are some good C++ coding standards?

Should I use using namespace std in my code?

Which is better: identifier names that_look_like_this or identifier names thatLookLikeThis?

What’s a good coding standard for using global variables?

Whoa, but what about machines or compilers that support multibyte characters. Are you saying that a “character” and a char might be different?!?

How can I provide printing for an entire hierarchy of classes?

What’s the difference between “const X* p”, “X* const p” and “const X* const p”?

What is the relationship between a return-by-reference and a const member function?

Why am I getting an error converting a Foo** → const Foo**?

To be continue..

最大公约数与欧几里德算法

大家对最大公约数这个概念应该不陌生,粗略回忆一下,大概小学的数学课就应该有介绍。并且大家稍微动动笔应该就可以算一算一些比较小的数字的最大公约数。

我们先来回忆一下这个概念。

首先是定义约数。

定义:如果ab都是整数,a \not= 0,如果存在一个整数c,使得b=ac我们就说a整除b。如果a整除b,那么a就是b的一个因子或者约数b则是a倍数

如果a整除b,我们记做a|b。如果a不整除b,我们记做a \not| b

由此,有一些显而易见的结论,这里不加证明地给出来:

结论1:如果a, bc都是整数,并且有a|bb|c,那么a|c

结论2:如果a,b,mn都是整数,并且有c|ac|b,那么c|(ma+nb)

有兴趣大家可以自己根据定义证明一下。接下来看一个比较重要的结论:

结论3:如果ab都是整数,并且b>0,那么存在唯一整数对q,r使得a=bq+r0 \le r < b

我们把q叫做,把r叫做余数

结论3是欧几里德算法的基础,比较重要,所以我们还是稍微证明一下。不过这个结论的证明需要用到良序性质,所以我们先介绍下良序性质。

良序性质(Well-Ordering Property):所有的非空正整数集都有一个最小值。

有了这个性质我们就可以比较容易地证明结论3了。

证明:令集合S=\{a-bk|k \in \mathbb{Z}\},令TS中的非负整数集合。由于k < a/b时,a-bk>0,所以集合T必然非空,根据良序性质,T中存在一个最小值r=a-bq。易知r \ge 0(如果T中没有0r>0,反之则r=0)。假设r \ge b,则有r>r-b = a-bq-b=a-b(q+1) \ge 0,这样就与rT中的最小值矛盾,所以有0 \le r < b

下面证明唯一性。如果a=bq_1+r_1a=bq_2+r_2并且0 \le r_1 < b, 0 \le r_2 < b,那么我们有0=b(q_1-q_2)+(r_1-r_2)。因此r_2-r_1=b(q_1-q_2),也就是br_2-r_1的约数,因为0 \le r_1 < b, 0 \le r_2 < b,所以-b<r_2-r_1<b,由此当且仅当r_2-r_1=0,条件b|(r_2-r_1)得到满足。综上r_1=r_2并且q_1=q_2,唯一性得证。\blacksquare

现在我们正式定义最大公约数。

定义:两个不同时为0的整数ab最大公约数(greatest common divisor),是能同时整除ab的最大整数。

我们把ab的最大公约数记做(a,b)。有时候也记做gcd(a,b)。能同时整除ab的整数则是公约数,显然,最大公约数也是公约数。

注意到(0,n)=(n,0)=n,并且我们定义(0,0)=0

最大公约数的概念可以从两个整数扩展到多个整数,并且有着类似的记号。

下面我们来看看欧几里德算法(辗转相除法)。

定理1欧几里德算法。对于整数a \ge b > 0,令r_0=a并且r_1=b,如果我们连续使用结论3来得到r_j=r_{j+1}q_{j+1}+r_{j+2},其中0 < r_{j+2} < r_{j+1}, j = 0, 1, 2, ... , n-2并且r_{n+1}=0,那么(a,b)=r_n,即最后一个非零余数。

为了证明欧几里德算法的正确性,首先引入一个定理:

定理2:如果a,bc是整数,那么(a+cb,b)=(a,b)

证明:令eab的公约数,根据结论2,e|(a+cb),所以e也是a+cbb的公约数。令fa+cbb的公约数,同样根据结论2,我们知道f整除(a+cb)-cb=a,因此f也是ab的公约数,由此可知(a+cb,b)=(a,b)\blacksquare

由定理2立得以下推论。

推论1:如果ed是整数,且e=dq+rqr是整数,那么(e,d)=(d,r)

下面我们证明欧几里德算法。

证明:根据推论1,不难得出

 \begin{aligned} (a,b) &=(r_0,r_1) \\ &=(r_1,r_2) \\ &=(r_2,r_3) \\ &= \cdots \\ &=(r_{n-3},r_{n-2}) \\ &=(r_{n-1},r_n) \\ &=(r_n,0) \\ &=r_n \end{aligned}

因此(a,b)=r_n\blacksquare

欧几里德算法的作用就是计算最大公约数,这是一个古老而高效的算法,如果大家有一点计算复杂度的知识,可以知道这个算法只需要O(\log a)次除法。

最大公约数的用处非常多,一个有趣的用处是,在破解Vigenere密码的时候,可以用最大公约数确定密钥的长度。

我们以一个有趣的关于欧几里德算法的结论结束本篇话题。

大家知道费波那契数列(Fibonacci sequence)是这样定义的:

 \begin{aligned} f_0 &=0 \\ f_1 &=1 \\ f_n &=f_{n-1}+f_{n-2}, n \ge 2 \end{aligned}

f_{n+1}f_{n+2}为费波那契数列的相邻两项,当n > 1的时候,(f_{n+1},f_{n+2})=1

我们可以使用欧几里德算法证明这个结论:

 \begin{aligned} f_{n+2} & =f_{n+1} \cdot 1 + f_n \\ f_{n+1} &= f_n \cdot 1 + f_{n-1} \\ & \vdots \\ f_4 &= f_3 \cdot 1 + f_2 \\ f_3 &= f_2 \cdot 2 \end{aligned}

所以(f_{n+2}, f_{n+1}) = f_2 = 1\blacksquare

后缀自动机报告

后缀自动机是一个非常强有力的字符串工具。但是一直以来相关资料较少,连wiki也没有相关页面。搜索后缀自动机的结果往往是一些OI/ACM神牛的blog。其中最出名的莫过于CLJ的讲演用PPT和FHQ的blog

这些文章/blog相对来讲,注重代码的理解与应用,但是缺乏相关数学背景和证明,经过我努力查找资料,终于在学校图书馆里找到一本Applied Combinatorics on Words, 这本书对后缀自动机进行了非常详尽严格的证明与推导。看完之后会有一种豁然开朗的感觉。于是便根据这本书的内容写了一篇调查报告。由于我不知道怎么用(LaTeX) 对中文进行排版,再者是写给老师看的,所以写了英文版,还望诸位看官谅解。目前也暂时没有中文版的计划。

这篇报告的起因是我上的一门读书课。教授会指定一本书阅读,每周有一小时的时间跟教授谈谈都读到了些什么。其中一个章节是后缀树,我思量着后缀树的递归建立十分复杂繁琐,虽然时间复杂度也是(O(n)),但是显然不如后缀自动机简洁,于是决定讲后缀自动机。结果两周下来,还是没能把后缀自动机讲清楚,无奈之下只好继续讲后缀树。但是后缀自动机因其简洁的代码必定会在各种场合大放异彩,所以我思前想后,决定还是写成报告呈给老师一阅以聊未能讲清之憾。

废话这么多,还是赶紧给出地址,如有错误和需要改进的地方还请留言指正,如果诸位有所收获,那我也不胜欣慰。

地址:An Introduction to Suffix Automaton.

TRAINING 2013.3.17 Simple Analysis

The contest link.

Though there are only three problems, the last two problems are harder than before.

A

A simple count problem. Count (0) and (1) of left doors and right doors respectively, then the answer is (min(left zero, left one) + min(right zero, right one)).

B

It's a little hard to solve the problem directly, so we print some result of small n. After that we can find that there is a cycle of the last three digits. So the problem is very easy to code. You can find the details with my Java helper.

C

A simple DP problem. The most important thing you should know is that the problem can be converted to the longest none decreasing subsequence. Let's look at the problem. First, the position is not necessary. Second, we can make a wrong position plant to the correct position with only one replant. Therefore, if we know how many plants needn't to replant, the answer is (n - NotNeed). So we can do the longest none decreasing subsequence first then calculate the answer directly.

Click here to access to my codes.

TRAINING 2013.3.10 Simple Analysis

The contest link.

A

A simple math problem. Just simulate the process described in the problem you can get the answer.

B

Another simple math problem. Calculate the 4 by 4 tile first and deal with the special cases.

C

Greedy and hash. Due to the small scale of (a_{i}), (b_{i}), (x_{i}) and (y_{i}), we can hash them and calculate the answer directly.

D

Implementation, and binary search. We can check an answer in (O(lg x)) time, and binary search the answer until we find the smallest one.

E

Also implementation, with in (O(n)) time, we can get the prefix sum of the occurance of (t leq 0) and the suffix sum of the occurance of (t geq 0). Then, we can record the smallest sum of every split in (O(n)) time.

F

First, find the only loop in the graph, mark their distance all zero. Second, simulate the shortest distance from the loop. Both can be done by depth first search.

Click here to access my codes.

TCO13 Round 1B

250

There is an array with (2n) numbers, we must divide them into (n) pairs, the goal is to minimize the difference of the maximum pair and the minimum pair.

The problem can be solved by greedy algorithm. But as you know, it's a little hard to make sure the greedy algorithm is a right solution. So let's talk about the algorithm first and then to prove it's correctness.

First, sort the array, then make pairs with the (i)th element and the ((2n - i - 1))th element, (i in [0, n)). Record the maximum value and the minimum value, so the answer is the difference.

And the correctness. In the sorted array, let's denote two elements with (a_{i}) and (a_{j}), (i < j), it's obviously that (a_{i} leq a_{j}). If we swap them, then we can find that (min(a_{i} + a_{2n-i-1}, a_{j} + a_{2n-j-1}) geq min(a_{j} + a_{2n-i-1}, a_{i} + a_{2n-j-1})) and (max(a_{i} + a_{2n-i-1}, a_{j} + a_{2n-j-1}) leq max(a_{j} + a_{2n-i-1}, a_{i} + a_{2n-j-1})), so the difference might be bigger than before, therefore, the algorithm is correct.

500

There is a board contains only '.' and 'X'. We can make the 'X's to '.'s with two kinds of operation -- a horizontal brush with the width of (R), or a vertical brush with the width of (C). Our goal is to make the board contains only '.' with minimum number of operations.

This is an easy brute force problem. With the bit skill, we can easily enumerate every conditions of horizontal brush or vertical brush, and then we calculate the number of vertical brush or horizontal brush if there is any 'X' left. So the complexity of the solution is (O(2^n * R * C * n * m)). It works very well due to the small scale.

1000

Ah...It's a little hard to explain the problem statement...so here is the link.

So the key to solve the problem is how to determine if two string is the same. Here is a  explanation from ftiasch.

  1. We can change any (s_{2i}) and (s_{2i+1}) pair, (0-index). One of the procedure is to reverse the ((2i + 2))-prefix first, next step is to reverse the first two characters, then reverse the ((2i + 2))-prefix again.
  2. If we denote the pair (s_{2i}s_{2i+1}) with (a_{i}), then we can change from any permutation to any other permutation of (a). If we want to make (a_{i}) the last element, reverse the ((i+1))-prefix first and reverse the whole string, so (a_{i}) becomes the last element. Then the (n) scale problem is reduced to a (n-1) scale problem.

With the two claims, we can simply compare two strings and get the answer.

TCO13 Round 1A

250

A board with different values ( [0, 9]) in each grid. If we change the value to other value, the cost is the absolute value of the difference. The goal is to change some values of the grids to make the difference of the values no more than 1 and return the minimum cost. And the board is no more than (50 * 50).

It's a simple brute force problem. We can check them with the value pair ( (i, i + 1)), and (i) is in (0) to (8), inclusively, and calculate the cost directly and record the minimum cost.

500

There are (n) segments on a line, which are described as integer pair, and they are not intersect. The line is no more than 30000, the integer pairs are between 0 and the length of the line (D). And we must determine a minimum length of step to start from the origin, without any steps in any segment, eventually ended beyond the end point of the line.

The solution is a little tricky. It based on the observation that if we step across the line with a minimum step length, we must have a stop at some of the right most point of a segment. So the code is very easy to implement. And the complexity of the code is (O(n*n*D)).

1000

Another board problem. A n*n board, each of the grid contains a capital letter which could represent one of four kinds of directions. The directions are up, down, left and right. We can modify some of the grids with a cost one in order to make the board satisfied a property that start from any grid of the board and follow the directions of the grids, we can get back to the start point. If we get out of the board, we follow the direction and go to the opposite edge of the board. We want to know the minimum cost of the modification.

In fact, though this is a 3rd level problem, it still not very hard to solve. Let's take a look at the modified board. In order to satisfy that property, the indegree and the outdegree of every grid must be one. If we represent a grid with two vertices, we call them are A and A', then the next step is to make some arcs. The start vertices of the arcs are the grids' A vertices and the end vertices are the corresponding four adjacent grids' A' vertices. The cost of the arcs are zero if the direction is toward the grid, otherwise, the cost is one. So at last the problem becomes a familiar one which is the Assignment Problem or Maximum Weighted Bipartite Matching. This kind of problem can be solved by Minimum Cost Flow algorithm or Kuhn-Munkres Algorithm.

MathJax公式测试

The Lorenz Equations

[begin{aligned}
dot{x} & = sigma(y-x) \
dot{y} & = rho x - y - xz \
dot{z} & = -beta z + xy
end{aligned} ]

The Cauchy-Schwarz Inequality

[ left( sum_{k=1}^n a_k b_k right)^2 leq left( sum_{k=1}^n a_k^2 right) left( sum_{k=1}^n b_k^2 right) ]

A Cross Product Formula

[mathbf{V}_1 times mathbf{V}_2 = begin{vmatrix}
mathbf{i} & mathbf{j} & mathbf{k} \
frac{partial X}{partial u} & frac{partial Y}{partial u} & 0 \
frac{partial X}{partial v} & frac{partial Y}{partial v} & 0
end{vmatrix} ]

The probability of getting (k) heads when flipping (n) coins is

[P(E) = {n choose k} p^k (1-p)^{ n-k} ]

An Identity of Ramanujan

[ frac{1}{Bigl(sqrt{phi sqrt{5}}-phiBigr) e^{frac25 pi}} =
1+frac{e^{-2pi}} {1+frac{e^{-4pi}} {1+frac{e^{-6pi}}
{1+frac{e^{-8pi}} {1+ldots} } } } ]

A Rogers-Ramanujan Identity

[ 1 + frac{q^2}{(1-q)}+frac{q^6}{(1-q)(1-q^2)}+cdots =
prod_{j=0}^{infty}frac{1}{(1-q^{5j+2})(1-q^{5j+3})},
quadquad text{for $|q|<1$}. ]

Maxwell’s Equations

[ begin{aligned}
nabla times vec{mathbf{B}} -, frac1c, frac{partialvec{mathbf{E}}}{partial t} & = frac{4pi}{c}vec{mathbf{j}} \ nabla cdot vec{mathbf{E}} & = 4 pi rho \
nabla times vec{mathbf{E}}, +, frac1c, frac{partialvec{mathbf{B}}}{partial t} & = vec{mathbf{0}} \
nabla cdot vec{mathbf{B}} & = 0 end{aligned}
]

SRM 559 DIV1

DIV1感觉比DIV2好混啊。。做出250,分数也不咋地,rating居然暴涨161。。

250(DIV2 500)

比赛的时候想到了直接计算的方法。

式子很简单,在纸上画画就推出来了。

但是实际上,这必须是在max(a,b)*2 < min(numRow,numColumn)的时候公式才成立。

否则会有很多特殊情况。

当然我也看漏了条件,当我把a == b的情况写好了才发现不用考虑a == b。

于是本来还可以快一点的。

赛后看了vexorian的blog,他介绍了一种容斥的方法,学习了下,practice的时候写了写,感觉挺好。

不过复杂度是(2^the number of  kinds)^2,运用的时候要注意规模。

500

500没有太多想法,目前的想法是枚举度为1和2的点为根,然后再dfs或者树DP之类的。

900

不会做。。

--------------------------------------------------------------------------------------------------------------------------

DIV2

DIV2也去practice了一下。

250

简单DP一下。

500

同DIV1 250

1000

这次的1000比赛之中无人做出。

看了下题,开头怀疑是插头DP,但是看完shi哥的代码发现他只是做了一些枚举和判断。

暂时留个坑,等题解出来再看看吧。

SRM 558 DIV2

这场由于时间关系没有赶得上。

所以只是practice了一下DIV2,总的来说,这场难度比以往要高,所以很多人都做得不是很好。

250

按题意,一个格子周围都是石头或者本身是石头的时候才算是被控制了。

根据这个直接枚举一下,加加减减就是结果。

开头题意读错了,还好样例比较强,改之交了之后只有200pt。

600

因为分数是600,所以很悲剧啊,弄了半天没弄出来。

结果还是因为题意没明确。

开头以为可以用多种刷子,结果题目的意思就是只能用一种刷子。

这样一来,再加上同一个格子不能被刷两次,题目其实就简单了。

枚举刷子的长度,因为有的格子不确定到底是哪种颜色,所以需要每次dp一下求出最小需要刷的次数。

900

这个900比较水,首先如果没有黑色,那么先手必败。

接下来统计出每个白色段的长度,就相当于取石子游戏了,直接异或就可以得到答案。

交了之后有700+。。无语了。。