昨天在PKU上做了一題2187，限時(shí)3s。
算法主要耗時(shí)在多次求不同整數(shù)的平方。
當(dāng)用pow函數(shù)求時(shí)，超時(shí)；
而直接乘才232ms。
相差也太大了吧。
于是就寫了一段代碼來測(cè)試pow的性能
首先產(chǎn)生10000個(gè)隨機(jī)整數(shù)，然后重復(fù)1000次求整數(shù)的平方

下面是測(cè)試結(jié)果：

test a[i]*a[i]
time: 31ms
test pow(a[i], 2.0)
time: 2828ms

所以下次遇到類似情況不再用pow函數(shù)了……

在做PKU2762時(shí)，需要建鄰接表。
于是按部就班寫了下面一個(gè)插入邊到鄰接表中的函數(shù)：

完成完整的程序提交上去，得到結(jié)果
Memory:25796K  Time:375MS
Language:C++  Result:Accepted

再對(duì)比別人的程序
Memory:296K Time:109MS

無論是時(shí)間還是空間都相差很大。
于是就考慮怎么優(yōu)化自己的程序。
第一個(gè)問題：規(guī)模只有1000，為什么會(huì)用那么多內(nèi)存呢？
仔細(xì)一想數(shù)據(jù)是多case的，每次插入新節(jié)點(diǎn)時(shí)都要?jiǎng)討B(tài)創(chuàng)建一個(gè)節(jié)點(diǎn)。
一來動(dòng)態(tài)創(chuàng)建耗時(shí)間，二來每個(gè)case結(jié)束的鄰接表中的節(jié)點(diǎn)沒有釋放，故耗費(fèi)大量?jī)?nèi)存。
然后就想到了下面的算法，首先初始化一塊內(nèi)存Graph use[100*VMAX];這樣每次需要新節(jié)點(diǎn)時(shí)，
就從use中獲取。如果use使用完畢就再動(dòng)態(tài)創(chuàng)建。

依此算法優(yōu)化后，得到的結(jié)果比較滿意
Memory:1000K  Time:218MS
Language:C++  Result:Accepted

發(fā)現(xiàn)用stl中的bitset求子集樹只要短短的幾行代碼
n個(gè)元素有2^n個(gè)子集，
i從0到2^n - 1,
把它換算成二進(jìn)制就分別對(duì)應(yīng)一個(gè)子集。

以前求子集樹都是用回溯法，
今天在topcoder做SRM時(shí)學(xué)到一種求子集樹的新方法：位運(yùn)算。
第一重循環(huán)是枚舉所有子集，共2^n個(gè)，即1 << n個(gè)
第二重循環(huán)求集合所有j個(gè)元素的值，0或1。
求一下1 & (1 << j)的值就可以知道它的原理。