乱八七糟的代码

Basic Sample Senario :

Client 需要一种组件提供一种 FastString类， 此类具有 int length() 方法

解决方案：

静态链接 ： 组件厂商将源代码交给 client ，客户将组件代码与client 代码编译连接运行。 如果组件代码需要fix bug or update ，则client 端代码需要重新编译连接。 而且client软件的不同实例使用各自的组件内存对象。

动态链接 ： 组件厂商使用DLL形式发放组件，此时不同的client实例可以共享组件在内存中的代码段。

DLL的问题：1.导出名称的问题 ： 不同的compiler可以使用不同的mangle name 用来区分 c++的函数，那么使用不同的compiler的client和组件无法链接 （可以使用extern “C”解决全局函数名的问题，使用 .DEF文件解决导出成员函数的问题）

                   2.升级的问题 ：如果组件最初定义为

class FastString
{
    char* m_psz;
public:
    FastString(const char* psz){strcpy(m_psz, psz);}
};

                                          而后厂商更改了组件的实现

class FastString
{
int newmember;
char* psz;
public:

FastString(const char* psz){strcpy(m_psz, psz);}

}

原来FastString对象大小为4字节，现在变为8字节，但是client端按照4字节分配对象， dll却要向后面的4个字节存入一个指针，行为不可预料！

解决这一问题的一种方法便是每次发布便更改dll的名字，即1.0, 2.0, x.0 等等。但这样比较弱啊！！

这种问题根本原因是啥呢？

class 的关键在于封装了其中的实现细节，即用户知道类提供了哪些服务（ public方法）就行了，不需要管类的内部到底使用了哪些成员变量。这样一来，只要接口没变（类提供功能），user就可以安心的使用任意版本的实现了。C++怎么不行呢？C++告诉用户接口的同时，也告诉了用户类的实现(对象布局)。比如类对象有多大啊，每个成员的偏移啊(具体可以看Inside c++ object model)。知道了这些，客户端使用接口的代码就和DLL中的具体实现紧密的耦合起来了，杯具 啊~

咋办呢？ 只要不让client直接创建FastString就行了，这样client的代码就不会受到FastString实现变化的影响了。给FastString加一个Wrapper类，内部嵌套一个FastString，所有对FastString的调用都foward给内部的FastString member, 创建FastString 的任务在dll方面完成，client只知道Wrapper大小为4个字节--指向FastString的指针。这样问题解决了，但是太麻烦了，所有的接口都要包一层!! 而且多了一层调用!

还有啥办法么？ 为了保证c++接口类实现二进制级别的兼容只能使用编译器无关的特性：1.假设复合类型表现形式相同(struct) 2. 传参顺序相同，可以使用指示符指定3.虚函数调用机制相同，即基于 vtbl 和 vptr. 基于这些假设，我们创建的c++接口类所有函数设置为虚函数，那么不同compiler将为客户端方法调用产生相同的机器代码。定义了接口，便规定了所有继承于他的类的内存结构一定与它兼容。但此时不能告诉用户类的定义，否则重回上面的老路上了。怎么办，只有接口客户无法创建类的定义，只有export一个创建类对象的函数客户了。  同上面的wrapper一样，创建类的操作仅仅在dll内部调用，这意味着实际建造类对象大小和布局的代码与编译实现类的方法的代码使用同样的编译器创建 （即ctor和call ctor的代码由同一编译器同时编译）。由于虚析构函数在vtbl的位置与compiler相关，所以不能把它设置为虚函数，只有显示增加一个Delete函数完成析构工作。

OK，当前我们得到的DLL中只有创建类对象的函数需要用extern “C”export 给客户，其他的接口中的虚函数是通过虚表访问的，无需靠符号名字链接。

进一步的，如果我们要给接口增加一个功能呢？ 如果直接在现有接口中方法声明后加入新的方法，那么此方法会出现在vtbl的最后一栏，旧的client不会调用新方法，但是如果新的client访问老的对象呢? 不幸的事情发生了！ 这样做的问题在于，修改公开的接口就打破了对象的封装性。

那么增加接口功能只能通过设计一个接口继承另一个接口，或者让类继承多个接口来实现了。客户可以在运行时通过RTTI来询问对象，支持这个功能不，亲？然而 ，RTTI也是一个compiler相关的东东，好吧，我们让每个类自己实现RTTI，也就是实现一个dynamic_cast 方法， 用来将自己cast成为自己实现的接口，如果不支持则返回 0 。

例如：

void* CFastString::Dynamic_Cast(const char* pszTypename)
{
void * pRev;
if(strcmp(pszTypename, "IFastString") == 0)
{
pRev = static_cast<IFastString*>(this);
}
else if(strcmp(pszTypename , "IOut") == 0)
{
pRev = static_cast<IOut*>(this);
}
else if(strcmp(pszTypename , "IExtent") == 0)
{
pRev = static_cast<IFastString*>(this);
}
else
{
return 0;
}

return pRev;
}

注意cast到IExtent的时候用了IFastString，因为IFastString 和 IOut都是从IExtent继承的，写IExtent的话不知道用哪个，用虚拟继承可以使CFastString对象只有一份IExtent，为啥不用呢？ 你懂得。。。跟前面答案一样，编译器相关。

最后一个问题是delete的问题，用户需要记得为每一个对象调用一次delete方法，而指针cast来cast去，想记得对象被delete没有很难啊！ 怎么办？ 用引用计数吧，把每个指针当做具有生命周期的实体，创建时候计数++，销毁时候--，等到0的时候就delete对象。

大功告成，通过vptr和vtbl的二进制防火墙，我们做到了可重用的二进制组件，组件变化客户无需重新编译 。

什么时候用memory-mapped files:

1.System use it to load and execute .exe and dll files.

2.Use memory-mapped files to access a data file on disk.

3.allow multiple processes running on the same machine to share data with each other.

------------------------------------------------------------------------------------------------------

用途一：使用mapping file executables and dlls

当调用createProcess时候，系统做了以下的事情:

1.locates CreateProcess 中指定的the .exe file，失败则return false

2.创建新的process kernel object

3.creates a private address space for new process

4.reserves a region of address space large enough to contain the .exe file.The desired location of this region is specified by the .exe file itself.by default ,base address is 0x00400000 .You can change it by create your app .exe fiel using linker’s /BASE option.

5.the systems notes that the physical storage baking the reserved region is in the .exe file on disk instread of the system’s paging file.(系统注意到，支持已保留区域的物理存储区域是在磁盘上的.exe 文件而不是在系统页面中)

当。exe 被mapped into the process address space，系统访问.exe的一个区域，那里列出了.exe含有的dll，然后系统利用 LoadLibrary for each dlls。系统map dll时候，如果dll的 preferred base address 被占据或者不够大，dllwill try to find another region of address space to reserve for the dll。如果dll 被设定了/Fixed when it build,也就是不支持重定位，那么加载失败。

如果加载dll或者exe 失败，弹出对话框并且释放申请的地址空间。

after all .exe  dll mapped into the process address space, system can begin exec the .exe file starup code. the sys takes care of all paging,buffering, and caching. 例如，如果一段代码访问了一个并不在主存的地址，那么一个错误产生，系统察觉到错误并且自动的调入page of code from the files image into a page of RAM。

the sys maps the page of ram to the proper location in the process address and allows the thread  to continue.

当为一个app创建第二个实例时，系统只是简单的打开另外一个memory-mapped view  of file-mapping object that identifies the exec files image and create a new process object and a new thread object.利用内存映射文件，多个实例可以共享代码和数据。实际上，file 是分为多个section ，多个节均对齐于页边界。如果一个instance of the app 修改了全局变量，系统应用了copy-on-write 机制，复制修改的页面，并更新实例的file-mapping view。当我们调试程序时同样的事情会发生，debuger modify code，sys use cow again。

