[c++11]Lambda 表达式

在 C++11 中新增了一个特性 —— Lambda 表达式,它提供了一个简便的方法来创建一个函数对象。

至于函数对象,它的用途通常是在调用标准库算法的时候作为核心部分传入的,比如说 std::sort 默认是从小到大排序,然而如果我们要从大到小排序在 C++ 98/03 中有三种方法

第一种是给 std::sort 一个函数,第二种是给一个函数对象,第三种是用标准库 functional 里面已经定义好了的函数对象

你可能会说,第三种多快多方便,但是,如果比较算法一变得复杂起来,如果标准库没有提供这样的函数对象,那你就不得不选择前两种方法了,肯定,很多人会选择第一种。

但是…… 如果你的比较函数要依赖于一个外部的,比较函数调用之时才确定的,那么第一种就无能为力了,考虑下面这个例子

这种写法无疑会消耗很多时间,增加很多代码量,于是 Lambda 表达式便在 C++11 标准中诞生了。

Lambda 的语法是这样的,首先以 [] 打头,之后是和普通函数一样的参数列表,然后是函数体,如果有返回值(假定为 T),那么在参数列表后加上 -> T,它语法大概就写成这样,最简单的 lambda 表达式就是 []{} 它什么都不做

[ capture ] ( argument-list ) -> return-type { statement }

  • [ capture ]:捕获列表。它总是出现在 lambda 函数开头,并且不能省略,事实上,它是 lambda 函数的引出符。捕获列表可以捕捉上下文中的变量以供 lambda 函数内部使用,具体用法请看下文。
  • ( argument-list ):参数列表。和普通函数参数列表一样,如果没够参数可以连同括号一起省略。
  • mutable:默认情况下 lambda 函数总是 const 函数,也就是说捕获的变量不可修改。mutable 可以取消其常量性,若有这个修饰符,参数列表不可省略。
  • return-type:函数返回类型。详见下文
  • { statement }:函数体。

(more…)

Read More

[c++11]编译期间判断两个类型的实例是否可以应用等于运算符

标题十分地长的样子、还是把以前写在其它地方的东西都搬到这个地方来了

我主要是想有两个类型分别是 A 和 B 的变量 a、b,能否在在编译期间获得一个 bool 常量,表示是否拥有 a == b 这样的运算

然后我们来看看测试的结果

(more…)

Read More

BZOJ-3157. 国王奇遇记

题目大意是要求下面这个式子

 \begin{eqnarray*} \sum_{i=1}^n m^i \cdot i^m \end{eqnarray*}

这个题目有三个版本:

BZOJ-3157 m \leq 200

BZOJ-3516 m \leq 1000

BZOJ-4126 m \leq 500000

这篇文章介绍 \mathcal O(m^2)\mathcal O(m) 两种做法

为了方便,定义一个函数 f(i)

 \begin{eqnarray*} f(i) = \sum_{k=1}^n k^i \cdot m^k \end{eqnarray*}

然后使用“扰动法“

 \begin{eqnarray*} (m - 1) \cdot f(i) & = & \sum_{k=1}^n k^i \cdot m^{k + 1} - \sum_{k=1}^n k^i \cdot m^k \\ & = & \sum_{k=1}^{n + 1} (k - 1)^i \cdot m^k - \sum_{k=1}^n k^i \cdot m^k \\ & = & n^i \cdot m^{n + 1} + \sum_{k=1}^n m^k \sum_{j = 0}^{i - 1} {i \choose j} \cdot (-1)^{i - j} \cdot k^j \\ & = & n^i \cdot m^{n + 1} + \sum_{j = 0}^{i - 1} {i \choose j} \cdot (-1)^{i - j} \sum_{k = 1}^n k^j \cdot m^k \\ & = & n^i \cdot m^{n + 1} + \sum_{j = 0}^{i - 1} {i \choose j} \cdot (-1)^{i - j} \cdot f(j) \\ \end{eqnarray*}

然后这个算法的复杂度是 \mathcal O(m^2) 的,但是这题最快可以做到 \mathcal O(m) 的!

(more…)

Read More

Hello world!

第一次弄了博客感觉真好啊哈哈,虽然只有 100M 网页空间和 20M 数据空间造成了怨念……

我来测一测插件


\cos (\alpha + \beta) = \cos \alpha \cos \beta - \sin \alpha \sin \beta

Read More