Snowdream

两场 Luna ZvP 开局都一样，我12D分矿BH，对手2BG xx rush，两局还都是近点。
第一局show了一下农民卡位，貌似这个因为玩了魔兽提高了不少，愣是把P的第一个狂热卡了好几下，等它到我的分矿6条小狗已经出来了。之后是小狗show，纯小狗一只没死先后杀死6狂热，我都怀疑这是不是自己的操作了，然后就是纯A了。。。
第二局没第一局好玩，近点xx rush防住后骗对方升级基地，然后爆狗A掉了

一开始没看清题目，以为是在网状图中找遍历所有点的最短路径
后来才发现是在一棵树中，而且是从根节点出发，这个就简单多了
把所有路径加起来乘以2，就是从根节点到各个路径后再返回根节点所需的最短耗费。
然后再减掉访问最后一个节点后返回所需的耗费即可，既然要求最小的耗费就减去耗费最大的路径即可。

 1. File hole
The file's offset can be greater than the file's current size, in which case the next write to the file will extend the file. This is referred to as creating a hole in a file and is allowed. Any bytes in a file that not been written are read back as 0.
A hole in a file isn't required to have storage backing it on disk. Depending on the file system implementation, when you write after seeking past the end of the file, new disk blocks might be allocated to store the data, but there's no need to allocate disk blocks for the data between the old end of file and t he location where you start writing.

2. read Function
#include <unistd.h>
ssize_t read(int filedes, void *buf, size_t nbytes);
// Returns: number of bytes read, 0 if end of file, -1 on error
read读取的字节数小于所要求的字节数的几种可能：
1) 从文件中读取，在所要求的字节数读取完成前到达文件尾。
2) 从终端读取，这种情况下通常每次最多读取一行内容。
3) 通过网络读取，网络缓冲可能导致读取到少于要求的字节数。
4) 从管道或者FIFO中读取
5) 从record-oriented设备中读取，如磁带，每次至多返回一个记录。orz...
6) 在一定数量的数据读取后被信号中断。

3. write Function
#include <unistd.h>
ssize_t write(int filedes, const void *buf, size_t nbytes);
// Returns: number of bytes written if OK, -1 on error
导致错误的通常原因是磁盘已满，或者超出了给定进程的文件大小限制。

PS: 看了IEF2007 ipx vs pj, ipx vs lx的四场ZvP，ipx和他们的差距自然很大，细节上lx比pj强不少，包括小狗进入矿区时农民的控制，开局的计算等。推荐ipx vs pj中Luna上的一场，局面一边倒，ipx充分展示了ZvP的关键——灵活，打得很妖。

1. 任何存储字符串size()方法返回的结果的变量必须为string::size_type类型。特别重要的是，不要把size的返回结果赋给一个int变量。string::size_type是一个unsigned型。
同样，在定义用作索引的变量时，最好也用string::size_type类型。

2. vector::const_iterator() 返回只读迭代器。

3.
typedef string *pstring;
const pstring cstr;
等价于string *const cstr;
而不是const string *cstr;
也可以写成pstring const str;
但是大多数人习惯把const写在类型的前面，尽管这种情况把const放在类型后面更容易理解。

 

把以前跳过去的几节补一下

对齐就是指为了提高处理器的效率，把某些基础类型的地址规定为必须是某个值(通常是2,4或8）的整数倍。
如果不这样处理，例如把一个double值分开存放在地址为8*n的两边，处理器每次从内存中读取8字节，这样就需要读取两次才能得到这个double值了。
Linux的做法是把2字节数据（如short）存放在偶数的地址中，把其他更大的数据（int, int *, float, double）放在以4为约数的地址中。
Windows则使用了相对现代的处理器而言更好的做法，任何k字节的数据必须存放在以k的倍数为起始的地址中，即double必须存放在以8*n为起始的地址中。
GCC的编译开关-malign-double也可以达到这种效果，但因此可能导致与某些假定4字节对齐方式的库的链接错误。
一个简单的例子：
struct S1 {
    int i;
    char c;
    int j;
};
对齐后的保存方式为
0-4: i
4-5: c
8-12: j

1. unbuffered IO是相对于standard IO而言的，unbuffered指每个read和write函数都是通过内核系统调用实现的。这些函数并不是ISO C的一部分，但都属于POSIX.1和Single UNIX Specification.

2. File Descriptors
内 核中所有打开的文件都是通过File Descriptor指向的。file descriptor是一个非负的整数，按照管理，UNIX系统把0指定为进程的标准输入，1为进程的标准输出，2为标准错误输出。为了程序的通用性考 虑，这些magic number应该由<unistd.h>中的STDIN_FILENO, STDOUT_FILENO, STRERR_FILENO代替。
file descriptor的范围是从[0, OPEN_MAX]，早期系统的上限为19，现在许多已经到达了63，Linux 2.4.22把每个进程打开的文件数上限提升到了2^20.

3. open 函数
#include <fcntl.h>
int open(const char *pathname, int oflag, ..., /* mode_t mode */ );
返回: 正常 - 最小的未被使用的file descriptor，出错 - 0
oflag: O_RDONLY(0), O_WRONLY(1), O_RDWR(2) 括号内为大多数情况下的值，这三个参数中必选一个，剩下的可选参数指定了是否追加、是否创建等信息，具体参见man 2 open

4. File Name and Pathname Truncation
如果创建的文件名长度大于NAME_MAX常量，BSD系统会返回一个错误状态，并把errno设为ENAMETOOLONG。如果只是把文件名截去部分就有可能导致与已存在的文件重名。
POSIX.1中的常量_POSIX_NO_TRUNC指定了长文件名和路径会被截断还是会引发错误

5.  创建文件
#include <fcntl.h>
int creat(const char *pathname, mode_t mode);
事实上这个函数等价于
open (pathname, O_WRONLY | O_CREAT | O_TRUNC, mode);

6. 关闭文件
#include <fcntl.h>
int close(int filedes);
返回: 成功 -1，出错 0
当一个进程结束时，系统会自动关闭该进程打开的所有文件。

7. lseek 函数
每个打开的文件都有一个current file offset属性，通常是一个非负的整数。默认情况下文件打开后该值为0,除非指定了O_APPEND选项。
#include <unistd.h>
off_t lseek(int filedes, off_t offset, int whence);
// Returns: new file offset if OK, -1 on error

可以通过seek 0字节来得到当前的offset
off_t currpos;
currpos = lseek(fd, 0, SEEK_CUR);
这个方法也可以用来判断当前文件是否可以被seek，如果是指向管道(pipe)，FIFO，或者socket的file descriptor，lseek把errno设置为ESPIPE并返回-1

某些设备可能允许负值的offset(如FreeBSD上的/dev/kmem)，因此在检查返回值时应判断是否等于-1，而不是是否小于0

水木上看到的，
while (i != i) {}
问如何给i赋值使程序进入死循环

一种正确答案是
当i为浮点类型，且值为NAN时
例如
float i = -1;
i = sqrt(i);

1. 静态库(static library)的主要缺陷：
1) 静态库通常需要维护和定期更新，而这些库的使用者就得注意这些变化，并且在库修改后重新将自己的程序和库链接起来
2) 以printf和scanf这两个函数为例，它们的代码在每个运行的进程里都保留了一份，在一个典型的操作系统上运行着50-100个进程，这无疑是对系统资源的严重浪费。（内存的一个有趣的特性是，它永远是一个短缺的资源，无关一个系统里有多大的内存）