当一个进程被加载，系统检查其所有映射文件页,系统将所有通常用cow保护的页面提交给存储系统，这些页面仅仅是被提交，当文件被访问的时候，系统读入相应的页面，如果页面没有被修改，那么他们可以被换出，如果已经修改，系统将修改过的页面转入已经提交的页面之一(这点很晦涩啊 system swaps the modified page to one of the perviously committed pages in the paging file ,怎么翻译呢~~~~ ：（   )

------------------------------------------------------------------------------------------------------

在可执行文件或者dll中共享静态变量

------------------------------------------------------------------------------------------------------

内存映射数据文件

例子：要把一个文件所有字节倒置

如果利用file mapping 我们告诉系统使用一个虚拟空间的区域来倒置文件，然后告诉把文件的第一个字节映射到保留空间的第一个字节，然后就像处理内存中的字符串一样处理文件即可，引文系统会帮助你完成文件缓存以及调页等工作。

使用流程：

1.创建一个file kernel object that identifies the file on disk that you want to use as a memory –mapped file

2.创建一个file mapping kernel object 告诉系统文件的大小，以及你准备如何访问文件

3.告诉系统map all或者部分文件到你的进程地址空间

当使用结束后要：

1告诉系统 unmap file-mapping kernel object form your process add

2cloes filemapping kernel object

3close file kernel object

---------

具体步骤

--1. 创建文件内核对象

CreateFile

失败返回 INVALID_HANDLE_VALUE = –1 一般来说windows func 失败return null这个比较特殊

createfile dwdesiredAccess 需要设置为 GENERIC_READ 或者 GENERIC_WRITE 

--2. 创建file-mapping 内核对象

CreatefileMapping(HANDLE,PSECURITY_ATTRIBUTES,DWORD fdwProtect,DWORD dwMaximumsizeHigh,DWORD dwMaximumSizeLow,PCTSTR pszName);

第一个参数使用createfile 返回的handle。psa一般使用默认null。当创建一个file mapping object 时候，系统并不会 马上保留一个地址空间，然后将file映射到这个区域。但很i，当系统map时候，系统必须知道为physical storage分配什么样的保护属性，第三个参数指明了这些。

后面两个参数指明file的大小，ensure  enouth physical storage is available for the file-mapping object.

high指明高32位，low指明低32位。如果想创建一个反应现在文件大小的map，均传0.

pszName 用于与其它进程共享内存映射文件

--3.将文件数据map to process address space

使用这个函数

PVOID MapViewOfFile(HANDLE hfileMappingObject,dwDesireaccess,dwFileOffsetHigh,dwFileOffsetLow,dwNumberOfbytestomap)

文件没必要一次全映射，一次映射一部分，这一部分成为一个view

首先通过high和low 指定开始映射的字节

其次是指定映射多大，0则映射到文件尾部。

--4.unmapping the file data from the process address space

UnmapviewOfFile(PVOID pvBaseAdddress);

参数使用mapview的返回值

如果强制write back to disk 则使用 FlushViewOfFile(PVOID pvAddress,SIZE_T dwNumberOfBytesToFlush)

第一个地址是想要开始flush的地址

--5.关闭filemapping object 以及file object

-----------------------------------------------------------------------------------

使用filemap 在进程之间共享数据

例子：

app开始时候，系统调用createfile to open .exe file onthe disk。sys call creatFileMapping to create filemapping object.然后系统调用  mapviewofffileEX (with sec_image flag to point out it is a pe file),So that the file’s image is mapped to the address of the first byte of exectuable code of this mapped view. System creates the primary thread , puts the address of the first byte of exec code of this mapped view in the thread instruction pointer,and then lets the cpu start exec the code.

If user 再启动同一个app，sys 看到file-mapping已经存在了，系统maps a view of file a second time，this time in the context of the newly created process address space.

像所有内核对象一样，有三种方法共享他，继承，命名对象以及赋值handle。

···页文件支持的内存映射文件

许多应用程序运行是产生数据需要和其他进程共享如果必须在硬盘建立文件才可以共享，那么效率很低。因此微软提供了由system paging file 支持的 file mapping。不需要createfile ，只需要在调用createFilemapping 的时候传进一个 INVALID_HANDLE_VALUE 作为hFile 参数即可。 映射文件大小同样是由high 和low 参数决定的。

