欧美中文字幕在线,午夜精品影院,亚洲电影在线播放

win核心�~�程-Chap17-Memory-Mapped Files

rikisand — Wed, 26 May 2010 09:48:00 GMT

什么时候用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.

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

用途一�Q��用mapping file executables and dlls

当调用createProcess时候，�pȝ��做了以下的事�?

1.locates CreateProcess 中指定的the .exe file�Q�失败则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.(�pȝ��注意刎ͼ�支持已保留区域的物理存储区域是在��盘上的.exe 文�g而不是在�pȝ��面�?

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

如果加蝲dll或者exe ��p�|�Q�弹出对话框�q�且释放甌��的地址�I�间�?/font>

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. 例如�Q�如果一�D�代码访问了一个�ƈ不在��d��的地址�Q�那么一个错误��生，�pȝ��察觉到错误�ƈ且自动的调入page of code from the files image into a page of RAM�?/font>

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

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

当一个进�E�被加蝲�Q�系�l�检查其所有映��文仉��,�pȝ��所有通常用cow保护的页面提交给存储�pȝ��Q�这些页面仅仅是被提交，当文件被讉K��的时候，�pȝ��d��相应的页面，如果��面没有被修改，那么他们可以被换出，如果已经修改�Q�系�l�将修改�q�的��面转入已经提交的页面之一(�q�点很晦涩啊 system swaps the modified page to one of the perviously committed pages in the paging file ,怎么��译呢~~~~ �Q�（ )

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

在可执行文�g或者dll中共享静态变�?/font>

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

内存映射数据文�g

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

如果利用file mapping 我们告诉�pȝ��使用一个虚拟空间的区域来倒置文�g�Q�然后告诉把文�g的第一个字节映��到保留�I�间的第一个字节，然后��像处理内存中的字符串一样处理文件即可，引文�pȝ��会帮助你完成文�g�~�存以及调页�{�工作�?/font>

使用��程�Q?/font>

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 告诉�pȝ��文�g的大��，以及你准备如何访问文�?/font>

3.告诉�pȝ��map all或者部分文件到你的�q�程地址�I�间

当��用结束后要：

1告诉�pȝ�� unmap file-mapping kernel object form your process add

2cloes filemapping kernel object

3close file kernel object

---------

具体步骤

--1. 创徏文�g内核对象

CreateFile

��p�|�q�回 INVALID_HANDLE_VALUE = �? 一般来说windows func ��p�|return null�q�个比较�Ҏ��

createfile dwdesiredAccess 需要设�|��ؓ GENERIC_READ 或�?GENERIC_WRITE

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

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

�W�一个参��C��用createfile �q�回的handle。psa一般��用默认null。当创徏一个file mapping object 时候，�pȝ��q�不�?马上保留一个地址�I�间�Q�然后将file映射到这个区域。但很i�Q�当�pȝ��map时候，�pȝ��必须知道为physical storage分配什么样的保护属性，�W�三个参数指明了�q�些�?/font>

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

high指明�?2位，low指明�?2位。如果想创徏一个反应现在文件大��的map�Q�均�?.

pszName 用于与其它进�E�共享内存映��文�?/font>

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

使用�q�个函数

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

文�g没必要一�ơ全映射�Q�一�ơ映��一部分�Q�这一部分成�ؓ一个view

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

其次是指定映��多大，0则映��到文�g��N��?/font>

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

UnmapviewOfFile(PVOID pvBaseAdddress);

参数使用mapview的返回�?/font>

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

�W�一个地址是想要开始flush的地址

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

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

使用filemap 在进�E�之间共享数�?/font>

例子�Q?/font>

app开始时候，�pȝ��调用createfile to open .exe file onthe disk。sys call creatFileMapping to create filemapping object.然后�pȝ��调用 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�Q�sys 看到file-mapping已经存在了，�pȝ��maps a view of file a second time�Q�this time in the context of the newly created process address space.

像所有内核对象一��P��有三�U�方法共享他�Q��承，命名对象以及赋值handle�?/font>

···��|��件支持的内存映射文�g

许多应用�E�序�q�行是��生数据需要和其他�q�程�׃�n如果必须在硬盘徏立文件才可以�׃�n�Q�那么效率很低。因此微软提供了由system paging file 支持�?file mapping。不需要createfile �Q�只需要在调用createFilemapping 的时候传�q�一�?INVALID_HANDLE_VALUE 作�ؓhFile 参数卛_��?映射文�g大小同样是由high 和low 参数军_��的�?/font>

`````�E�疏提交的内存映射文�g

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

rikisand 2010-05-26 17:48 发表评论

Google code jam Round1B

rikisand — Tue, 25 May 2010 15:29:00 GMT

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

This refers to the directory with name "finals" in the directory described by "/home/gcj", which in turn refers to the directory with name "gcj" in the directory described by the path "/home". In this path, there is only one part, which means it refers to the directory with the name "home" in the root directory.

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  S;
        REP (i, n)
        {
            string s;
            cin >> s;
            S.insert(s);//已有的�\径用set表示
        }

        int res =0 ;

        REP (i, m)
        {
            string s;
            cin >> s;
            vector  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())//依次加入各��目录�Q?a  /a/b  /a/b/c 增加递增的所有目�?
                {
                    res ++;
                    S.insert(s);
                }
            }
        }

题目中的�q�一�?/font>

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存在�Q�那�?a也一定被list出来�?�Q�所以上面代码可以不��d��隔处理已�l�给出的目录

yuhch123的解�?/font>

struct node {
   map  sons;//每个节点�Q�用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 ++)//�W�一�?
      str += tmp[i];
   if (cnt -> sons.find(str) == cnt -> sons.end()) {//如果没有�q�子树，则创建子�?
      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的解�?/font>

vector  parse (string s)
{
    vector  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  direc;

int insert (vector  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�q�回一个pair 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 �q���o回�R�I�字�W�串
            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  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 ::iterator it = want.begin(); it != want.end(); it++)//遍历所有需要加入的�Q�然后看是否存在
      if (!have.count(*it))
    ans++;
    printf("Case #%d: %d\n", t, ans);
  }
}

rikisand 2010-05-25 23:29 发表评论

五一前小�l�下

rikisand — Sat, 01 May 2010 06:31:00 GMT

�q�学期也开始了好久�Q��ȝ��下�?

��目上：基本弄完了码��_��是�l�束了吧�Q�剩下的工作是好好�ȝ��下学到的东西�Q�把架构�Q�用到的技术都理顺了，方便之后面试回答�?

生活上：�q�半个月gf生病了，嘉定闵行两头跑果然很累，不过�q�好一直抽�I�看书。健康很重要~~ 要抓紧锻��D�n体了。本�׃��定要掌握好�?

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

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

1-4��h��假，应该不会有新的安排进来（面试之类的）�Q�得安排下事�?

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

然后想看看c++标准文档�Q�这个会很慢�Q�可以选择性的跌��一些东西，��d��700多页�Q�看�?00��就可以了，后面是介�l�库的。一天看75��，�?···比较困难·· ��力�?

其他的就不安排了�Q�也做不完的�?

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

rikisand 2010-05-01 14:31 发表评论

关于new和delete

rikisand — Wed, 07 Apr 2010 02:42:00 GMT

良好的编�E�风格是�Q�new和delete 配套使用�Q�即如果使用new [] 则��用delete []

事实上，如果我们使用的是自定义类型int char�{�，或者我们��用的是没有内存申��L��c�，我们使用 delete A;�q�不会发生什么不好的事情�?/font>

�q�是由delete 的语义决定的。当我们是申请一�l�对象时候，�~�译器会加入内存大小信息和此�D�内存相兌��。因此当我们delte A �Ӟ��~�译器会按照内存大小收回分给我们的内存。显�Ӟ��如果是基本类型或者没有申请内存的情况�q�样的行为是良好的。但是如果我们在自徏�c�d��中申请了内存~对不��P��~�译器是不知道的�Q�这些申��L��内存��是内存泄露�Q�随着�E�序不断�q�行�Q�堆不断地被侵蚀·····

�q�就是delete的第二个作用�Q�他会施加析构函数在我们甌��的内存上�Q�如果我们delete A�Q�只会在�W�一个上施加�Q�而如果delete [] A;他会�Ҏ��l�中每一个元素进行析构~~

so····

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

rikisand 2010-04-07 10:42 发表评论

关于寚w��

rikisand — Sun, 04 Apr 2010 08:00:00 GMT

数据寚w��Q�是指数据所在的内存地址必须是该数据长度的整数倍。处理器可以直接讉K��寚w��的数据，而访问未寚w��的数据会在内部进行一�p�d��的调��_��虽然可以正常处理�Q�但是会降低�q�行速度。例如一个处理器�ȝ��宽度�?4位，那么地址必须�?的倍数�Q�也��是一�ơ取�?个字节。如果我们可以保证所有double地址都�ؓ8的倍数�Q�那么可以用一个存储器操作来读或者写double了，否则我们可能需要执行两�ơ存储器讉K��Q�因为对象可能位于两�?字节存储器块�?/font>

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

更进一�?�Q?/font>

未对齐的数据会以不同方式�l�cpu带来�ȝ��~

1.如果一个变量被划分��C��个缓存行�Q�那么我们需要访问两个缓存行才可以�?/font>

2.一些simd指��o��L��要求寚w��的指令，对于未对齐的指��o�Q�数据对齐也会媄响这些指令的使用�?/font>

rikisand 2010-04-04 16:00 发表评论

USACO 4.2.2 �W�一道网�l�流····

rikisand — Fri, 26 Mar 2010 05:04:00 GMT

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_i, E_i, and C_i. S_i and E_i (1 <= S_i, E_i <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from S_i to E_i. C_i (0 <= C_i <= 10,000,000) is the maximum rate at which water will flow through the ditch.

SAMPLE INPUT (file ditch.in)

OUTPUT FORMAT

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

SAMPLE OUTPUT (file ditch.out)

最基本的网�l�流

   1:  #include

   2:  #include

   3:  #include<string>

   4:  #include

   5:  #include

   6:  #include

   7:  #include

   8:  #include

   9:  #include

  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  24:      {
  25:          scanf("%d %d %d",&c,&s,&t);
  26:          capacity[c][s] += t; //两个节点间不只有一条�\
  27:      } 
  28:  }
  29:  int bfs(){//��L��增广路径
  30:      while(!mq.empty()) mq.pop(); 
  31:      mq.push(start);  //源节点入�?/span>
  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; //到达汇点�l�束路径 
  39:          for(int i=1;i<=end;i++){ 
  40:              if(prenode[i]==-1 && capacity[cur][i]) //讉K��当前节点所有未讉K��的相邻节点，更新flow
  41:              {
  42:                  prenode[i] = cur;
  43:                  flow[i] = (flow[cur]  44:                  mq.push(i);
  45:              }
  46:          }
  47:      }
  48:      if(prenode[end]==-1)  //如果未找到增�q��\径返�?1
  49:          return -1;
  50:      return flow[end];
  51:  }
  52:  int Edmonds_Karp(){
  53:      int total = 0, pathcapacity;//pathcapacity 路径增加�?/span>
  54:      while((pathcapacity = bfs()) != -1){//可以扑ֈ�增广路径时候进行��@�?/span>
  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<  70:  } 
  71:     int main()
  72:  {
  73:      init();  
  74:      output();
  75:      return 0;
  76:  }

标程�Q��用贪心法�Q�寻找一条增�q��\径的时候不断寻找cap最大的�Q�未被访问的节点mloc�Q�然后更新跟mloc盔R��的节点flow�?/font>

及prenode信息.最后当�q�行到end时候，更新路径节点capacity�Q�同时增加max_flow.重复上述�q�程直到找不到增�q��\�?/font>

   1:  #include

   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:   }

rikisand 2010-03-26 13:04 发表评论

深入探烦C++对象模型��M��W�记 (�?

rikisand — Thu, 25 Mar 2010 13:09:00 GMT

最后一章~~拖了几天�Q�得赶紧��C��了~~

名字�Q?On the cusp of the object model

7.1 Template

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

Template的具现行�?template instantiation

Template 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 *freelist

static int chunksize; T _x,_y;

};

�~�译器看到这��L��声明�Q�会有什么动作？�Q?/font>

没有。static data 不可�?enum 不可�?�Q�enum虽然�c�d��固定�Q�但他只能和template point class 的某个实体来存取或操作。我们可�?point::Status s;

但是不能 point::status s; 因此我们可能��x��enum抽离��C��个非模板�c�M��避免多重拯��。同样道理，freelist 和chunksize对于�E�序而言也不可用。必��L��指定point::freelist.也就是说静态数据成员是和特定类型的�cȝ��定的而不是泛型的模板�c�R��但是如果定义一个指针不一定会��L��出相应的�c�，因�ؓ一个指针，�q�不一定指向一个class object。编译器不需要知道该class 相应的�Q何member 或者数据或�?/font>

内存布局�Q�所以没有必要具现。但是如果是定义�q�初始化一个引用就真的会具现出一个实体，因�ؓ不存在空引用�?/font>

成员函数�q�不应该被实体化�Q�只有当他被调用的时候才需要被��L��出来�?/font>

template

class mumble{

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

private: T tt;

};

上面的模板中出现错误有，t=1024 不一定成功，!= 不一定定�?/font>

�q�两个错误只有到��L��操作�l�合具体�c�d��才能��定出来

�~�译器面对一个template声明�Q�在他被一�l�实际参数具��C��前，只能实行以有限地错误��查，只有特定实体定义之后�Q�才会发��C��些与语法无关的但是十分明昄��错误�Q�这是技术上的一大问题�?/font>

Template 的名�U�决议方�?/font>

.h文�g定义

void out(int x){
    cout<<"out_by_class_define_scrope"<}
template
class A{
public:
    void test1(){
        out(m1);
    }
    void test2(){
        out(m2);
    }
private:
    int m1;
    type m2;
};
.cpp文�g定义
void out(double x){
    cout<<"out_by_class_instantiation_scrope"<}

int main(�Q?br>{
    A a;
    a.test1();
    a.test2();

}

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

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

MEMber function的具现行为：

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

在实现层面上�Q�template ��g��拒绝全面自动化，以手动方式在个别的object module中完成预先的��L��工作是一�U�有效率的方法�?/font>

7.2异常处理

��Z��l�持执行速度�Q�编译器可以在编译时期徏立�v用于支持的数据结�?/font>

��Z��l�持�E�序大小�Q�编译器可以在执行期建立数据�l�构

c++ eH 主要�׃��个部分构成：

throw语句

catch语句

try语句�Q�这些语句可能触发catch子句起作�?/font>

一个exception 被抛出时候，控制权会从函数调用释攑և�来，�q�寻找一个吻合的catch�Q�如果没有那么默认的处理例程terminate()会被调用�Q�控制权攑ּ�后，堆栈中的每一个函数调用也被推��R��每一个函数被推离堆栈的时候，函数的local class object 的dtor也会被调用�?/font>

在程序不同段里，�׃��声明不同的变量，一个区域可能因为在区域内发生exception的处理方式不同分成多个区�D�c�?/font>

在程序员层面�Q�eh也改变了函数在资源上的管理。例如下面函��C��更含有对一块共享内存的locking和unlocking操作 �Q?/font>

void mumble(void * arena){

Point *p= new point ;

smlock(arena) ;

//�?.如果此时一个exception发生�Q�问题就产生�?/font>

sumunlock(arena);

delete p;

}

从语义上�Ԍ��我们在函数退出堆栈之前，需要unlock�׃�n内存�q�delete p�Q�我们需要这样做�Q?/font>

try{smlock(arena)} catch(�?{

    smunlock(arena); delete p; throw;

}

new不需要放在try�D�里�Q�因为，如果new发生了exception�Q�heap中的内存�q�没有分配，point的ctor没有调用�Q�如果在ctor中exception�Q�那么piont的�Q何构造好的合成物也会自动解构掉，heap也会自动释放掉�?/font>

处理�q�种资源��理问题�Q�徏议：把资源需求封装在一个class object 体内�Q��ƈ由dtor释放资源.

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

// 不需要明��的unlock 和delete

// local dtor 会在�q�里被调�?sm.SMlock::~smlock(); ph.auto_ptr::~auto_ptr

Exception handling 的支持：

1.��验发生throw操作的函�?/font>

2.军_��throw是否发生在try区段�?/font>

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

4.��d��的话控制权交�l�catch

5.如果throw不发生在try�D�|��者没有吻合的�Q�系�l�会摧毁所有active local object b从堆栈把当前函数unwind�?�Q�蟩出到�E�序堆栈的下一个函数去�Q�然后重复上�q�步�?/font>

当一个实际对象在�E�序执行时被抛出�Q�exception object会被产生出来�q��常攑֜�相同形式的exception 数据堆栈中�?/font>

catch(expoint p){

   //do sth

   throw;

}

以及一个exception object �c�d��?exVertex �z��?expoint �Q�这两种�c�d��都吻合，catch会怎么�?/font>

以exception object作�ؓ初��|��像函数参��C��样会有一个local copy�Q�如果p是一个object而不是一个reference �Q�内容被拯��的时候，�q�个object的非expoint部分会被切掉�Q�如果有vptr 会被讑֮�为expoint的vptr�Q�如果被再次丢出呢？丢出p需要再产生另外一个exception 临时对象�Q�丢出原来的异常 �Q�之前的修改�l�统作废。但是如�?catch(expoint& p);怎么样呢�?��M��对这个object的改变都会繁�D�到之后的catch语句怅R�?/font>

c++ �~�译器�ؓ了支持EH付出的代��h��大，某种�E�度是因为执行期的天性以及对底层��g的依赖�?/font>

7.3 RTTI

RTTI是Except handling的一个附属��品，因�ؓ我们需要提供某�U�查询exception objects的方法，用来得到exception的实际类型�?/font>

在向下�{型问题上�Q�如果要保证其安全性，那么必须在执行期�Ҏ��针有所查询�Q�看看它到底指向什么类型的对象。那么我们需要额外的�I�间存储�c�d��信息�Q�通常是一个指针，指某个类型信息节炏V�?/font>

需要额外的旉��以决定执行期的类型�?/font>

冲突发生在：

1.�E�序员大量的使用了多収ͼ��q��要大量的downcast操作

2.�E�序员��用内建的数据�c�d��和非多态，他不需要额外负担带来的便利

那么如何了解�E�序员的需要呢�Q�？ �{�略是一个具有多态性性质的class�Q�也��是��h��内涵�l�承或者声�?virtual func的类需要rtti支持�?/font>

�q�样所有多态类�l�护一个vptr。额外负担降低到�Q�每一个class object多花费一个指针，指针只被讑֮�一�ơ，而且是编译器静态设定�?/font>

down_cast

if(pfct pf = dynamic_cast< pfct >(pt))�?

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

Reference --------Pointer

dynamic_cast执行在ptr�?��p�|�q�回0�Q�如果实行在ref上。由于ref不能被赋予null�Q�也��是没有�I�引用。如果我们把一个ref设�ؓ0会引发��时对象��生，然后�?初始化它�Q��ref成�ؓ�q�个临时对象的别名。因此此时失败了会��生一个bad_cast exception�?/font>

typeid的参数可以��引用�Q�对象或者是�c�d��

事实上，type_info 也适用内徏�c�d��Q�这对于eh机制有必�?/font>

例如 int ex_errno; throw ex_errno;

其中int�c�d�� int *ptr; if(typeid(ptr) == typeid(int*));

----------------------全书�W�记到此�l�束 --------------------------------s

rikisand 2010-03-25 21:09 发表评论

微��Y�l�典面试��试题和参考答案（变态） - TOMB RAIDER - CSDNBlog�Q��{载）

rikisand — Mon, 22 Mar 2010 15:21:00 GMT

�W�一�l?

1.烧一根不均匀的��Q�从头烧到尾��d��需�?个小时。现在有若干条材质相同的�l�_��Q�问如何用烧�l�的�Ҏ��来计时一个小时十五分钟呢�Q?br>2.你有一桶果冻，其中有黄艌Ӏ�绿艌Ӏ�红色三�U�，闭上眼睛抓取同种颜色的两个。抓取多��个��可以确定你肯定有两个同一颜色的果冻？
3.如果你有无穷多的��_��一�?公升的提捅，一�?公升的提捅，两只提捅形状上下都不均匀�Q�问你如何才能准��称�?公升的水�Q?br>4.一个岔路口分别通向诚实国和说谎国。来了两个�h�Q�已知一个是诚实国的�Q�另一个是说谎国的。诚实国永远说实话，说谎国永�q�说谎话。现在你要去说谎国，但不知道应该走哪条�\�Q�需要问�q�两个�h。请问应该怎么问？
5.12个球一个天�q�I��现知道只有一个和其它的重量不同，问怎样�U�才能用三次��找到那个球�?3个呢�Q�（注意此题�q�未说明那个球的重量是轻是重�Q�所以需要仔�l�考虑�Q?br>6.�?个点上画10条直�U�，要求每条直线上至��有三个点？
7.在一天的24��时之中�Q�时钟的旉��、分针和�U�针完全重合在一��L��时候有几次�Q�都分别是什么时��_��你怎样��出来的�Q?br>8.怎么��L��?��|��木，使其中�Q意两��|��的距��ȝ��{�？

�W�二�l?

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

�W�三�l?

1.你让工�h��Z��工作7天，回报是一栚w��条，�q�个金条�q�_��成相�q�的7�D�，你必��d��每天�l�束的时候给他们一�D�金条。如果只允许你两�ơ把金条弄断�Q�你如何�l�你的工��Z��费？
2.有一辆火车以每小�?5公里的速度��d��北京直奔�q�州�Q�同时另一辆火车每��时20公里的速度从广州开往北京。如果有一只鸟�Q�以30公里每小时的速度和两辆火车同时启动，从北京出发，��到另一辆�R后就向相反的方向�q�回去飞�Q�就�q�样依次在两辆火车之间来回地飞，直到两辆火�R盔R��。请问，�q�只鸟共飞行了多长的距离�Q?br>3.你有四个装药丸的�|�子�Q�每个药且R��有一定的重量�Q�被污染的药丸是没被污染的药丸的重量+1。只�U�量一�ơ，如何判断哪个�|�子的药被污染了�Q?br>4.门外三个开兛_��别对应室内三盏灯�Q�线路良好，在门外控制开��x��候不能看到室内灯的情况，现在只允许进门一�ơ，��定开兛_��灯的对应关系�Q?br>5.人民币�ؓ什么只�?�?�?�?0的面��|��
6.你有两个�|�子以及50个红色弹球和50个蓝色弹球，随机选出一个罐子，随机选出一个弹球放入罐子，怎么�l�出�U�色弹球最大的选中��Z��Q�在你的计划里，得到�U�球的几率是多少�Q?br>7.�l�你两颗6面色子，可以在它们各个面上刻�?-9��L��一个数字，要求能够用它们拼��Z�Q意一�q�中的日期数�?

�W�四�l?

�W�一�?. 五个��L��抢到�?00颗宝矻I��每一颗都一样大��和价��D��城。他们决定这么分�Q?br>抽签军_��自己的号码（1�?�?�?�?�Q?br>首先�Q�由1��h��出分配方案，然后大家表决�Q�当且仅当超�q�半数的人同意时�Q�按照他的方�?br>�q�行分配�Q�否则将被扔�q�大��喂鲨鱼
如果1��h��后，再由2��h��出分配方案，然后剩下�?��行表冻I��当且仅当��过半数的�h�?br>意时�Q�按照他的方案进行分配，否则��被扔入大�v喂鲨�?br>依此�c�L��
条�g�Q�每个�v盗都是很聪明的�h�Q�都能很理智地做出判断，从而做出选择�?br>问题�Q�第一个�v盗提出怎样的分配方案才能��自己的收益最大化�Q?

�W�二�?. 一道关于飞机加油的问题�Q�已知：
每个飞机只有一个��a��，
飞机之间可以�怺�加��a�Q�注意是�怺��Q�没有加�Ҏ��Q?br>一��a可供一枉��机绕地球飞半圈，
问题�Q?br>��Z��臛_��一枉��机绕地球一圈回到�v飞时的飞机场�Q�至��需要出动几枉��机？�Q�所有飞��Z��同一机场起飞�Q�而且必须安全�q�回机场�Q�不允许中途降落，中间没有飞机场）

�W�三�? 汽�R加��a问题
一辆蝲�?00升的汽�R从A开往1000公里外的B�Q�已知汽车每公里耗��a量�ؓ1升，A处有无穷多的油，其他��M��地点都没有��a�Q�但该�R可以在�Q何地点存放��a以备中�{�Q�问从A到B最��需要多��a

�W�四�? ��h��问题
一�U�杯子，若在�W�N层被摔破�Q�则在�Q何比N高的楼层均会��_��若在�W�M层不��_��则在��M��比M低的楼层均会��_��l�你两个�q�样的杯子，让你�?00层高的楼层中��试�Q�要求用最��的��试�ơ数扑և�恰��y会��杯子破碎的楼层�?

�W�五�? 推理游戏
教授选出两个�?�?的数�Q�把它们的和告诉学生�Ԍ��把它们的�U�告诉学生乙�Q�让他们轮流猜这两个�?br>甲说�Q�“我猜不出�?br>乙说�Q�“我猜不出�?br>甲说�Q�“我猜到了�?br>乙说�Q�“我也猜��C��?br>问这两个数是多少

�W�六�? 病狗问题
一个住宅区内有100户�h�Ӟ��每户人家��M��条狗�Q�每天傍晚大安��在同一个地斚w��狗。已知这些狗中有一部分病狗�Q�由于某�U�原因，狗的��M�h无法判断自己的狗是否是病狗，却能够分辨其他的狗是否有病，现在�Q�上�U�传来通知�Q�要求住户处册��些病狗，�q�且不允许指认他人的狗是病狗�Q�就是只能判断自��q��Q�，�q�了7天之后，所有的病狗都被处决了，问，一共有几只病狗�Q��ؓ什么？

�W�七�? U2合唱团在17分钟内得赶到演唱会场�Q�途中必需跨过一座桥�Q�四个�h从桥的同一端出发，你得帮助他们到达另一端，天色很暗�Q�而他们只有一只手�늭�。一�ơ同时最多可以有两�h一赯��桥，而过桥的时候必��L��有手�늭��Q�所以就得有人把手电�{�带来带去，来回桥两端。手�늭�是不能用丢的方式来传递的。四个�h的步行速度各不同，若两人同行则以较慢者的速度为准。BONO需�?分钟�q�桥,EDGE需�?分钟�q�桥,ADAM需�?分钟�q�桥,LARRY需�?0分钟�q�桥,他们要如何在17分钟内过桥呢�Q?

�W�八�? 监狱里有100个房��_��每个戉K��内有一囚犯。一天，监狱长说�Q�你们狱房外有一�늁��Q�你们在��N��时可以控制这个电灯（熄或亮）。每天只能有一个�h出来��N��Q��ƈ且防风是随机的。如果在有限旉��内，你们中的某�h能对我说�Q�“我敢保证，现在每个人都已经臛_��放过一�ơ风了。”我��放了你们！问囚犯们要采取什么策略才能被监狱长放掉？如果采用了这�U�策略，大致多久他们可以被释放？

�W�五�l?

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

�W�六�l?

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

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

�W�一�l�题�{�案�Q?

1�Q�三根��Q�第一根点燃两端，�W�二根点燃一端，�W�三根不�?br>�W�一根��烧完�Q?0分钟�Q�后�Q�点燃第二根�l�的另一端，�W�二根��烧完�Q?5分钟�Q�后�Q�点燃第三根�l�_��两端�Q�第三根�l�烧完（1��时15分）后，计时完成
2�Q�根据抽屉原理，4�?br>3�Q?升装满；3�?�?升（全注入）�Q?升装满；3�?�?升（�?升）�Q?升倒掉�Q?�?�?升（注入1升）�Q?升装满；3�?�?升；完成�Q�另�Q�可用回溯法�~�程求解�Q?br>4�Q�问其中一人：另外一个�h会说哪一条�\是通往诚实国的�Q�回�{�者所指的那条路必然是通往说谎国的�?br>5�Q?2个球�Q?br>�W�一�ơ：4�Q? 如果�q�了�Q?br> 那么剩下的球中取3攑ַ��?�?个好球放双��Q�称�Q?br>    如果左边重，那么取两个球�U�C��下，哪个重哪个是�ơ品�Q��^的话�W�三个重�Q�是�ơ品�Q�轻的话同理
    如果�q�了�Q�那么剩下一个次品，�q�可�Ҏ��需要称出次品比正品��L��者重
如果不��^�Q?br> 那么不妨讑ַ�辚w��双��轻，��Z��便于说明�Q�将左边4颗称为重球，双��4颗称��球，剩下4颗称为好�?br> 取重�?颗，�ȝ��2颗放在左侧，右侧�?颗好球和一颗轻�?br> 如果左边�?br>      �U�那两颗重球�Q�重的一个次品，�q�的话右边轻球次�?br> 如果双��?br>      �U�左边两颗轻球，�ȝ��一个次�?br> 如果�q?br>      �U�剩下两颗重球，重的一个次品，�q�的话剩下那颗轻球次�?br>13个球�Q?br>�W�一�ơ：4�Q?�Q�如果��^�?br> �?颗球用上面的�Ҏ��仍旧能找出次品，只是不能知道�ơ品是重是轻
如果不��^�Q�同�?br>6�Q?br>o   o   o
o o o
o   o   o
7�Q?br>23�ơ，因�ؓ分针要�{24圈，旉��才能�?圈，而分针和旉��重合两次之间的间隔显�?gt;1��时�Q�它们有23�ơ重合机会，每次重合中秒针有一�ơ重合机会，所以是23��?br>重合旉��可以对照手表求出�Q�也可列方程求出
8�Q?br>在地球表面种树，做一个地球内接的正四面体�Q�内接点即�ؓ所�?

�W�二�l?无标准答�?

�W�三�l?

1. 分成1,2,4三段�Q�第一天给1�Q�第二天�l?取回1�Q�第3天给1�Q�第4天给4取回1�?�Q�第5天给1�Q�第6天给2取回1�Q�第七天�l?
2. 求出火�R盔R��旉��Q�鸟速乘以时间就是鸟飞行的距��?br>3. 四个�|�子中分别取1,2,3,4颗药丸，�U�出比正帔R��多少�Q�即可判断出那个�|�子的药被污�?br>4. 三个开兛_��别：养I��开�Q�开10分钟�Q�然后进屋，暗且凉的为开�?控制的灯�Q�亮的�ؓ开�?控制的灯�Q�暗且热的�ؓ开�?控制的灯
5. 因�ؓ可以�?�Q?�Q?�Q?0�l�合成�Q何需要的货币��|��日常习惯�?0�q�制
6. 题意不理�?..*_*
7. 012345 0126(9)78

�W�四�l?都是很难的题�?

�W�一题：97 0 1 2 0 或�?97 0 1 0 2 �Q�提�C�：可用逆推法求出）

�W�二题：3枉��?架次�Q�飞法：
ABC 3架同时�v飞，1/8处，C�l�AB加满油，C�q�航�Q?/4处，B�l�A加满油，B�q�航�Q�A到达1/2处，C从机场往另一方向起飞�Q?/4处，C同已�l�空油箱的A�q�_��剩余沚w��Q�同时B从机��v飞，AC�?/8处同B�q�_��剩余沚w��Q�刚�?枉��机同时返航。所以是3枉��?架次�?

�W�三题：需要徏立数学模�?br>�Q�提�C�，严格证明该模型最优比较麻烦，但确实可证，大胆猜想是解题关键）
题目可归�l��ؓ求数�?an=500/(2n+1) n=0,1,2,3......的和Sn什么时候大于等�?000,解得n>6
当n=6�Ӟ��S6=977.57
所以第一个中转点��v始位�|�距��Mؓ1000-977.57=22.43公里
所以第一�ơ中转之前共耗��a 22.43*(2*7+1)=336.50�?br>此后每次中�{耗��a500�?br>所以总耗��a量�ؓ7*500+336.50=3836.50�?

�W�四题：需要徏立数学模�?br>题目可归�l��ؓ求自然数列的和S什么时候大于等�?00�Q�解得n>13
�W�一个杯子可能的投掷楼层分别为：14�Q?7�Q?9�Q?0�Q?0�Q?9�Q?7�Q?4�Q?0�Q?5�Q?9�Q?00

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

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

�W�七题：�Q�提�C�：可用图论�Ҏ��解决�Q?br>BONO&EDGE�q�（2分）�Q�BONO��手电带回（1分）�Q�ADAM&LARRY�q�（10分）�Q�EDGE��手电带回（2分）�Q�BONO&EDGE�q�（2分） 2+1+10+2+2=17分钟

�W�八题：
�U�定好一个�h作�ؓ报告人（可以是第一个放风的人）
规则如下�Q?br>1、报告�h��N��的时候开灯�ƈ数开灯次�?br>2、其他�h�W�一�ơ遇到开着灯放风时�Q�将灯关�?br>3、当报告人第100�ơ开灯的时候，��d��监狱长报告，要求监狱长放�?.....
按照概率大约30�q�后�Q?0000天）他们可以被释�?

�W�五�l�无标准�{�案

�W�六�l�部分题参考答案：
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;

rikisand 2010-03-22 23:21 发表评论

深入探烦C++对象模型��M��W�记 (�?

rikisand — Fri, 19 Mar 2010 08:55:00 GMT

执行期语义学 RunTime Semantics

if( yy == xx.getValue() ) �?/font>

X xx; Y yy;

class Y{

public:

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

};

class X{

public:

X(); ~X(); operator Y()const; //重蝲转换�c�d��操作�W?必须成员不能有参��C��能有�q�回��D��l�在 http://m.shnenglu.com/zqsand/archive/2010/03/15/109748.html里面有介�l?/font>

X getValue();

};

看看上面的表辑ּ�怎么执行的~~~

首先�{�号�q�算�W�的参数��定 if(yy.operator==(xx.getValue()));

Y�?= 需要一个Y型的参数�Q�但是getvalue得到的是一个X型的�Q�如果没有X到Y的�{型方法，�q�个式子是错的~ 而恰好X有个�c�d��转换�W�~

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

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

注意在这个过�E�中�Q�我们需要一个��时的Xobject 储存 getValue�q�回�?X temp1 = xx.getValue()

一个class Y object 储存 operator Y()�q�回�?Y temp2 = temp1.operator Y();

一�?int 攄�� {�号�q�回�?nbsp; int tmp3 = yy.operator == (temp2);

最后析构函��C��实施在每一个��时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 �q�存�z�）之前 �Q�所以，如果一个区�D�|��者函数有多个��d��点，那么每一个return ��d��炚w��要插入一个dtor了。因此我们一般尽量放�|�object在��用它的程序区�D�附�q�，节省不必要的对象产生与摧毁操作�?/font>

·全局对象�Q�全局对象如果有ctor或者dtor的话需要静态的初始化操作和内存释放操作。c++中全局对象攑֜�data segment中，如果不明��指定��|��内存内容�?.

但是ctor必须�{�到�E�序startup后才能实施。由于必��d��一个放在datasegment 中的object初始化表辑ּ�evaluate �Q�所以object需要静态初始化

一�U�策略（cfont �?munch�Q?/font>

为每一个需要静态初始化的档案��生一�?nbsp; _sti()函数�Q�内带必要的ctor调用操作或者inline expansions�?�c�M��的��涩会�l�你一个std()函数调用dtor

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

然后cfont在我们的�E�序中安插对 _main _exit 的调用�?最后需要解决的是如何收集各个对象的sti和std。cfont使用了nm命��o �Q?打印出符可��?目标文�g的符可��)�Q�然后munch会搜索所有用sti或者std开头的目标函数�Q�把他们记录��C��个表��|��当main和exit调用时候便利表格即可�?/font>

修改版本的方法是�Q�system V中，coff格式的目标文�Ӟ��验可执行文�g�Q�找出有着_linknodes�q�且内带一个指针指�?sti 和std函数的文�Ӟ��把他们都串联��h��Q�接下来把链表头�l�点讄��Z��个全局的_head object (定义在新�?patch runtime library)�Q�这个library中有一�U�不同的_main _exit 他们会以head��v点，遍历链表�Q�调用sti和std�?/font>

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

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

局部静态对�?/font>

const Matrix& identity(){

static Matrix mat_identity;

return mat_identity;

}

mat_identity的ctor必须只执行一�ơ，mat_identity的dtor必须只执行一��?/font>

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

对象数组�Q?/font>

Points knots[10];

如果Points没有定义ctor和dtor只要分配�I�间卛_��

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

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

array如果�?�Q�数�l�由new分配与heap�Q?vec_new(&knots,sizeof(Point),10,&Point::Point,0);

6.2 new �?delete �q�算�W?

int *pi = new int(5);

执行步骤�Q?/font>

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

*pi = 5;

int *pi;

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

   *pi=5;

delete pi;

if(pi!=0)

__delete (pi);

注意pi�q�不会自动清除�ؓ0�Q?/font>

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);

}

一�U�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];是合法的�Q�但是语�a�要求每次对new的调用必��返回一个独一无二的指针，解决该问题的传统�Ҏ��是传回一个指针，指向默认�?byte的内存区块。所以size被设�?.然后�q�种设计允许使用者提供一个属于自��q��_new_handler() 函数�?/font>

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

针对数组的new 语义�Q?/font>

int *p_array = new int[5];

�q�时�?vec_new()不会真正调用�Q�因为，它的主要功能是把default ctor 实施于class object数组的每个元素��n上。new�q�算�W�会被调用：

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

如果数组的class object 有default ctor vec_new才会被调用�?/font>

Point3d *p_array = new Point3d[10];�~�译�?

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

个别数组构造如果exception发生�Q�dtor被传输给vec_new �Q�已�l�构造的object需要dtor 实施�?/font>

delete 时候，开始需要程序员指定大小�Q�后来编译器开始不适用�E�序员指定的�Q�而是只需要写delete [] ptr 卛_��?/font>

如何记录数组大小呢：

一�U�方法在vecnew�q�回的内存块配置一个额外的word�Q�大��放在其中�?/font>

如果

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

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

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

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

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

实施于数�l�上的dtor是根据交�l�vec_delete()函数的被删除指针�c�d��的dtor�Q�也��是point的dtor�Q�每一个元素大��也被一起传了过厅R�?/font>

如何避免�Q?/font>

避免一个base class 指针指向一个derived class 的数�l�。如果真的要�q�么写看代码�?/font>

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

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

Placement Operator New

有一个重载过的new �q�算�W?需要两个参敎ͼ��c�d��为void*

Point2w *ptw = new(area) Point2w;

其中area指向内存一个区块，用来攄��产生出来的Point2w object.�q�个预先定义好的placement operator new 实现�Ҏ��Q?��获得的指针arena 所指的地址传回卛_��

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

事实上，他执行的另一半工作是�Q�把point2w 的ctor 实施�?arena所指的地址�?/font>

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

-------

p2w->~Point2w;

p2w = new(arena)Point2w;

如果我们�?/font>

delete p2w; p2w = new(arena) Point2w;

delete会释放p2w指向的内�?�׃��下一指��o�q�要用到p2w�Q�我们应该调用dtor�q�保留存储空�?以便再次使用.

�q�有一些关于placement opeator new 的设计问题·��h��看明�?不记了·�?/font>

6.3临时对象 �Q?/font>

c++对��时对象�ƈ无硬性规定，��q��译器抉择�?/font>

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

a+b可以直接构徏于c�?/font>

那么�Ҏ��不��生��时对�?/font>

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

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

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

所�?T c=a+b;�?c=a+b;更有效率

临时对象生命周期�Q?/font>

临时对象被摧毁，应该是对完整表达式求职过�E�的最后一个步骤，该完整表辑ּ�造成临时对象的��?/font>

如果一个��时对象绑定在一个reference上，对象��残留，知道被初始化之reference生命�l�束�Q�或者知道��时对象的声明范畴�l�束�?/font>

rikisand 2010-03-19 16:55 发表评论

欧美中文字幕在线,午夜精品影院,亚洲电影在线播放

win核心�~�程-Chap17-Memory-Mapped Files

Google code jam Round1B

Problem

Input

Output

Limits

Small dataset

Large dataset

Sample

五一前小�l�下

关于new和delete

关于寚w��

USACO 4.2.2 �W�一道网�l�流····

PROGRAM NAME: ditch

INPUT FORMAT

SAMPLE INPUT (file ditch.in)

OUTPUT FORMAT

SAMPLE OUTPUT (file ditch.out)

深入探烦C++对象模型��M���W�记 (�?

微��Y�l�典面试���试题和参考答案（变态） - TOMB RAIDER - CSDNBlog�Q��{载）

深入探烦C++对象模型��M���W�记 (�?

深入探烦C++对象模型��M��W�记 (�?

微��Y�l�典面试��试题和参考答案（变态） - TOMB RAIDER - CSDNBlog�Q��{载）

深入探烦C++对象模型��M��W�记 (�?