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[