`````稀疏提交的内存映射文件

--看来需要把虚拟内存那章一起看看了~~~~

A 简单的模拟 ,不过我写的很麻烦

Problem

On Unix computers, data is stored in directories. There is one root directory, and this might have several directories contained inside of it, each with different names. These directories might have even more directories contained inside of them, and so on.

A directory is uniquely identified by its name and its parent directory (the directory it is directly contained in). This is usually encoded in a path, which consists of several parts each preceded by a forward slash ('/'). The final part is the name of the directory, and everything else gives the path of its parent directory. For example, consider the path:

/home/gcj/finals

To create a directory, you can use the mkdir command. You specify a path, and thenmkdir will create the directory described by that path, but only if the parent directory already exists. For example, if you wanted to create the "/home/gcj/finals" and "/home/gcj/quals" directories from scratch, you would need four commands:

mkdir /home
mkdir /home/gcj
mkdir /home/gcj/finals
mkdir /home/gcj/quals

Given the full set of directories already existing on your computer, and a set of new directories you want to create if they do not already exist, how many mkdir commands do you need to use?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing two integers N and M, separated by a space.

The next N lines each give the path of one directory that already exists on your computer. This list will include every directory already on your computer other than the root directory. (The root directory is on every computer, so there is no need to list it explicitly.)

The next M lines each give the path of one directory that you want to create.

Each of the paths in the input is formatted as in the problem statement above. Specifically, a path consists of one or more lower-case alpha-numeric strings (i.e., strings containing only the symbols 'a'-'z' and '0'-'9'), each preceded by a single forward slash. These alpha-numeric strings are never empty.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of mkdir you need.

Limits

1 ≤ T ≤ 100.
No path will have more than 100 characters in it.
No path will appear twice in the list of directories already on your computer, or in the list of directories you wish to create. A path may appear once in both lists however. (See example case #2 below).
If a directory is listed as being on your computer, then its parent directory will also be listed, unless the parent is the root directory.
The input file will be no longer than 100,000 bytes in total.

Small dataset

0 ≤ N ≤ 10.
1 ≤ M ≤ 10.

Large dataset

0 ≤ N ≤ 100.
1 ≤ M ≤ 100.

Sample

Input
Output

3
0 2
/home/gcj/finals
/home/gcj/quals
2 1
/chicken
/chicken/egg
/chicken
1 3
/a
/a/b
/a/c
/b/b

Gluk的解法:

 set <string> S;
        REP (i, n)
        {
            string s;
            cin >> s;
            S.insert(s);//已有的路径用set表示
        }

        int res =0 ;

        REP (i, m)
        {
            string s;
            cin >> s;
            vector <string> ss;
            REP (j, s.size())
                if(s[j] == '/')
                    s[j] = ' ';//用空格替换’/’，然后使用istringstream分隔各级目录
            istringstream iss (s);
            while (iss >> s) {
                ss.pb (s);
            }

            s = "";
            REP (i, ss.size ())
            {
                s = s+"/"+ss[i];
                if (S.find(s) == S.end())//依次加入各级目录，/a  /a/b  /a/b/c 增加递增的所有目录
                {
                    res ++;
                    S.insert(s);
                }
            }
        }

题目中的这一句

If a directory is listed as being on your computer, then its parent directory will also be listed, unless the parent is the root directory.

告诉我们如果/a/b被list存在，那么/a也一定被list出来了 ，所以上面代码可以不去分隔处理已经给出的目录

yuhch123的解法

struct node {
   map <string, node *> sons;//每个节点，用map实现儿子节点
};
node *root;//一个根节点
int T;
int N, M;
char tmp[100005];
int ans = 0;
void insert(node *cnt, char *tmp) {//在节点cnt处，插入tmp子树
   int i;
   if (tmp[0] == 0)//为空则返回
      return;
   assert(tmp[0] == '/');
   string str;
   for (i = 1; tmp[i] != '/' && tmp[i] != 0; i ++)//第一层
      str += tmp[i];
   if (cnt -> sons.find(str) == cnt -> sons.end()) {//如果没有这子树，则创建子树
      ans ++;//需要一次mkdir 
      struct node *tmp2 = new node();
      cnt -> sons[str] = tmp2;
   }
   insert(cnt -> sons[str], tmp + i);// 递归创建子树
}
int main() {
   int i;
   int Case = 1;
   scanf("%d", &T);
   while (T --) {
      scanf("%d%d", &N, &M);
      root = new node();
      for (i = 0; i < N; i ++) {
     scanf("%s", tmp);
     insert(root, tmp);
      }
      ans = 0;
      for (i = 0; i < M; i ++) {
     scanf("%s", tmp);
     insert(root, tmp);
      }
      printf("Case #%d: %d\n", Case ++, ans);
   }
   return 0;
}

neal.wu的解法

vector <string> parse (string s)
{
    vector <string> v;
    string next = "";
    
    for (int i = 0; i < (int) s.length (); i++)
    {
        next += s [i];
        
        if (i + 1 == (int) s.length () || s [i + 1] == '/')
        {
            v.push_back (next);
            next = "";
        }
    }
    
    return v;
}

set <string> direc;

int insert (vector <string> v)
{
    int count = 0;
    string s = "";
    
    for (int i = 0; i < (int) v.size (); i++)
    {
        s += v [i];
        count += direc.insert (s).second ? 1 : 0; //set返回一个pair<iterator,bool> bool指示插入是否成功   

 }
    
    return count;
}

int main ()
{
             freopen("d:\\input.txt","r",stdin);
  
    for (scanf ("%d", &T); TC <= T; TC++)
    {
        scanf ("%d %d", &N, &M);
        direc.clear ();
        int make = 0;
        char str [1000];
        
        for (int i = 0; i < N; i++)
        {
            do gets (str); while (strlen (str) == 0);//do gets 过滤回车空字符串
            insert (parse (str));
        }
        
        for (int i = 0; i < M; i++)
        {
            do gets (str); while (strlen (str) == 0);
            make += insert (parse (str));
        }
        
        printf ("Case #%d: %d\n", TC, make);
    }
    
    //system ("pause");
    return 0;
}

ploh的解法:

int main(void)
{freopen("d:\\input.txt","r",stdin);
  int T; cin >> T;
  for (int t = 1; t <= T; t++) {
    int ans = 0;
    set <string> have, want;
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
      string path; cin >> path;
      have.insert(path);
    }
    for (int i = 0; i < M; i++) {//用一个set保存所有需要加入的
      string path; cin >> path;
      want.insert(path);
      for (int j = 1; j < path.length(); j++)
    if (path[j] == '/')
      want.insert(path.substr(0, j));
    }
    for (set <string>::iterator it = want.begin(); it != want.end(); it++)//遍历所有需要加入的，然后看是否存在
      if (!have.count(*it))
    ans++;
    printf("Case #%d: %d\n", t, ans);
  }
}

这学期也开始了好久，总结下。

项目上：基本弄完了码头，算是结束了吧，剩下的工作是好好总结下学到的东西，把架构，用到的技术都理顺了，方便之后面试回答。

生活上：这半个月gf生病了，嘉定闵行两头跑果然很累，不过还好一直抽空看书。健康很重要~~ 要抓紧锻炼身体了。本钱一定要掌握好。

找实习：先后笔试了摩根it和微软。上周摩根给了电面，全英文的。完全没有思想准备的我正在在闵行gf那里照顾她，手边什么书也没有，项目资料也没有，我的处女面就这样“裸着”度过了，到现在还没有消息，也不知道是不是默剧了。 微软是上周六笔试的，也没有消息，sigh~不知道是没改完卷子还是杯具了~~

关于实习的笔试和面试要专门写东西总结一下，方便以后查阅。

1-4号放假，应该不会有新的安排进来（面试之类的），得安排下事情

上周把大话设计模式翻了一遍，利用这几天要仔细的重新过一遍，每一个模式都写代码实践一下。

然后想看看c++标准文档，这个会很慢，可以选择性的跳过一些东西，总共700多页，看前300页就可以了，后面是介绍库的。一天看75页，恩 ···比较困难·· 尽力吧

其他的就不安排了，也做不完的。

另外，之后学的东西，一定要及时用日志记下来，否则时间长了还要从头学起`````

良好的编程风格是：new和delete 配套使用，即如果使用new [] 则使用delete []

事实上，如果我们使用的是自定义类型int char等，或者我们使用的是没有内存申请的类，我们使用 delete A;并不会发生什么不好的事情。

这是由delete 的语义决定的。当我们是申请一组对象时候，编译器会加入内存大小信息和此段内存相关联。因此当我们delte A 时，编译器会按照内存大小收回分给我们的内存。显然，如果是基本类型或者没有申请内存的情况这样的行为是良好的。但是如果我们在自建类型中申请了内存~对不起，编译器是不知道的，这些申请的内存就是内存泄露，随着程序不断进行，堆不断地被侵蚀·····

这就是delete的第二个作用，他会施加析构函数在我们申请的内存上，如果我们delete A，只会在第一个上施加，而如果delete [] A;他会对数组中每一个元素进行析构~~

so····

试验很容易做，写两个类，一个申请内存，一个普通的类，然后循环申请大量数组，但是用 delete A 形式，然后看看内存占用就行了

数据对齐：是指数据所在的内存地址必须是该数据长度的整数倍。处理器可以直接访问对齐的数据，而访问未对齐的数据会在内部进行一系列的调整，虽然可以正常处理，但是会降低运行速度。例如一个处理器总线宽度为64位，那么地址必须为8的倍数，也就是一次取出8个字节。如果我们可以保证所有double地址都为8的倍数，那么可以用一个存储器操作来读或者写double了，否则我们可能需要执行两次存储器访问，因为对象可能位于两个8字节存储器块中

对于结构体也是一样的例如 struct s2{int i;int j;char c;}; 如果我们把这个结构打包成9个字节，只要保证起始地址满足4的对齐要求我们就可以保证i j的对齐，不过如果我们声明了一个数组，那么元素地址成为 xd,xd+9,xd+18,xd+27 不满足对齐了。因此我们呢要分配12个字节给这个结构体

更进一步 ：

未对齐的数据会以不同方式给cpu带来麻烦~

1.如果一个变量被划分到两个缓存行，那么我们需要访问两个缓存行才可以。

2.一些simd指令总是要求对齐的指令，对于未对齐的指令，数据对齐也会影响这些指令的使用。

Drainage Ditches
Hal Burch

Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.

Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network. Note however, that there can be more than one ditch between two intersections.

Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.

PROGRAM NAME: ditch

INPUT FORMAT

Line 1:
Two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream.