2. 共享库(shared library)弥补了静态库的这些缺陷。所谓共享库，就是指在运行时可以被读入到任意的内存地址，并与程序链接的模块。这个过程也被称为动态链接(dynamic linking)，由动态链接器(dynamic linker)完成。
Unix系统中共享对象通常后缀为.so，微软的操作系统中大量使用了共享库，通常被称为DLL(dynamic link libraries)

3. 共享库的“共享”表现在两个方面：
1) 在任何一个给定的文件系统中，对于某个特定的库，只有一个.so文件
2) 共享库单独的一份.text域可以由多个不同的运行进程共享。

4. 编译一个共享库：gcc -shared -fPIC -o libvector.so addvec.c multvec.c
-fPIC开关让编译器产生位置独立的代码(PIC, position independent code)
-shared开关使得编译器产生共享对象的文件

5. 动态链接的几个应用：
1) 软件的分布式开发
2) 开发高效的Web服务器
早期的Web服务器通过fork和execve调用子进程来产生动态的内容，被称为CGI，而现代的Web服务器则通过基于动态链接库的一种高效的方式。
主要的方法是把生成动态内容的函数打包到一个共享库中，当服务器端接收到一个请求后，服务器动态地读入并且链接到相应的函数，并直接调用这个函数，而 fork和execve则是在子进程的环境中运行的。函数调用后继续存在，以后的类似请求都只需要一个简单的调用就可以了。另外，方法也可以在不停止服务 器的情况下更新，也可以加入新的函数。

6. Unix系统中读入并链接共享库的方法
#include <dlfcn.h>
void *dlopen(const char *filename, int flag);
// returns: ptr to handle if OK, NULL on error
需要通过-rdynamic编译，具体见CSAPP P569

获得已经打开的库的句柄(handle)
#include <dlfcn.h>
void #dlsym(void *handle, char *symbol);
// returns: ptr to symbol if OK, NULL on error

关闭共享库
#include <dlfcn.h>
int dlclose(void *handle);
// returns: 0 if OK, -1 on error

获得错误信息
#include <dlfcn.h>
const char *dlerror(void);

1. 一个有限非空集合M到自身的一个双射称为置换。
若M的元素个数为n，记M的所有置换的集合记作S_n，则不难得出S_n的元素个数为n个元素的排列数，即
| S_n | = n!

2. Sn的一个把i₁变到i₂，i₂变到i₃，……，i_k-1变到i_k，i_k变到i₁，而其余的元（如果还有）不变的置换称为k阶循环置换
如
(1 2 3 4 5 6)  =  (1) = (2) = ... = (6)，称为恒等置换
 1 2 3 4 5 6

3.几个定理：
1) 设f，g为两个不相交的循环置换，则fg = gf
2) 任意置换均可唯一地分解成不相交循环置换的乘积
这个定理可由构造法证得，该证法同时也给出了分解为循环置换的乘积的方法
3) 任意置换均可分解为对换的乘积（不唯一），例如
(12)(345) = (12)(35)(34) = (12)(14)(41)(35)(34)

4. 置换的奇偶性
1) 设f ∈Sn，规定f的符号为
Sgn f = ∏[ f(i) - f(j) ] / (i - j)
貌似就是逆序对数的奇偶性，奇为-1，偶为1
2) Sgn(fg) = (Sgn f)(Sgn g)
3) n > 1时，Sn中奇置换与偶置换的个数相等，均为n! / 2
可通过分离一组对换积证得

1. The following Vim command will perform a fast code block formatting:
1G=G
We can split it up in simply says:
1G : Go to the first line(you can also use gg)
= : Indent according to the configuration
G : Go to the last line(tell Vim where to end indenting)

2. Another way is to go into visual mode with V and press =  to reindent the chosen lines.

3.
=i{ will reindent everything between { and } excluding the brackets.
other similar choices:
a{ : all the code between { and } including the brackets.
i(, a(, i<, a<, i[, a[