SAT / SMT 求解器

本文是个长期的工作,是对 Dennis Yurichev的文章《SAT/SMT by example》的翻译。文本总长460页,二十余章。在翻译的过程中,我会假如我的理解和一些具体的算法。

Read More

c preprocess 预处理

伪指令(或预处理指令)定义:

预处理指令是以#号开头的代码行。#号必须是该行除了任何空白字符外的第一个字符。#后是指令关键字,在关键字和#号之间允许存在任意个数的空白字符。整行语句构成了一条预处理指令,该指令将在编译器进行编译之前对源代码做某些转换。下面是部分预处理指令:

Read More

C++ 命名空间

假设这样一种情况,当一个班上有两个名叫 Zara 的学生时,为了明确区分它们,我们在使用名字之外,不得不使用一些额外的信息,比如他们的家庭住址,或者他们父母的名字等等。

同样的情况也出现在 C++ 应用程序中。例如,可能会写一个名为 xyz() 的函数,在另一个可用的库中也存在一个相同的函数 xyz()。这样,编译器就无法判断所使用的是哪一个 xyz() 函数。

Read More

C 存储类型

C 语言中,static是用于说明变量作用范围的关键字。它的作用有如下的三条

A. static

1. 隐藏

Read More

C++ 文件操作

iostream 标准库,它提供了 cin 和 cout 方法分别用于从标准输入读取流和向标准输出写入流。
如果要从文件读取流和向文件写入流,这就需要用到 C++ 中另一个标准库 fstream,它定义了三个新的数据类型:

  • ofstream 表示输出文件流,用于创建文件并向文件写入信息。

Read More

Manacher 算法

在介绍 Manacher 算法之前,首先介绍一下什么是回文串,所谓回文串,简单来说就是正着读和反着读都是一样的字符串,比如 abba,noon 等等,一个字符串的最长回文子串即为这个字符串的子串中,是回文串的最长的那个。

计算字符串的最长回文字串最简单的算法就是枚举该字符串的每一个子串,并且判断这个子串是否为回文串,这个算法的时间复杂度为 O(n3)O(n^3) 的,显然无法令人满意,稍微优化的一个算法是枚举回文串的中点(把每一个字符当做中心,向两边延伸),这里要分为两种情况,一种是回文串长度是奇数的情况,另一种是回文串长度是偶数的情况,枚举中点再判断是否是回文串,这样能把算法的时间复杂度降为O(n2)O(n^2),但是当 n 比较大的时候仍然无法令人满意,Manacher 算法可以在线性时间复杂度内求出一个字符串的最长回文字串,达到了理论上的下界。

Read More

C++ virtual function

C++的多态(polymorphism)是通过虚函数来实现的。想象一下我们定义一个基类:动物。在基类中,我们给了动物不同的属性和行为。我们可以继承出各种具体的动物,并且继承基类中的属性和行为。但是,特殊的情况是,不同的继承类中,具体的行为是不一样的。由此,在基类中运用虚函数,我们定义一个抽象的行为,行为的实现方式在基类中可以实现,也可以不实现(纯虚函数),在继承类中,需要对抽象的行为具体化,也就是必须给实现方式。

Read More

C 命令行参数

在调用主函数main时,它带有两个参数。第一个参数(习惯上称为argc,用于参数计数)的值表示运行程序行中参数的数目;第二个参数(称为argv,用于参数向量)时一个指向字符串数组的指针,其中每个字符串对应一个参数。

1
2
3
4
int main(int argc, char const *argv[]) {
/* code here*/
return 0;
}

Read More

C++ 动态内存

了解动态内存在 C++ 中是如何工作的是成为一名合格的 C++ 程序员必不可少的。C++ 程序中的内存分为两个部分:

  • 栈:在函数内部声明的所有变量都将占用栈内存。
  • 堆:这是程序中未使用的内存,在程序运行时可用于动态分配内存。

Read More

东南西北

一、东去

这座城市的门窗紧闭,在煮饭的在煮饭,在做爱的在做爱,在猜疑的在猜疑,在逗猫的在逗猫,一切井然有序,没有突如其来的干扰和意外如雷的波动。一到二十区还是那个样子,看似像个少女迷人得要命,但莫名其妙的味道仿佛是个腐朽的老人,带着花枝招展的虚妄,让你嗤之以鼻。夜晚的塞纳河迷迷糊糊,被下了迷魂药,埃菲尔铁塔硬硬得戳起要非礼她,梵高捧着一堆话,说没办法,没办法。

Read More