Line 2..N+1:
Each of N lines contains three integers, S<sub>i</sub>, E<sub>i</sub>, and C<sub>i</sub>. S<sub>i</sub> and E<sub>i</sub> (1 <= S<sub>i</sub>, E<sub>i</sub> <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from S<sub>i</sub> to E<sub>i</sub>. C<sub>i</sub> (0 <= C<sub>i</sub> <= 10,000,000) is the maximum rate at which water will flow through the ditch.

SAMPLE INPUT (file ditch.in)

5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

OUTPUT FORMAT

One line with a single integer, the maximum rate at which water may emptied from the pond.

SAMPLE OUTPUT (file ditch.out)

50

最基本的网络流

   1:  #include<iostream>

   2:  #include<fstream>

   3:  #include<string>

   4:  #include<vector>

   5:  #include<map>

   6:  #include<algorithm>

   7:  #include<sstream>

   8:  #include <cstring>

   9:  #include <queue>

  10:  using namespace std;

  11:  const int MAXN = 220;

  12:  const int infi = 0x7FFFFFFF;

  13:   int capacity[MAXN][MAXN], prenode[MAXN], flow[MAXN];

  14:   queue<int> mq; 

  15:   

  16:  int start, end, N;

  17:  void init(){

  18:      freopen("ditch.in","r",stdin);

  19:      //freopen("e:\\usaco\\ditch.in","r",stdin);

  20:      start = 1;  

  21:      scanf("%d %d",&N,&end); int c, s, t;

  22:      memset(capacity,0,sizeof(capacity));

  23:      for(int i=0;i<N;i++)

  24:      {

  25:          scanf("%d %d %d",&c,&s,&t);

  26:          capacity[c][s] += t; //两个节点间不只有一条路

  27:      } 

  28:  }

  29:  int bfs(){//寻找增广路径

  30:      while(!mq.empty()) mq.pop(); 

  31:      mq.push(start);  //源节点入队

  32:      //memset(flow,0,sizeof(flow));

  33:      memset(prenode,-1,sizeof(prenode)); //重置前向节点

  34:      prenode[start] = 0; flow[start]=infi; //源节点流量无限大

  35:      while(!mq.empty()){

  36:          int cur = mq.front(); 

  37:          mq.pop();

  38:          if(cur == end) break; //到达汇点结束路径 

  39:          for(int i=1;i<=end;i++){ 

  40:              if(prenode[i]==-1 && capacity[cur][i]) //访问当前节点所有未访问的相邻节点，更新flow

  41:              {

  42:                  prenode[i] = cur;

  43:                  flow[i] = (flow[cur]<capacity[cur][i]?flow[cur]:capacity[cur][i]);

  44:                  mq.push(i);

  45:              }

  46:          }

  47:      }

  48:      if(prenode[end]==-1)  //如果未找到增广路径返回-1

  49:          return -1;

  50:      return flow[end];

  51:  }

  52:  int Edmonds_Karp(){

  53:      int total = 0, pathcapacity;//pathcapacity 路径增加量

  54:      while((pathcapacity = bfs()) != -1){//可以找到增广路径时候进行循环

  55:          int cur = end;    //从汇点开始增加逆向节点

  56:          while( cur != start ){

  57:              int t = prenode[cur] ;

  58:              capacity[t][cur] -= pathcapacity;

  59:              capacity[cur][t] += pathcapacity;

  60:              cur = t;

  61:          }

  62:          total += pathcapacity;//max_flow

  63:      }

  64:      return total;

  65:  }

  66:  void output(){

  67:      freopen("ditch.out","w",stdout);

  68:      //freopen("c:\\usaco\\ditch.out","w",stdout);

  69:      cout<<Edmonds_Karp()<<endl;

  70:  } 

  71:     int main()

  72:  {

  73:      init();  

  74:      output();

  75:      return 0;

  76:  }

标程：使用贪心法，寻找一条增广路径的时候不断寻找cap最大的，未被访问的节点mloc；然后更新跟mloc相邻的节点flow以

及prenode信息.最后当运行到end时候，更新路径节点capacity，同时增加max_flow.重复上述过程直到找不到增广路径

   1:  #include <stdio.h>

   2:  #include <string.h>

   3:   

   4:  #define MAXI 200

   5:   

   6:  /* total drain amount between intersection points */

   7:  int drain[MAXI][MAXI];

   8:  int nint; /* number of intersection points */

   9:   

  10:  int cap[MAXI]; /* amount of flow that can get to each node */

  11:  int vis[MAXI]; /* has this node been visited by Dijkstra's yet? */

  12:  int src[MAXI]; /* the previous node on the path from the source to here */

  13:   

  14:  int augment(void)

  15:   { /* run a Dijkstra's varient to find maximum augmenting path */

  16:    int lv;

  17:    int mloc, max;

  18:    int t;

  19:   

  20:    memset(cap, 0, sizeof(cap));

  21:    memset(vis, 0, sizeof(vis));

  22:   

  23:    cap[0] = 2000000000;

  24:    while (1)

  25:     {

  26:      /* find maximum unvisited node */

  27:      max = 0;

  28:      mloc = -1;

  29:      for (lv = 0; lv < nint; lv++)

  30:        if (!vis[lv] && cap[lv] > max)

  31:         {

  32:          max = cap[lv];

  33:      mloc = lv;

  34:         }

  35:      if (mloc == -1) return 0;

  36:      if (mloc == nint-1) break; /* max is the goal, we're done */

  37:   

  38:      vis[mloc] = -1; /* mark as visited */

  39:   

  40:      /* update neighbors, if going through this node improves the

  41:         capacity */

  42:      for (lv = 0; lv < nint; lv++)

  43:        if (drain[mloc][lv] > cap[lv] && max > cap[lv])

  44:         {

  45:          cap[lv] = drain[mloc][lv];

  46:      if (cap[lv] > max) cap[lv] = max;

  47:      src[lv] = mloc;

  48:         }

  49:     }

  50:    max = cap[nint-1];

  51:   

  52:    /* augment path, starting at end */

  53:    for (lv = nint-1; lv > 0; lv = src[lv])

  54:     {

  55:      t = src[lv];

  56:      drain[t][lv] -= max;

  57:      drain[lv][t] += max;

  58:     }

  59:    return max;

  60:   }

  61:   

  62:  int main(int argc, char **argv)

  63:   {

  64:    FILE *fout, *fin;

  65:    int lv;

  66:    int num;

  67:    int p1, p2, c;

  68:   

  69:    if ((fin = fopen("ditch.in", "r")) == NULL)

  70:     {

  71:      perror ("fopen fin");

  72:      exit(1);

  73:     }

  74:    if ((fout = fopen("ditch.out", "w")) == NULL)

  75:     {

  76:      perror ("fopen fout");

  77:      exit(1);

  78:     }

  79:   

  80:    fscanf (fin, "%d %d", &num, &nint);

  81:    while (num--)

  82:     {

  83:      fscanf (fin, "%d %d %d", &p1, &p2, &c);

  84:      p1--;

  85:      p2--;

  86:      drain[p1][p2] += c; /* note += handles two ditches between same points */

  87:     }

  88:   

  89:    /* max flow algorithm: augment while you can */

  90:    c = 0;

  91:    while ((p1 = augment()))

  92:      c += p1;

  93:    fprintf (fout, "%d\n", c);

  94:    return 0;

  95:   }

最后一章~~拖了几天，得赶紧记下了~~

名字： On the cusp of the object model

7.1 Template

Template用的很少，这节中的有些东西比较晦涩，挑一些能理解的记下吧。剩下的等用的多了再回头来看。

Template的具现行为 template instantiation

Template <calss T>class Point{

  public: enum Status{unallocated,normalized};Point(T x=0.0,T y=0.0);

~Point() ; void * operator new(size_t);private:static Point<T> *freelist

static int chunksize; T _x,_y;

};

编译器看到这样的声明，会有什么动作？？

没有。static data 不可用 enum 不可用 ，enum虽然类型固定，但他只能和template point class 的某个实体来存取或操作。我们可以 point<float>::Status s;

但是不能 point::status s; 因此我们可能想把enum抽离到一个非模板类以避免多重拷贝。同样道理，freelist 和chunksize对于程序而言也不可用。必须明确指定point<float>::freelist.也就是说静态数据成员是和特定类型的类绑定的而不是泛型的模板类。但是如果定义一个指针不一定会具现出相应的类，因为一个指针，并不一定指向一个class object。编译器不需要知道该class 相应的任何member 或者数据或者

内存布局，所以没有必要具现。但是如果是定义并初始化一个引用就真的会具现出一个实体，因为不存在空引用。

成员函数并不应该被实体化，只有当他被调用的时候才需要被具现出来。

template<class T>

class mumble{

public: Muble(T t=1024):tt(t){ if(tt!=t)throw ex; }

private: T tt;

};

上面的模板中出现错误有，t=1024 不一定成功，!= 不一定定义

这两个错误只有到具现操作结合具体类型才能确定出来

编译器面对一个template声明，在他被一组实际参数具现之前，只能实行以有限地错误检查，只有特定实体定义之后，才会发现一些与语法无关的但是十分明显的错误，这是技术上的一大问题。

Template 的名称决议方式

.h文件定义

void out(int x){
    cout<<"out_by_class_define_scrope"<<endl;
}
template <class type>
class A{
public:
    void test1(){
        out(m1);
    }
    void test2(){
        out(m2);
    }
private:
    int m1;
    type m2;
};

.cpp文件定义

void out(double x){
    cout<<"out_by_class_instantiation_scrope"<<endl;
}

int main(）
{    
    A<double> a;
    a.test1();
    a.test2();

}

按照书中的说法，如果一个函数，参数类型和type无关的话，应该取他的scope of template declaration中定义的函数，而反之取在他的instantiation中的那个。事实上在测试中发现

MSVC 中 ，函数定义的决议是依照类型的，如果有合适的函数比如type是double，此时如果定义处或者具现处有double型的函数定义，那么函数就会决议为那一个定义的~~~

MEMber function的具现行为：

编译器如何确保只有一个vtable产生？ 一种方法是 每一个virtual func地址都放在vtable中，如果取得函数地址，则表示virtual func 的定义必然出现在程序的某个地点，否则程序无法连接成功。此外该函数只能有一个实体，否则也是连接不成功。那么，就把vtable放在定义了该class的第一个non-inline，nonpure virtual function的文件中吧。。（not so clear）

在实现层面上，template 似乎拒绝全面自动化，以手动方式在个别的object module中完成预先的具现工作是一种有效率的方法。

7.2异常处理

为了维持执行速度，编译器可以在编译时期建立起用于支持的数据结构

为了维持程序大小，编译器可以在执行期建立数据结构

c++ eH 主要由三个部分构成：

throw语句

catch语句

try语句，这些语句可能触发catch子句起作用

一个exception 被抛出时候，控制权会从函数调用释放出来，并寻找一个吻合的catch，如果没有那么默认的处理例程terminate()会被调用，控制权放弃后，堆栈中的每一个函数调用也被推离。每一个函数被推离堆栈的时候，函数的local class object 的dtor也会被调用。

在程序不同段里，由于声明不同的变量，一个区域可能因为在区域内发生exception的处理方式不同分成多个区段。

在程序员层面，eh也改变了函数在资源上的管理。例如下面函数中更含有对一块共享内存的locking和unlocking操作 ：

void mumble(void * arena){

Point *p= new point ;

smlock(arena) ;

//…..如果此时一个exception发生，问题就产生了

sumunlock(arena);

delete p;

}

从语义上讲，我们在函数退出堆栈之前，需要unlock共享内存并delete p，我们需要这样做：

try{smlock(arena)} catch(…){

    smunlock(arena); delete p; throw;

}

new不需要放在try段里，因为，如果new发生了exception，heap中的内存并没有分配，point的ctor没有调用，如果在ctor中exception，那么piont的任何构造好的合成物也会自动解构掉，heap也会自动释放掉。

处理这种资源管理问题，建议： 把资源需求封装在一个class object 体内，并由dtor释放资源.

auto_ptr<point> ph (new point); smlock sm(arena);//如果此时exception 没有问题

// 不需要明确的unlock 和delete

// local dtor 会在这里被调用 sm.SMlock::~smlock(); ph.auto_ptr<point>::~auto_ptr<point>

Exception handling 的支持：

1.检验发生throw操作的函数

2.决定throw是否发生在try区段里

3.如果是编译器必须把exception type 拿来和catch比较

4.吻合的话控制权交给catch

5.如果throw不发生在try段或者没有吻合的，系统会摧毁所有active local object b从堆栈把当前函数unwind掉 ，跳出到程序堆栈的下一个函数去，然后重复上述步骤

当一个实际对象在程序执行时被抛出，exception object会被产生出来并通常放在相同形式的exception 数据堆栈中。

catch(expoint p){

   //do sth

   throw;

}

以及一个exception object 类型为 exVertex 派生自 expoint ，这两种类型都吻合，catch会怎么做

以exception object作为初值，像函数参数一样会有一个local copy，如果p是一个object而不是一个reference ，内容被拷贝的时候，这个object的非expoint部分会被切掉，如果有vptr 会被设定为expoint的vptr，如果被再次丢出呢？丢出p需要再产生另外一个exception 临时对象，丢出原来的异常 ，之前的修改统统作废。但是如果 catch(expoint& p);怎么样呢。 任何对这个object的改变都会繁殖到之后的catch语句总。

c++ 编译器为了支持EH付出的代价最大，某种程度是因为执行期的天性以及对底层硬件的依赖。

7.3 RTTI

RTTI是Except handling的一个附属产品，因为我们需要提供某种查询exception objects的方法，用来得到exception的实际类型。

在向下转型问题上，如果要保证其安全性，那么必须在执行期对指针有所查询，看看它到底指向什么类型的对象。那么我们需要额外的空间存储类型信息，通常是一个指针，指某个类型信息节点。

需要额外的时间以决定执行期的类型。

冲突发生在：

1.程序员大量的使用了多台，并需要大量的downcast操作

2.程序员使用内建的数据类型和非多态，他不需要额外负担带来的便利

那么如何了解程序员的需要呢？？ 策略是一个具有多态性性质的class，也就是具有内涵继承或者声明 virtual func的类需要rtti支持。

这样所有多态类维护一个vptr。额外负担降低到：每一个class object多花费一个指针，指针只被设定一次，而且是编译器静态设定。

down_cast

if(pfct pf = dynamic_cast< pfct >(pt))….

((type_info*)(pt->vptr[0]))->type_descripter;

Reference --------Pointer

dynamic_cast执行在ptr上 失败返回0，如果实行在ref上。由于ref不能被赋予null，也就是没有空引用。如果我们把一个ref设为0会引发临时对象产生，然后用0初始化它，使ref成为这个临时对象的别名。因此此时失败了会产生一个bad_cast exception。

typeid的参数可以使引用，对象或者是类型

事实上，type_info 也适用内建类型，这对于eh机制有必要

例如 int ex_errno; throw ex_errno;

其中int类型 int *ptr; if(typeid(ptr) == typeid(int*));

----------------------全书笔记到此结束 --------------------------------s

第一组

1.烧一根不均匀的绳，从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢？
2.你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻？
3.如果你有无穷多的水，一个3公升的提捅，一个5公升的提捅，两只提捅形状上下都不均匀，问你如何才能准确称出4公升的水？
4.一个岔路口分别通向诚实国和说谎国。来了两个人，已知一个是诚实国的，另一个是说谎国的。诚实国永远说实话，说谎国永远说谎话。现在你要去说谎国，但不知道应该走哪条路，需要问这两个人。请问应该怎么问？
5.12个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。13个呢？（注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑）
6.在9个点上画10条直线，要求每条直线上至少有三个点？
7.在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次？都分别是什么时间？你怎样算出来的？
8.怎么样种植4棵树木，使其中任意两棵树的距离相等？

第二组

1.为什么下水道的盖子是圆的？
2.中国有多少辆汽车？
3.将汽车钥匙插入车门，向哪个方向旋转就可以打开车锁？
4.如果你要去掉中国的34个省（含自治区、直辖市和港澳特区及台湾省）中的任何一个，你会去掉哪一个，为什么？
5.多少个加油站才能满足中国的所有汽车？
6.想象你站在镜子前，请问，为什么镜子中的影象可以颠倒左右，却不能颠倒上下？
7.为什么在任何旅馆里，你打开热水，热水都会瞬间倾泻而出？
8.你怎样将Excel的用法解释给你的奶奶听？
9.你怎样重新改进和设计一个ATM银行自动取款机？
10.如果你不得不重新学习一种新的计算机语言，你打算怎样着手来开始？
11.如果你的生涯规划中打算在5年内受到奖励，那获取该项奖励的动机是什么？观众是谁？
12.如果微软告诉你，我们打算投资五百万美元来启动你的投资计划，你将开始什么样商业计划？为什么？
13.如果你能够将全世界的电脑厂商集合在一个办公室里，然后告诉他们将被强迫做一件事，那件事将是什么？

第三组

1.你让工人为你工作7天，回报是一根金条，这个金条平分成相连的7段，你必须在每天结束的时候给他们一段金条。如果只允许你两次把金条弄断，你如何给你的工人付费？
2.有一辆火车以每小时15公里的速度离开北京直奔广州，同时另一辆火车每小时20公里的速度从广州开往北京。如果有一只鸟，以30公里每小时的速度和两辆火车同时启动，从北京出发，碰到另一辆车后就向相反的方向返回去飞，就这样依次在两辆火车之间来回地飞，直到两辆火车相遇。请问，这只鸟共飞行了多长的距离？
3.你有四个装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被污染的药丸的重量+1。只称量一次，如何判断哪个罐子的药被污染了？
4.门外三个开关分别对应室内三盏灯，线路良好，在门外控制开关时候不能看到室内灯的情况，现在只允许进门一次，确定开关和灯的对应关系？
5.人民币为什么只有1、2、5、10的面值？
6.你有两个罐子以及50个红色弹球和50个蓝色弹球，随机选出一个罐子， 随机选出一个弹球放入罐子，怎么给出红色弹球最大的选中机会？在你的计划里，得到红球的几率是多少？
7.给你两颗6面色子，可以在它们各个面上刻上0-9任意一个数字，要求能够用它们拼出任意一年中的日期数值

第四组

第一题 . 五个海盗抢到了100颗宝石，每一颗都一样大小和价值连城。他们决定这么分：
抽签决定自己的号码（1、2、3、4、5）
首先，由1号提出分配方案，然后大家表决，当且仅当超过半数的人同意时，按照他的方案
进行分配，否则将被扔进大海喂鲨鱼
如果1号死后，再由2号提出分配方案，然后剩下的4人进行表决，当且仅当超过半数的人同
意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼
依此类推
条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。
问题：第一个海盗提出怎样的分配方案才能使自己的收益最大化？

第二题 . 一道关于飞机加油的问题，已知：
每个飞机只有一个油箱，
飞机之间可以相互加油（注意是相互，没有加油机）
一箱油可供一架飞机绕地球飞半圈，
问题：
为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？（所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场）

第三题. 汽车加油问题
一辆载油500升的汽车从A开往1000公里外的B，已知汽车每公里耗油量为1升，A处有无穷多的油，其他任何地点都没有油，但该车可以在任何地点存放油以备中转，问从A到B最少需要多少油

第四题. 掷杯问题
一种杯子，若在第N层被摔破，则在任何比N高的楼层均会破，若在第M层不破，则在任何比M低的楼层均会破，给你两个这样的杯子，让你在100层高的楼层中测试，要求用最少的测试次数找出恰巧会使杯子破碎的楼层。

第五题. 推理游戏
教授选出两个从2到9的数，把它们的和告诉学生甲，把它们的积告诉学生乙，让他们轮流猜这两个数
甲说：“我猜不出”
乙说：“我猜不出”
甲说：“我猜到了”
乙说：“我也猜到了”
问这两个数是多少

第六题. 病狗问题
一个住宅区内有100户人家，每户人家养一条狗，每天傍晚大家都在同一个地方遛狗。已知这些狗中有一部分病狗，由于某种原因，狗的主人无法判断自己的狗是否是病狗，却能够分辨其他的狗是否有病，现在，上级传来通知，要求住户处决这些病狗，并且不允许指认他人的狗是病狗（就是只能判断自己的），过了7天之后，所有的病狗都被处决了，问，一共有几只病狗？为什么？

第七题. U2合唱团在17分钟内得赶到演唱会场，途中必需跨过一座桥，四个人从桥的同一端出发，你得帮助他们到达另一端，天色很暗，而他们只有一只手电筒。一次同时最多可以有两人一起过桥，而过桥的时候必须持有手电筒，所以就得有人把手电筒带来带去，来回桥两端。手电筒是不能用丢的方式来传递的。四个人的步行速度各不同，若两人同行则以较慢者的速度为准。BONO需花1分钟过桥,EDGE需花2分钟过桥,ADAM需花5分钟过桥,LARRY需花10分钟过桥,他们要如何在17分钟内过桥呢？

第八题. 监狱里有100个房间，每个房间内有一囚犯。一天，监狱长说，你们狱房外有一电灯，你们在放风时可以控制这个电灯（熄或亮）。每天只能有一个人出来放风，并且防风是随机的。如果在有限时间内，你们中的某人能对我说：“我敢保证，现在每个人都已经至少放过一次风了。”我就放了你们！问囚犯们要采取什么策略才能被监狱长放掉？如果采用了这种策略，大致多久他们可以被释放？

第五组

1.某手机厂家由于设计失误，有可能造成电池寿命比原来设计的寿命短一半（不是冲放电时
间），解决方案就是免费更换电池或给50元购买该厂家新手机的折换券。请给所有已购买的
用户写信告诉解决方案。
2.一高层领导在参观某博物馆时，向博物馆馆员小王要了一块明代的城砖作为纪念，按国家
规定，任何人不得将博物馆收藏品变为私有。博物馆馆长需要如何写信给这位领导，将城砖
取回。
3.营业员小姐由于工作失误，将2万元的笔记本电脑以1.2万元错卖给李先生，王小姐的经理
怎么写信给李先生试图将钱要回来？
4.给你一款新研制的手机，如果你是测试组的组长，你会如何测试？
5.如何为函数int atoi(const char * pstr)编写测试向量？

第六组

1.链表和数组的区别在哪里？
2.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？
3.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？
4.请编写能直接实现char * strcpy(char * pstrDest,const char * pstrSource)函数功能的代码。
5.编写反转字符串的程序，要求优化速度、优化空间。
6.在链表里如何发现循环链接？
7.给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。
8.写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码
9.给出一个函数来输出一个字符串的所有排列。
10.请编写实现void * malloc(int)内存分配函数功能一样的代码。
11.给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。
12.怎样编写一个程序，把一个有序整数数组放到二叉树中？
13.怎样从顶部开始逐层打印二叉树结点数据？请编程。
14.怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？ --
15.请编写能直接实现int atoi(const char * pstr)函数功能的代码。

---------------------------------------------------------------------------------------

第一组题答案：

1）三根绳，第一根点燃两端，第二根点燃一端，第三根不点
第一根绳烧完（30分钟）后，点燃第二根绳的另一端，第二根绳烧完（45分钟）后，点燃第三根绳子两端，第三根绳烧完（1小时15分）后，计时完成
2）根据抽屉原理，4个
3）3升装满；3升-〉5升（全注入）；3升装满；3升-〉5升（剩1升）；5升倒掉；3升-〉5升（注入1升）；3升装满；3升-〉5升；完成（另：可用回溯法编程求解）
4）问其中一人：另外一个人会说哪一条路是通往诚实国的？回答者所指的那条路必然是通往说谎国的。
5）12个球：
第一次：4，4 如果平了：
  那么剩下的球中取3放左边,取3个好球放右边，称：
    如果左边重，那么取两个球称一下，哪个重哪个是次品，平的话第三个重，是次品，轻的话同理
    如果平了，那么剩下一个次品，还可根据需要称出次品比正品轻或者重
如果不平：
  那么不妨设左边重右边轻，为了便于说明，将左边4颗称为重球，右边4颗称为轻球，剩下4颗称为好球
  取重球2颗，轻球2颗放在左侧，右侧放3颗好球和一颗轻球
  如果左边重
      称那两颗重球，重的一个次品，平的话右边轻球次品
  如果右边重
      称左边两颗轻球，轻的一个次品
  如果平
      称剩下两颗重球，重的一个次品，平的话剩下那颗轻球次品
13个球：
第一次：4，4，如果平了
  剩5颗球用上面的方法仍旧能找出次品，只是不能知道次品是重是轻
如果不平，同上
6）
o   o   o
  o o o
o   o   o
7）
23次，因为分针要转24圈，时针才能转1圈，而分针和时针重合两次之间的间隔显然>1小时，它们有23次重合机会，每次重合中秒针有一次重合机会，所以是23次
重合时间可以对照手表求出，也可列方程求出
8）
在地球表面种树，做一个地球内接的正四面体，内接点即为所求

第二组 无标准答案

第三组

1. 分成1,2,4三段，第一天给1，第二天给2取回1，第3天给1，第4天给4取回1、2，第5天给1，第6天给2取回1，第七天给1
2. 求出火车相遇时间，鸟速乘以时间就是鸟飞行的距离
3. 四个罐子中分别取1,2,3,4颗药丸，称出比正常重多少，即可判断出那个罐子的药被污染
4. 三个开关分别：关，开，开10分钟，然后进屋，暗且凉的为开关1控制的灯，亮的为开关2控制的灯，暗且热的为开关3控制的灯
5. 因为可以用1，2，5，10组合成任何需要的货币值，日常习惯为10进制
6. 题意不理解...*_*
7. 012345 0126(9)78

第四组 都是很难的题目

第一题：97 0 1 2 0 或者 97 0 1 0 2 （提示：可用逆推法求出）

第二题：3架飞机5架次，飞法：
ABC 3架同时起飞，1/8处，C给AB加满油，C返航，1/4处，B给A加满油，B返航，A到达1/2处，C从机场往另一方向起飞，3/4处，C同已经空油箱的A平分剩余油量，同时B从机场起飞，AC到7/8处同B平分剩余油量，刚好3架飞机同时返航。所以是3架飞机5架次。

第三题：需要建立数学模型
（提示，严格证明该模型最优比较麻烦，但确实可证，大胆猜想是解题关键）
题目可归结为求数列 an=500/(2n+1) n=0,1,2,3......的和Sn什么时候大于等于1000,解得n>6
当n=6时，S6=977.57
所以第一个中转点离起始位置距离为1000-977.57=22.43公里
所以第一次中转之前共耗油 22.43*(2*7+1)=336.50升
此后每次中转耗油500升
所以总耗油量为7*500+336.50=3836.50升

第四题：需要建立数学模型
题目可归结为求自然数列的和S什么时候大于等于100，解得n>13
第一个杯子可能的投掷楼层分别为：14，27，39，50，60，69，77，84，90，95，99，100

第五题：3和4（可严格证明）
设两个数为n1，n2，n1>=n2，甲听到的数为n=n1+n2，乙听到的数为m=n1*n2
证明n1=3，n2=4是唯一解
证明：要证以上命题为真，不妨先证n=7
1)必要性：
   i) n>5 是显然的，因为n<4不可能，n=4或者n=5甲都不可能回答不知道
   ii) n>6 因为如果n=6的话，那么甲虽然不知道（不确定2+4还是3+3）但是无论是2，4还是3，3乙都不可能说不知道（m=8或者m=9的话乙说不知道是没有道理的）
  iii) n<8 因为如果n>=8的话，就可以将n分解成 n=4+x 和 n=6+(x-2)，那么m可以是4x也可以是6(x-2)而4x=6(x-2)的必要条件是x=6即n=10，那样n又可以分解成8+2，所以总之当n>=8时，n至少可以分解成两种不同的合数之和，这样乙说不知道的时候，甲就没有理由马上说知道。
   以上证明了必要性
