Client 需要一U组件提供一U?FastStringc， 此类h int length() Ҏ
解决ҎQ?/font>
静态链?Q?lg厂商源代码交给 client Q客户将lg代码与client 代码~译q接q行?如果lg代码需要fix bug or update Q则client 端代码需要重新编译连接?而且client软g的不同实例用各自的lg内存对象?/font>
动态链?Q?lg厂商使用DLL形式发放lgQ此时不同的client实例可以׃nlg在内存中的代码段?/font>
DLL的问题：1.导出名称的问?Q?不同的compiler可以使用不同的mangle name 用来区分 c++的函敎ͼ那么使用不同的compiler的client和组件无法链?Q可以用extern “C”解军_局函数名的问题Q?.DEF文g解决导出成员函数的问题）
2.升的问?Q如果组件最初定义ؓ
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对象大小?字节Q现在变?字节Q但是client端按?字节分配对象Q?dll却要向后面的4个字节存入一个指针，行ؓ不可预料Q?/font>
解决q一问题的一U方法便是每ơ发布便更改dll的名字，?.0, 2.0, x.0 {等。但q样比较弱啊Q！
q种问题Ҏ原因是啥呢？
class 的关键在于封装了其中的实现细节，即用L道类提供了哪些服务（ publicҎQ就行了Q不需要管cȝ内部到底使用了哪些成员变量。这样一来，只要接口没变Q类提供功能Q，user可以安心的使用L版本的实C。C++怎么不行呢？C++告诉用户接口的同Ӟ也告诉了用户cȝ实现(对象布局)。比如类对象有多大啊Q每个成员的偏移?具体可以看Inside c++ object model)。知道了q些Q客L使用接口的代码就和DLL中的具体实现紧密的耦合h了，杯具 啊~
咋办呢？ 只要不让client直接创徏FastStringp了，q样client的代码就不会受到FastString实现变化的媄响了。给FastString加一个Wrapperc，内部嵌套一个FastStringQ所有对FastString的调用都fowardl内部的FastString member, 创徏FastString 的Q务在dll斚w完成Qclient只知道Wrapper大小?个字?-指向FastString的指针。这样问题解决了Q但是太ȝ了，所有的接口都要包一?! 而且多了一层调?
q有啥办法么Q?Z保证c++接口cdCq制U别的兼容只能用编译器无关的特性：1.假设复合cd表现形式相同(struct) 2. 传参序相同Q可以用指C符指定3.虚函数调用机制相同，卛_?vtbl ?vptr. Zq些假设Q我们创建的c++接口cL有函数设|ؓ虚函敎ͼ那么不同compilerؓ客户端方法调用生相同的机器代码。定义了接口Q便规定了所有承于他的cȝ内存l构一定与它兼宏V但此时不能告诉用户cȝ定义Q否则重回上面的老\上了。怎么办，只有接口客户无法创徏cȝ定义Q只有export一个创建类对象的函数客户了?nbsp; 同上面的wrapper一P创徏cȝ操作仅仅在dll内部调用Q这意味着实际建造类对象大小和布局的代码与~译实现cȝҎ的代码用同L~译器创?Q即ctor和call ctor的代码由同一~译器同时编译）。由于虚析构函数在vtbl的位|与compiler相关Q所以不能把它设|ؓ虚函敎ͼ只有昄增加一个Delete函数完成析构工作?/font>
OKQ当前我们得到的DLL中只有创建类对象的函数需要用extern “C”export l客P其他的接口中的虚函数是通过虚表讉K的，无需靠符号名字链接?/font>
q一步的Q如果我们要l接口增加一个功能呢Q?如果直接在现有接口中Ҏ声明后加入新?font color="#86bc43">ҎQ那么此Ҏ会出现在vtbl的最后一栏，旧的client不会调用新方法，但是如果新的client讉K老的对象? 不幸的事情发生了Q?q样做的问题在于Q修改公开的接口就打破了对象的装性?/font>
那么增加接口功能只能通过设计一个接口承另一个接口，或者让cȝ承多个接口来实现了。客户可以在q行旉过RTTI来询问对象，支持q个功能不，Ԍ然?QRTTI也是一个compiler相关的东东，好吧Q我们让每个c自己实现RTTIQ也是实现一个dynamic_cast ҎQ?用来自己cast成ؓ自己实现的接口，如果不支持则q回 0 ?/font>
例如Q?/font>
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的时候用了IFastStringQ因为IFastString ?IOut都是从IExtentl承的，写IExtent的话不知道用哪个Q用虚拟l承可以使CFastString对象只有一份IExtentQؓ啥不用呢Q?你懂得。。。跟前面{案一P~译器相兟?/font>
最后一个问题是delete的问题，用户需要记得ؓ每一个对象调用一ơdeleteҎQ而指针cast来cast去，惌得对象被delete没有很难啊！ 怎么办？ 用引用计数吧Q把每个指针当做h生命周期的实体，创徏时候计?+Q销毁时?-Q等?的时候就delete对象?/font>
大功告成Q通过vptr和vtbl的二q制防火墙，我们做到了可重用的二q制lgQ组件变化客h需重新~译 ?/font>
]]>
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 fileQ失败则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 spaceQ系l访?exe的一个区域，那里列出?exe含有的dllQ然后系l利?LoadLibrary for each dlls。系lmap dll时候，如果dll?preferred base address 被占据或者不够大Qdllwill 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.利用内存映射文gQ多个实例可以共享代码和数据。实际上Qfile 是分为多个section Q多个节均对齐于边界。如果一个instance of the app 修改了全局变量Q系l应用了copy-on-write 机制Q复制修改的面Qƈ更新实例的file-mapping view。当我们调试E序时同L事情会发生，debuger modify codeQsys 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ȝ使用一个虚拟空间的区域来倒置文gQ然后告诉把文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 nullq个比较Ҏ
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映射到这个区域。但很iQ当pȝmap时候，pȝ必须知道为physical storage分配什么样的保护属性，W三个参数指明了q些?/font>
后面两个参数指明file的大，ensure enouth physical storage is available for the file-mapping object.
high指明?2位，low指明?2位。如果想创徏一个反应现在文件大的mapQ均?.
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则映到文gN?/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 再启动同一个appQsys 看到file-mapping已经存在了，pȝmaps a view of file a second timeQthis time in the context of the newly created process address space.
像所有内核对象一P有三U方法共享他Q承，命名对象以及赋值handle?/font>
···|件支持的内存映射文g
许多应用E序q行是生数据需要和其他q程׃n如果必须在硬盘徏立文件才可以׃nQ那么效率很低。因此微软提供了由system paging file 支持?file mapping。不需要createfile Q只需要在调用createFilemapping 的时候传q一?INVALID_HANDLE_VALUE 作ؓhFile 参数卛_?映射文g大小同样是由high 和low 参数军_的?/font>
`````E疏提交的内存映射文g
--看来需要把虚拟内存那章一L看了~~~~
]]>
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/finalsThis 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 <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())//依次加入各目录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 <string, node *> 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 <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; //setq回一个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 qo回RI字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 <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++)//遍历所有需要加入的Q然后看是否存在 if (!have.count(*it)) ans++; printf("Case #%d: %d\n", t, ans); } }
]]>
目上：基本弄完了码_是l束了吧Q剩下的工作是好好ȝ下学到的东西Q把架构Q用到的技术都理顺了，方便之后面试回答?
生活上：q半个月gf生病了，嘉定闵行两头跑果然很累，不过q好一直抽I看书。健康很重要~~ 要抓紧锻Dn体了。本׃定要掌握好?
扑֮习：先后W试了摩根it和微软。上周摩根给了电面，全英文的。完全没有思想准备的我正在在闵行gf那里照顾她，手边什么书也没有，目资料也没有，我的处女面就q样“裸着”度q了Q到现在q没有消息，也不知道是不是默剧了?微Y是上周六W试的，也没有消息，sigh~不知道是没改完卷子还是杯具了~~
关于实习的笔试和面试要专门写东西ȝ一下，方便以后查阅?
1-4h假，应该不会有新的安排进来（面试之类的）Q得安排下事?
上周把大话设计模式翻了一遍，利用q几天要仔细的重新过一遍，每一个模式都写代码实践一下?
然后想看看c++标准文档Q这个会很慢Q可以选择性的跌一些东西，d700多页Q看?00就可以了，后面是介l库的。一天看75，?···比较困难·· 力?
其他的就不安排了Q也做不完的?
另外Q之后学的东西，一定要及时用日志记下来Q否则时间长了还要从头学起`````
]]>
事实上，如果我们使用的是自定义类型int char{，或者我们用的是没有内存申Lc，我们使用 delete A;q不会发生什么不好的事情?/font>
q是由delete 的语义决定的。当我们是申请一l对象时候，~译器会加入内存大小信息和此D内存相兌。因此当我们delte A Ӟ~译器会按照内存大小收回分给我们的内存。显Ӟ如果是基本类型或者没有申请内存的情况q样的行为是良好的。但是如果我们在自徏cd中申请了内存~对不P~译器是不知道的Q这些申L内存是内存泄露Q随着E序不断q行Q堆不断地被侵蚀·····
q就是delete的第二个作用Q他会施加析构函数在我们甌的内存上Q如果我们delete AQ只会在W一个上施加Q而如果delete [] A;他会Ҏl中每一个元素进行析构~~
so····
试验很容易做Q写两个c，一个申请内存，一个普通的c，然后循环甌大量数组Q但是用 delete A 形式Q然后看看内存占用就行了
]]>
数据寚wQ是指数据所在的内存地址必须是该数据长度的整数倍。处理器可以直接讉K寚w的数据，而访问未寚w的数据会在内部进行一pd的调_虽然可以正常处理Q但是会降低q行速度。例如一个处理器ȝ宽度?4位，那么地址必须?的倍数Q也是一ơ取?个字节。如果我们可以保证所有double地址都ؓ8的倍数Q那么可以用一个存储器操作来读或者写double了，否则我们可能需要执行两ơ存储器讉KQ因为对象可能位于两?字节存储器块?/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>
未对齐的数据会以不同方式lcpu带来ȝ~
1.如果一个变量被划分C个缓存行Q那么我们需要访问两个缓存行才可以?/font>
2.一些simd指oL要求寚w的指令，对于未对齐的指oQ数据对齐也会媄响这些指令的使用?/font>
]]>
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, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 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
最基本的网l流
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(){//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]<capacity[cur][i]?flow[cur]:capacity[cur][i]); 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<<Edmonds_Karp()<<endl; 70: } 71: int main()
72: { 73: init(); 74: output();75: return 0;
76: }标程Q用贪心法Q寻找一条增q\径的时候不断寻找cap最大的Q未被访问的节点mlocQ然后更新跟mloc盔R的节点flow?/font>
及prenode信息.最后当q行到end时候，更新路径节点capacityQ同时增加max_flow.重复上述q程直到找不到增q\?/font>
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: }
]]>
名字Q?On the cusp of the object model
7.1 Template
Template用的很少Q这节中的有些东西比较晦涩，挑一些能理解的记下吧。剩下的{用的多了再回头来看?/font>
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;
};
~译器看到这L声明Q会有什么动作？Q?/font>
没有。static data 不可?enum 不可?Qenum虽然cd固定Q但他只能和template point class 的某个实体来存取或操作。我们可?point<float>::Status s;
但是不能 point::status s; 因此我们可能xenum抽离C个非模板cM避免多重拯。同样道理，freelist 和chunksize对于E序而言也不可用。必L指定point<float>::freelist.也就是说静态数据成员是和特定类型的cȝ定的而不是泛型的模板cR但是如果定义一个指针不一定会L出相应的c，因ؓ一个指针，q不一定指向一个class object。编译器不需要知道该class 相应的Q何member 或者数据或?/font>
内存布局Q所以没有必要具现。但是如果是定义q初始化一个引用就真的会具现出一个实体，因ؓ不存在空引用?/font>
成员函数q不应该被实体化Q只有当他被调用的时候才需要被L出来?/font>
template<class T>
class mumble{
public: Muble(T t=1024):tt(t){ if(tt!=t)throw ex; }
private: T tt;
};
上面的模板中出现错误有，t=1024 不一定成功，!= 不一定定?/font>
q两个错误只有到L操作l合具体cd才能定出来
~译器面对一个template声明Q在他被一l实际参数具C前，只能实行以有限地错误查，只有特定实体定义之后Q才会发C些与语法无关的但是十分明昄错误Q这是技术上的一大问题?/font>
Template 的名U决议方?/font>
.h文g定义
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文g定义
void out(double x){
cout<<"out_by_class_instantiation_scrope"<<endl;
}int main(Q?br>{
A<double> a;
a.test1();
a.test2();}
按照书中的说法，如果一个函敎ͼ参数cd和type无关的话Q应该取他的scope of template declaration中定义的函数Q而反之取在他的instantiation中的那个。事实上在测试中发现
MSVC ?Q函数定义的册是依照类型的Q如果有合适的函数比如type是doubleQ此时如果定义处或者具现处有double型的函数定义Q那么函数就会决议ؓ那一个定义的~~~
MEMber function的具现行为：
~译器如何确保只有一个vtable产生Q?一U方法是 每一个virtual func地址都放在vtable中，如果取得函数地址Q则表示virtual func 的定义必然出现在E序的某个地点，否则E序无法q接成功。此外该函数只能有一个实体，否则也是q接不成功。那么，把vtable攑֜定义了该class的第一个non-inlineQnonpure virtual function的文件中吧。。（not so clearQ?/font>
在实现层面上Qtemplate g拒绝全面自动化，以手动方式在个别的object module中完成预先的L工作是一U有效率的方法?/font>
7.2异常处理
Zl持执行速度Q编译器可以在编译时期徏立v用于支持的数据结?/font>
Zl持E序大小Q编译器可以在执行期建立数据l构
c++ eH 主要׃个部分构成：
throw语句
catch语句
try语句Q这些语句可能触发catch子句起作?/font>
一个exception 被抛出时候，控制权会从函数调用释攑և来，q寻找一个吻合的catchQ如果没有那么默认的处理例程terminate()会被调用Q控制权攑ּ后，堆栈中的每一个函数调用也被推R每一个函数被推离堆栈的时候，函数的local class object 的dtor也会被调用?/font>
在程序不同段里，׃声明不同的变量，一个区域可能因为在区域内发生exception的处理方式不同分成多个区Dc?/font>
在程序员层面Qeh也改变了函数在资源上的管理。例如下面函C更含有对一块共享内存的locking和unlocking操作 Q?/font>
void mumble(void * arena){
Point *p= new point ;
smlock(arena) ;
//?.如果此时一个exception发生Q问题就产生?/font>
sumunlock(arena);
delete p;
}
从语义上Ԍ我们在函数退出堆栈之前，需要unlock׃n内存qdelete pQ我们需要这样做Q?/font>
try{smlock(arena)} catch(?{
smunlock(arena); delete p; throw;
}
new不需要放在tryD里Q因为，如果new发生了exceptionQheap中的内存q没有分配，point的ctor没有调用Q如果在ctor中exceptionQ那么piont的Q何构造好的合成物也会自动解构掉，heap也会自动释放掉?/font>
处理q种资源理问题Q徏议： 把资源需求封装在一个class object 体内Qƈ由dtor释放资源.
auto_ptr<point> ph (new point); smlock sm(arena);//如果此时exception 没有问题
// 不需要明的unlock 和delete
// local dtor 会在q里被调?sm.SMlock::~smlock(); ph.auto_ptr<point>::~auto_ptr<point>
Exception handling 的支持：
1.验发生throw操作的函?/font>
2.军_throw是否发生在try区段?/font>
3.如果是编译器必须把exception type 拿来和catch比较
4.d的话控制权交lcatch
5.如果throw不发生在tryD|者没有吻合的Q系l会摧毁所有active local object b从堆栈把当前函数unwind?Q蟩出到E序堆栈的下一个函数去Q然后重复上q步?/font>
当一个实际对象在E序执行时被抛出Qexception object会被产生出来q常攑֜相同形式的exception 数据堆栈中?/font>
catch(expoint p){
//do sth
throw;
}
以及一个exception object cd?exVertex z?expoint Q这两种cd都吻合，catch会怎么?/font>
以exception object作ؓ初|像函数参C样会有一个local copyQ如果p是一个object而不是一个reference Q内容被拯的时候，q个object的非expoint部分会被切掉Q如果有vptr 会被讑֮为expoint的vptrQ如果被再次丢出呢？丢出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间存储cd信息Q通常是一个指针，指某个类型信息节炏V?/font>
需要额外的旉以决定执行期的类型?/font>
冲突发生在：
1.E序员大量的使用了多収ͼq要大量的downcast操作
2.E序员用内建的数据cd和非多态，他不需要额外负担带来的便利
那么如何了解E序员的需要呢Q？ {略是一个具有多态性性质的classQ也是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回0Q如果实行在ref上。由于ref不能被赋予nullQ也是没有I引用。如果我们把一个ref设ؓ0会引发时对象生，然后?初始化它Qref成ؓq个临时对象的别名。因此此时失败了会生一个bad_cast exception?/font>
typeid的参数可以引用Q对象或者是cd
事实上，type_info 也适用内徏cdQ这对于eh机制有必?/font>
例如 int ex_errno; throw ex_errno;
其中intcd int *ptr; if(typeid(ptr) == typeid(int*));
----------------------全书W记到此l束 --------------------------------s
]]>
W一l?
1.烧一根不均匀的Q从头烧到尾d需?个小时。现在有若干条材质相同的l_Q问如何用烧l的Ҏ来计时一个小时十五分钟呢Q?br>2.你有一桶果冻，其中有黄艌Ӏ绿艌Ӏ红色三U，闭上眼睛抓取同种颜色的两个。抓取多个可以确定你肯定有两个同一颜色的果冻？
3.如果你有无穷多的_一?公升的提捅，一?公升的提捅，两只提捅形状上下都不均匀Q问你如何才能准称?公升的水Q?br>4.一个岔路口分别通向诚实国和说谎国。来了两个hQ已知一个是诚实国的Q另一个是说谎国的。诚实国永远说实话，说谎国永q说谎话。现在你要去说谎国，但不知道应该走哪条\Q需要问q两个h。请问应该怎么问？
5.12个球一个天qI现知道只有一个和其它的重量不同，问怎样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.中国有多辆汽RQ?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.如果你的生规划中打在5q内受到奖励Q那获取该项奖励的动机是什么？观众是谁Q?br>12.如果微Y告诉你，我们打算投资五百万美元来启动你的投资计划Q你开始什么样商业计划Qؓ什么？
13.如果你能够将全世界的电脑厂商集合在一个办公室里，然后告诉他们被做一件事Q那件事是什么？
W三l?
1.你让工hZ工作7天，回报是一栚w条，q个金条q_成相q的7D，你必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色弹球最大的选中ZQ在你的计划里，得到U球的几率是多少Q?br>7.l你两颗6面色子，可以在它们各个面上刻?-9L一个数字，要求能够用它们拼ZQ意一q中的日期数?
W四l?
W一?. 五个L抢到?00颗宝矻I每一颗都一样大和价D城。他们决定这么分Q?br>抽签军_自己的号码（1????Q?br>首先Q由1h出分配方案，然后大家表决Q当且仅当超q半数的人同意时Q按照他的方?br>q行分配Q否则将被扔q大喂鲨鱼
如果1h后，再由2h出分配方案，然后剩下?行表冻I当且仅当过半数的h?br>意时Q按照他的方案进行分配，否则被扔入大v喂鲨?br>依此cL
条gQ每个v盗都是很聪明的hQ都能很理智地做出判断，从而做出选择?br>问题Q第一个v盗提出怎样的分配方案才能自己的收益最大化Q?
W二?. 一道关于飞机加油的问题Q已知：
每个飞机只有一个a，
飞机之间可以怺加aQ注意是怺Q没有加ҎQ?br>一a可供一枉机绕地球飞半圈，
问题Q?br>Z臛_一枉机绕地球一圈回到v飞时的飞机场Q至需要出动几枉机？Q所有飞Z同一机场起飞Q而且必须安全q回机场Q不允许中途降落，中间没有飞机场）
W三? 汽R加a问题
一辆蝲?00升的汽R从A开往1000公里外的BQ已知汽车每公里耗a量ؓ1升，A处有无穷多的油，其他M地点都没有aQ但该R可以在Q何地点存放a以备中{Q问从A到B最需要多a
W四? h问题
一U杯子，若在WN层被摔破Q则在Q何比N高的楼层均会_若在WM层不_则在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原因，狗的Mh无法判断自己的狗是否是病狗，却能够分辨其他的狗是否有病，现在Q上U传来通知Q要求住户处册些病狗，q且不允许指认他人的狗是病狗Q就是只能判断自qQ，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出来NQƈ且防风是随机的。如果在有限旉内，你们中的某h能对我说Q“我敢保证，现在每个人都已经臛_放过一ơ风了。”我放了你们！问囚犯们要采取什么策略才能被监狱长放掉？如果采用了这U策略，大致多久他们可以被释放？
W五l?
1.某手机厂家由于设计失误，有可能造成甉|寿命比原来设计的寿命短一半（不是冲放甉|
_Q解x案就是免Ҏ换电池或l?0元购买该厂家新手机的折换券。请l所有已购买?br>用户写信告诉解决Ҏ?br>2.一高层领导在参观某博物馆时Q向博物馆馆员小王要了一块明代的城砖作ؓU念Q按国家
规定QQ何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.怎样从顶部开始逐层打印二叉树结Ҏ据？LE?br>14.怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件ƈ考虑I链表）Q?--
15.L写能直接实现int atoi(const char * pstr)函数功能的代码?
---------------------------------------------------------------------------------------
W一l题{案Q?
1Q三根Q第一根点燃两端，W二根点燃一端，W三根不?br>W一根烧完Q?0分钟Q后Q点燃第二根l的另一端，W二根烧完Q?5分钟Q后Q点燃第三根l_两端Q第三根l烧完（1时15分）后，计时完成
2Q根据抽屉原理，4?br>3Q?升装满；3??升（全注入）Q?升装满；3??升（?升）Q?升倒掉Q???升（注入1升）Q?升装满；3??升；完成Q另Q可用回溯法~程求解Q?br>4Q问其中一人：另外一个h会说哪一条\是通往诚实国的Q回{者所指的那条路必然是通往说谎国的?br>5Q?2个球Q?br>W一ơ：4Q? 如果q了Q?br> 那么剩下的球中取3攑ַ??个好球放双Q称Q?br> 如果左边重，那么取两个球UC下，哪个重哪个是ơ品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一ơ：4Q?Q如果^?br> ?颗球用上面的Ҏ仍旧能找出次品，只是不能知道ơ品是重是轻
如果不^Q同?br>6Q?br>o o o
o o o
o o o
7Q?br>23ơ，因ؓ分针要{24圈，旉才能?圈，而分针和旉重合两次之间的间隔显?gt;1时Q它们有23ơ重合机会，每次重合中秒针有一ơ重合机会，所以是23?br>重合旉可以对照手表求出Q也可列方程求出
8Q?br>在地球表面种树，做一个地球内接的正四面体Q内接点即ؓ所?
W二l?无标准答?
W三l?
1. 分成1,2,4三段Q第一天给1Q第二天l?取回1Q第3天给1Q第4天给4取回1?Q第5天给1Q第6天给2取回1Q第七天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?0l合成Q何需要的货币|日常习惯?0q制
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处，ClAB加满油，Cq航Q?/4处，BlA加满油，Bq航QA到达1/2处，C从机场往另一方向起飞Q?/4处，C同已l空油箱的Aq_剩余沚wQ同时B从机v飞，AC?/8处同Bq_剩余沚wQ刚?枉机同时返航。所以是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什么时候大于等?00Q解得n>13
W一个杯子可能的投掷楼层分别为：14Q?7Q?9Q?0Q?0Q?9Q?7Q?4Q?0Q?5Q?9Q?00
W五题：3?Q可严格证明Q?br>设两个数为n1Qn2Qn1>=n2Q甲听到的数为n=n1+n2Q乙听到的数为m=n1*n2
证明n1=3Qn2=4是唯一?br>证明Q要证以上命题ؓ真，不妨先证n=7
1)必要性：
i) n>5 是显然的Q因为n<4不可能，n=4或者n=5甲都不可能回{不知道
ii) n>6 因ؓ如果n=6的话Q那么甲虽然不知道（不确?+4q是3+3Q但是无论是2Q?q是3Q?乙都不可能说不知道（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=10Q那样n又可以分解成8+2Q所以M当n>=8Ӟn臛_可以分解成两U不同的合数之和Q这样乙说不知道的时候，甲就没有理由马上说知道?br> 以上证明了必要?br>2)充分?br> 当n=7Ӟn可以分解?+5?+4
昄2+5不符合题意，舍去Q容易判断出3+4W合题意Qm=12Q证?br>于是得到n=7 m=12 n1=3 n2=4是唯一解?
W六题：7只（数学归纳法证明）
1Q若只有1只病狗，因ؓ病狗Mh看不到有其他病狗Q必然会知道自己的狗是病狗（前提是一定存在病狗）Q所以他会在W一天把病狗处决?br>2Q设有k只病狗的话，会在Wk天被处决Q那么，如果有k+1只，病狗的主人只会看到k只病狗，而第k天没有h处决病狗Q病狗主人就会在Wk+1天知道自q狗是病狗Q于是病狗在Wk+1天被处决
3Q由1Q?Q得Q若有n只病狗，必然在第n天被处决
W七题：Q提C：可用图论Ҏ解决Q?br>BONO&EDGEq（2分）QBONO手电带回（1分）QADAM&LARRYq（10分）QEDGE手电带回（2分）QBONO&EDGEq（2分） 2+1+10+2+2=17分钟
W八题：
U定好一个h作ؓ报告人（可以是第一个放风的人）
规则如下Q?br>1、报告hN的时候开灯ƈ数开灯次?br>2、其他hW一ơ遇到开着灯放风时Q将灯关?br>3、当报告人第100ơ开灯的时候，d监狱长报告，要求监狱长放?.....
按照概率大约30q后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;
]]>
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; //重蝲转换cd操作W?必须成员不能有参C能有q回Dl在 http://www.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有个cd转换W~
if(yy.operator == (xx.getValue().operator Y()))
增加的代码都是编译器默默为我们加上的~~~
注意在这个过E中Q我们需要一个时的Xobject 储存 getValueq回?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 ?munchQ?/font>
为每一个需要静态初始化的档案生一?nbsp; _sti()函数Q内带必要的ctor调用操作或者inline expansions?cM的涩会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>
修改版本的方法是Qsystem V中，coff格式的目标文Ӟ验可执行文gQ找出有着_linknodesq且内带一个指针指?sti 和std函数的文Ӟ把他们都串联hQ接下来把链表头l点讄Z个全局的_head object (定义在新?patch runtime library)Q这个library中有一U不同的_main _exit 他们会以headv点，遍历链表Q调用sti和std?/font>
实际上现在的ELF格式Q有init ?fini两个sectionQ完成静态初始化和释放操作。编译器讑֮的startup函数会完成^台特定的支持
virtual base class 的指针或者引用存取virtual base class subobjectQ是一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_identityQ这样避免如果不被调用也需要构造所有对象。同时编译器引入条g式解析~也就是如果构造了则解析之
对象数组Q?/font>
Points knots[10];
如果Points没有定义ctor和dtor只要分配I间卛_
如果有default ctor Qctor必须实施于每个元素n上~q是由runtime library 完成的?cfont?我们使用vec_new()函数 MS和Sun提供两个函数Q一个用来处?vbs的class 一个处理内带base class 的classQ后者ؓ 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分配与heapQ?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);
注意piq不会自动清除ؓ0Q?/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);
}
一Ulibrary对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上。newq算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发生Qdtor被传输给vec_new Q已l构造的object需要dtor 实施?/font>
delete 时候，开始需要程序员指定大小Q后来编译器开始不适用E序员指定的Q而是只需要写delete [] ptr 卛_?/font>
如何记录数组大小呢：
一U方法在vecnewq回的内存块配置一个额外的wordQ大放在其中?/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是根据交lvec_delete()函数的被删除指针cd的dtorQ也是point的dtorQ每一个元素大也被一起传了过厅R?/font>
如何避免Q?/font>
避免一个base class 指针指向一个derived class 的数l。如果真的要q么写看代码?/font>
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; q样写是不行?/font>//要这样写
for(int i=0;i<3;i++){
point3d * p=&((point3d*)ptr)[i]; //恢复成point3d数组指针
delete p;
}
}Placement Operator New
有一个重载过的new q算W?需要两个参敎ͼcd为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指向的内?׃下一指oq要用到p2wQ我们应该调用dtorq保留存储空?以便再次使用.
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;中，直接传递cq入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>
]]>