- 定义元素类型没有任何构造函数的 vector，标准库将对该对象的每个成员进行值初始化。（Page 80）
- vector 迭代器支持一些算术操作。（Page 87）
- string 对象和 bitset 对象之间是反向转化的。(Page 89)
Related Posts
Posts Tagged ‘C++’
C++ Primer 随记——第 3 章，标准库类型
Thursday, February 5th, 2009Related Posts
C++ Primer 随记——第 2 章，变量和基本类型
Friday, January 23rd, 2009很久很久以前就买了 C++ Primer，但是一直是当工具书来看，现在闲下来了，就拿来仔细看看。
（由于是乱随记，看不懂的就不要看了）
第 1 章，快速入门，没有要记的。
第一部分 基本语言
第 2 章，变量和基本类型
- 表示整数、字符和布尔值的算数类型合称为整型。
- char 是 signed 还是 unsigned 是由编译器确定的。
- signed 类型如何用位来表示是由编译器决定的。
- 8 位 signed 类型的取值至少 -127~127，许多实现允许 -128~127。
- 将超出取值范围的数赋给 signed 类型时的行为是未定义的。
- 将超出取值范围的数赋给 unsigned 类型时，编译器会使用该值对 unsigned 类型的可能取值数目取模，然后将结果赋给该 unsigned 类型。
- 没有 short 类型的字面值常量。
- 默认的浮点字面值常量为 double 类型，在数值后面加 F 或 f 表示单精度，L 或 l 表示扩展精度。
- 字符前面加 L （只能大写）得到 wchar_t 类型的宽字符字面值。
- 字符串前面加 L （只能大写）得到宽字符串字面值。
- 两个相邻的仅由空白字符隔开的字符串字面值（或宽字符串字面值）可以连成一个新字符串字面值。
- 连接字符串字面值和宽字符串字面值的结果是未定义的。（g++ 会输出一个类似内存地址的东西，谁来解释下？）
- C++ 定义了保留了一片关键字和替代名（63 个关键字和 11 个替代名）
- 标识符不能饱含两个连续的下划线，也不能以下划线开头后面紧跟一个大写字母，函数外面定义的标识符还不能以下划线开头。C++ 把他们留给标准库了……
- 在全局作用域里定义的 const 对象默认具有文件作用域，使用 extern 使整个程序可以访问它。（非 const 变量默认为 extern）
- 枚举成员值可以不是惟一的。比如 enum p {p1 = 1, p2 = 1, p3}; 是合法的。
看完这一章，我发现 C++ 里有太多未定义的行为，不要依赖他们。
有一个问题，先看下面这段（在 2.3.1 节）：
C++ programmers tend to be cavalier in their use of the term object. Most generally, an object is a region of memory that has a type. More specifically, evaluating an expression that is an lvalue yields an object.
C++ 程序员经常随意地使用术语对象。一般而言，对象就是内存中具有类型的区域。说得更具体一些，计算左值表达式就会产生对象。
什么叫“计算左值表达式就会产生对象”，计算右值表达式的时候不会产生对象吗？望高人解答。
Tags:C++,C++ PrimerRelated Posts
[OI][Vijos 1107]环游大同 80 天
Sunday, October 26th, 2008话说这题是一个搜索题。
我采用的是两次 DFS 的方法，也就是任意取一个点开始 DFS，找到这次 DFS 时深度最深的点（也就是从所选点开始最长路径的终点），然后从这一点（可以证明，这一点是最长路径的端点）开始再进行 DFS，这次 DFS 的深度就是要求的路径长度。
算法就是这样了，不过这个算法的正确性我一开始也不太确定，下面来证明一下：
大家看图：
设最长路径为 AB ，一开始任选的点为 P。取路径 PB 上的一点 Q，使得 AQ 与 PQ 只有一个公共点 Q（也就是使得从 A 走到 Q 再走到 B 不会走回头路）。设 AQ=a，QB=b，QP=s，不妨设 a<b。
要证明这个算法的正确性，也就是要证明从 P 开始的最长路径的终点一定是 A 或 B。假设从 P 开始的最长路径的终点是 C ，设 CP=c。
由假设知， c>s+b。由于从从 P 开始的最长路径的终点是 C，所以第二次 DFS 将从 C 开始，所得最长路径为 CB=c+s+b>s+b+s+b，又因为 a<b，故CB>s+b+s+b>s+a+s+b>a+b=AB，这与 AB 是最长路径矛盾，故假设不成立，命题得证。
时间复杂度 O(CR)，空间复杂度 O(CR)。
代码还是非常 ugly，偷了很多懒，改一下的话应该能更快些。
P.S. 停止切题，准备期中考试。（其实这个星期就没做题）
Tags:algorithm,C++,OI,VijosRelated Posts
[OI][Vijos 1214]伤心的AsukaNoKaze
Sunday, October 19th, 2008这题算是个数论题。
其实也没用到什么数论结论，首先手算找找规律。发现，对于 ![\forall x\in (\frac{n}{i+1},\frac{n}{i+1}],x\in {\mathbb Z}](/latexrender/pictures/3b76308ef2690611761fd469699d22f5.gif "\forall x\in (\frac{n}{i+1},\frac{n}{i+1}],x\in {\mathbb Z}")
有 
为常数
，于是这一区间内的数就可以只算一次，然后将结果乘以区间内整数的个数就行了。但当
时，每个区间的长度
，这样就得不偿失了，所以当
时每个区间处理一次，当时，进行朴素的计算。
div 运算就这样解决了，剩下的取余可以由整除的结果生成，对于
，有
，每个区间内，
为定值，所以令
，则对于区间![(first,last]](/latexrender/pictures/62645c69df507cb4d61eb94266172dd0.gif "(first,last]")
，有
。同样地，当时，进行朴素的计算。
时间复杂度 
，空间复杂度 O(1)。
算法就是这样了，刚开始写的时候 TLE 了，原因是作为循环条件的 sqrt(n) 没有提前计算出来，于是导致了很多不必要的运算，多么低级的错误……
C++ 代码在这里。
P.S. 突然想做编号是大家生日的题目，这题编号是我一个朋友的生日，自己的生日编号的题目的状态是暂不提供……
Tags:algorithm,C++,OI,VijosRelated Posts
[OI][Vijos 1059]积木城堡
Thursday, October 16th, 2008一年没写代码了，这周又开始拿起我那二把刀，开始切题了……
看到我们的小妹妹写了积木城堡这个题，于是我也从这题开始了……
简单的 0/1 背包，渐进时间复杂度（大概）是 O(N*n*n)，渐进空间复杂度（大概）是 O(N*n*n)，其中 N 为城堡数量， n 为组成每个城堡的积木数。
这题有着 Vijos 的一贯传统，就是题目描述令人 confused，就这题来说，从中间抽取积木还能使城堡不倒，不得不说是有一定功力，抽出的积木就扔在一边，不能不说是浪费。其实这都可以在题目中说清楚的。
开始做，一开始用了 bitset （在 NOIP 中允许使用），结果 TLE ；后来优化了读入，还是 TLE，后来砍掉了 bitset ，用 boolean array，提交无数次后（Vijos 最近服务器有问题，运行程序忽快忽慢，随机 TLE 的现象时有发生），终于 AC 了。
代码可以看这里，其他 vijos 的代码也在那里。
事实证明， bitset 的效率并不高，竞赛的时候应远离 bitset …… （这也可能跟 Vijos 所用编译器的实现有关）
Tags:algorithm,C++,OI,VijosRelated Posts