2)充分性
    当n=7时，n可以分解成2+5或3+4
    显然2+5不符合题意，舍去，容易判断出3+4符合题意，m=12，证毕
于是得到n=7 m=12 n1=3 n2=4是唯一解。

第六题：7只（数学归纳法证明）
1）若只有1只病狗，因为病狗主人看不到有其他病狗，必然会知道自己的狗是病狗（前提是一定存在病狗），所以他会在第一天把病狗处决。
2）设有k只病狗的话，会在第k天被处决，那么，如果有k+1只，病狗的主人只会看到k只病狗，而第k天没有人处决病狗，病狗主人就会在第k+1天知道自己的狗是病狗，于是病狗在第k+1天被处决
3）由1）2）得，若有n只病狗，必然在第n天被处决

第七题：（提示：可用图论方法解决）
BONO&EDGE过（2分），BONO将手电带回（1分），ADAM&LARRY过（10分），EDGE将手电带回（2分），BONO&EDGE过（2分） 2+1+10+2+2=17分钟

第八题：
约定好一个人作为报告人（可以是第一个放风的人）
规则如下：
1、报告人放风的时候开灯并数开灯次数
2、其他人第一次遇到开着灯放风时，将灯关闭
3、当报告人第100次开灯的时候，去向监狱长报告，要求监狱长放人......
按照概率大约30年后（10000天）他们可以被释放

第五组无标准答案

第六组部分题参考答案：
4.
char * strcpy(char * pstrDest,const char * pstrSource)
{
assert((pstrDest!=NULL)&&(pstrSource!=NULL));

char * pstr=pstrDest;
while((*(pstrDest++)=*(pstrSource++))!='\0');
        return pstr;
}
5.
char * strrev(char * pstr)
{
assert(pstr!=NULL);
char * p=pstr;
char * pret=pstr;
while(*(p++)!='\0');
p--;
char tmp;
while(p>pstr)
{
  tmp=*p;
  *(p--)=*(pstr);
  *(pstr++)=tmp; 
}
return pret;

执行期语义学 RunTime Semantics

if( yy == xx.getValue() ) …

X xx; Y yy;

class Y{

public:

Y();  ~Y();  bool operator == (constY& )const;

};

class X{

public:

X(); ~X(); operator Y()const; //重载转换类型操作符 必须成员不能有参数不能有返回值详细在 http://www.cppblog.com/zqsand/archive/2010/03/15/109748.html里面有介绍

X getValue();

};

看看上面的表达式怎么执行的~~~

首先等号运算符的参数确定  if(yy.operator==(xx.getValue()));

Y的== 需要一个Y型的参数，但是getvalue得到的是一个X型的，如果没有X到Y的转型方法，这个式子是错的~ 而恰好X有个类型转换符~

if(yy.operator == (xx.getValue().operator Y()))

增加的代码都是编译器默默为我们加上的~~~

注意在这个过程中，我们需要一个临时的Xobject 储存 getValue返回值 X temp1 = xx.getValue()

一个class Y object 储存 operator Y()返回值 Y temp2 = temp1.operator Y();

一个 int 放置 等号返回值  int tmp3 = yy.operator == (temp2);

最后析构函数会实施在每一个临时class object上.

所以，我们的代码变成：

{

X temp1 = xx.getValue();Y temp2 = temp1.operator Y();int tmp3 = yy.operator == (temp2);

if(tmp3)  dosth```

tmp2.Y::~Y();

tmp1.X::~X();

}

surprise~~-----------------------------------------------------------------------

6.1-对象的构造和析构

·一般来说，dtor会被放在每一个离开点（object 还存活）之前 ，所以，如果一个区段或者函数有多个离开点，那么每一个return 离开点都要插入一个dtor了。因此我们一般尽量放置object在使用它的程序区段附近，节省不必要的对象产生与摧毁操作。

·全局对象：全局对象如果有ctor或者dtor的话需要静态的初始化操作和内存释放操作。c++中全局对象放在data segment中，如果不明确指定值，内存内容为0.

但是ctor必须等到程序startup后才能实施。由于必须对一个放在datasegment 中的object初始化表达式evaluate ，所以object需要静态初始化

一种策略（cfont 的 munch）

为每一个需要静态初始化的档案产生一个  _sti()函数，内带必要的ctor调用操作或者inline expansions。 类似的产涩会给你一个std()函数调用dtor

一个_main()函数调用sti 一个 exit()函数调用_std()

然后cfont在我们的程序中安插对 _main _exit 的调用。 最后需要解决的是如何收集各个对象的sti和std。cfont使用了nm命令 ， 打印出符号表格(目标文件的符号表)，然后munch会搜索所有用sti或者std开头的目标函数，把他们记录到一个表格，当main和exit调用时候便利表格即可。

修改版本的方法是：system V中，coff格式的目标文件，检验可执行文件，找出有着_linknodes并且内带一个指针指向 sti 和std函数的文件，把他们都串联起来，接下来把链表头结点设置为一个全局的_head object (定义在新的 patch runtime library)，这个library中有一种不同的_main _exit 他们会以head为起点，遍历链表，调用sti和std。

实际上现在的ELF格式，有init 和.fini两个section，完成静态初始化和释放操作。编译器设定的startup函数会完成平台特定的支持

virtual base class 的指针或者引用存取virtual base class subobject，是一种只有在执行期才能加以确定的操作。所以，编译器需要支持class object 的静态初始化，至少涵盖object的指针和reference。

局部静态对象

const Matrix& identity(){

    static Matrix mat_identity;

    return mat_identity;

}

mat_identity的ctor必须只执行一次，mat_identity的dtor必须只执行一次

编译器只在identity被调用的时候才构造mat_identity，这样避免如果不被调用也需要构造所有对象。同时编译器引入条件式解析~也就是如果构造了则解析之

对象数组：

Points knots[10];

如果Points没有定义ctor和dtor只要分配空间即可

如果有default ctor ，ctor必须实施于每个元素身上~这是由runtime library 完成的。 cfont中 我们使用vec_new()函数  MS和Sun提供两个函数，一个用来处理 vbs的class 一个处理内带base class 的class，后者为 vec_vnew() 函数原型基本如下

void* vec_new(void *array,size_t elem_size,int elem_count,void (*ctor)(void*),void(*dtor)(void*,char)))

array如果是0，数组由new分配与heap， vec_new(&knots,sizeof(Point),10,&Point::Point,0);

6.2 new 和 delete 运算符

int *pi  = new int(5);

执行步骤：

int* pi = __new (sizeof(int));

*pi = 5;

int *pi;

if(pi = __new(sizeof(int)))

   *pi=5;

delete pi;

if(pi!=0)

__delete (pi);

注意pi并不会自动清除为0！

CTOR

Point3d * origin=new Point3d;

if(origin = __new(sizeof(Point3d))){

try{

   origin = Point3d::Point3d(origin);   

}

calch(…){

__delete(origin);

throw;//上传exception

}

}

DTOR

delete origin;

if(origin!=0){

  Point3d::~Point3d(origin);

   __delete(origin);

}

一种library对new的设计：~~

extern void* operator new(size_t size){

if(size==0)size=1;

void *last_alloc;

while(!(last_alloc=malloc(size))){

if(_new_handler) (*_new_handler)();

else return 0;

}

return last_alloc;

}

虽然new T[0];是合法的，但是语言要求每次对new的调用必须返回一个独一无二的指针，解决该问题的传统方法是传回一个指针，指向默认为1byte的内存区块。所以size被设为1.然后这种设计允许使用者提供一个属于自己的_new_handler() 函数。

extern void operator delete (void *ptr) { if(ptr)free (char*)ptr;}

针对数组的new 语义：

int *p_array = new int[5];

这时候 vec_new()不会真正调用，因为，它的主要功能是把default ctor 实施于class object数组的每个元素身上。new运算符会被调用：

int *p_array = (int*) __new(5*sizeof(int));

如果数组的class object 有default ctor vec_new才会被调用。

Point3d *p_array = new Point3d[10];编译成:

Point3d *p_array = vec_new(0,sizeof(Point3d),10,&point3d::Point3d,&Point3d::~Point3d);

个别数组构造如果exception发生，dtor被传输给vec_new ，已经构造的object需要dtor 实施。

delete 时候，开始需要程序员指定大小，后来编译器开始不适用程序员指定的，而是只需要写delete [] ptr 即可。

如何记录数组大小呢：

一种方法在vecnew返回的内存块配置一个额外的word，大小放在其中。

如果

class Point {public:virtual ~Point (){}};

class Point3d : public Point {public:virtual ~Point3d(){}};

如果Point *ptr = new Point3d[10];

当我们delete [] ptr;时候只有 Point::~Point被掉用````

在vc里敲了代码验证确实如此~~~

实施于数组上的dtor是根据交给vec_delete()函数的被删除指针类型的dtor，也就是point的dtor，每一个元素大小也被一起传了过去。

如何避免：

避免一个base class 指针指向一个derived class 的数组。如果真的要这么写看代码吧

class point{
public:
    int p;
    point(){cout<<"point ctor"<<endl;}
    ~point(){cout<<"point dtor"<<endl;}
};
class point3d:public point{
public:
    int q;
    point3d(){cout<<"point3d ctor"<<endl;}
    ~point3d(){cout<<"point3d dtor"<<endl;}
};
int main()
{   
     point *ptr = new point3d[3];
     //delete [] ptr; 这样写是不行的

     //要这样写
     for(int i=0;i<3;i++){
         point3d * p=&((point3d*)ptr)[i]; //恢复成point3d数组指针
         delete p;
     }
}

Placement Operator New

有一个重载过的new 运算符 需要两个参数，类型为void*

Point2w *ptw = new(area) Point2w;

其中area指向内存一个区块，用来放置产生出来的Point2w object.这个预先定义好的placement operator new 实现方法： 将获得的指针arena 所指的地址传回即可

void* operator new (size_t,void* p) {return p;}

事实上，他执行的另一半工作是：把point2w 的ctor 实施于 arena所指的地址上

Point2w *ptw = (Point2w *)arena; if(ptw!=0)ptw->Point2w::Point2w();

-------

p2w->~Point2w;

p2w = new(arena)Point2w;

如果我们用

delete p2w; p2w = new(arena) Point2w;

delete会释放p2w指向的内存 由于下一指令还要用到p2w，我们应该调用dtor并保留存储空间,以便再次使用.

还有一些关于placement opeator new 的设计问题··没看明白 不记了··

6.3临时对象 ：

c++对临时对象并无硬性规定，由编译器抉择。

实际上 T c = a+ b; T operator + (const T& ,const T&);

a+b可以直接构建于c上

那么根本不产生临时对象

但是，意义相当的 c=a+b;不能忽略临时对象":

T temp; temp=operator+(a,b);c.operator =(tmp);tmp.T::~T();

注意c=a+b;中，直接传递c进入operator 中，也就是不要tmp的话：由于operator函数不为其外加参数调用dtor(期望一个新鲜的内存)，所以必须在其调用前调用dtor.然而转换操作会变成c.T::~T();c.T::T(a+b);copy ctor dtor  copy assignment operator 都可以自定义，所以我们用 析构和拷贝构造代替赋值一般而言是不安全的，所以需要临时对象调用operator=

所以 T c=a+b;比 c=a+b;更有效率

临时对象生命周期：

临时对象被摧毁，应该是对完整表达式求职过程的最后一个步骤，该完整表达式造成临时对象的产生

如果一个临时对象绑定在一个reference上，对象将残留，知道被初始化之reference生命结束，或者知道临时对象的声明范畴结束。