Posted on 2006-08-04 19:49
oyjpart 閱讀(222)
評論(0) 編輯 收藏 引用
貪心算法的判斷--矩陣胚
適宜于用貪心策略來求解的許多問題都可以歸結(jié)為在加權(quán)矩陣胚中找一個具有最大權(quán)值的獨立子集的問題，即給定一個加權(quán)矩陣胚，M=（S，I），若能找出一個獨立且具有最大可能權(quán)值的子集A，且A不被M中比它更大的獨立子集所包含，那么A為最優(yōu)子集，也是一個最大的獨立子集。
實際上他就是不斷的貪心一逐漸變成最大獨立子集的，比如kruskal算法 呵呵
struct Record {
string name;
// ...
};
struct name_compare { // 使用"name"作為鍵比較Record
bool operator()(const Record& a, const Record& b) const
{ return a.name<b.name; }
};
void f(vector<Record>& vs)
{
sort(vs.begin(), vs.end(), name_compare());
// ...
}
記得sort的第2個參數(shù)實際上比最后一個要排的元素[還要后一個！] 呵呵
如長為8?? sort(&s[0], &s[8], name_compare());
求3個整數(shù)的余一數(shù)可這樣預(yù)求:4,5,6 4*5*6=120; K*120/4%4=1;(K根據(jù)次式在1-4中窮舉）
在對P類較優(yōu)解問題的求解過程中，貪心策略無疑扮演著重要角色。
精度double?
if seg[j]左端點在seg[i]的右端點之前
明確一點
if( .left <= .right )
c++這里方便一點，沒有精度的麻煩
而C則要(a.left-b.right)<1E-10?什么意思？我覺得c++也要啊！
熟練和恰當(dāng)?shù)厥褂肧TL必須經(jīng)過一定時間的積累，準(zhǔn)確地了解各種操作的時間復(fù)雜度，切忌對STL中不熟悉的部分濫用，因為這其中蘊涵著許多初學(xué)者不易發(fā)現(xiàn)的陷阱。
1、離散數(shù)學(xué)——作為計算機學(xué)科的基礎(chǔ)，離散數(shù)學(xué)是競賽中涉及最多的數(shù)學(xué)分支，其重中之重又在于圖論和組合數(shù)學(xué)，尤其是圖論。
2、數(shù)論——以素數(shù)判斷和同余為模型構(gòu)造出來的題目往往需要較多的數(shù)論知識來解決，這部分在競賽中的比重并不大，但只要來上一道，也足以使知識不足的人冥思苦想上一陣時間。素數(shù)判斷和同余最常見的是在以密碼學(xué)為背景的題目中出現(xiàn)，在運用密碼學(xué)常識確定大概的過程之后，核心算法往往要涉及數(shù)論的內(nèi)容。
3、計算幾何——較常用到的部分包括——線段相交的判斷、多邊形面積的計算、內(nèi)點外點的判斷、凸包等等。計算幾何的題目難度不會很大，但也永遠(yuǎn)不會成為最弱的題。
4、線性代數(shù)——對線性代數(shù)的應(yīng)用都是圍繞矩陣展開的，一些表面上是模擬的題目往往可以借助于矩陣來找到更好的算法。
先說說數(shù)據(jù)結(jié)構(gòu)。掌握隊列、堆棧和圖的基本表達(dá)與操作是必需的，至于樹，我個人覺得需要建樹的問題有但是并不多。（但是樹往往是很重要的分析工具）除此之外，排序和查找并不需要對所有方式都能很熟練的掌握，但你必須保證自己對于各種情況都有一個在時間復(fù)雜度上滿足最低要求的解決方案。說到時間復(fù)雜度，就又該說說哈希表了，競賽時對時間的限制遠(yuǎn)遠(yuǎn)多于對空間的限制，這要求大家盡快掌握“以空間換時間”的原則策略，能用哈希表來存儲的數(shù)據(jù)一定不要到時候再去查找，如果實在不能建哈希表，再看看能否建二叉查找樹等等——這都是爭取時間的策略，掌握這些技巧需要大家對數(shù)據(jù)結(jié)構(gòu)尤其是算法復(fù)雜度有比較全面的理性和感性認(rèn)識。
接著說說算法。算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。這里要說的是，有些初學(xué)者在學(xué)習(xí)這些搜索基本算法是不太注意剪枝，這是十分不可取的，因為所有搜索的題目給你的測試用例都不會有很大的規(guī)模，你往往察覺不出程序運行的時間問題，但是真正的測試數(shù)據(jù)一定能過濾出那些沒有剪枝的算法。實際上參賽選手基本上都會使用常用的搜索算法，題目的區(qū)分度往往就是建立在諸如剪枝之類的優(yōu)化上了。
?常用算法中的另一類是以“相似或相同子問題”為核心的，包括遞推、遞歸、貪心法和動態(tài)規(guī)劃。這其中比較難于掌握的就是動態(tài)規(guī)劃，如何抽象出重復(fù)的子問題是很多題目的難點所在，筆者建議初學(xué)者仔細(xì)理解圖論中一些以動態(tài)規(guī)劃為基本思想所建立起來的基本算法（比如Floyd-Warshall算法），并且多閱讀一些定理的證明，這雖然不能有什么直接的幫助，但是長期堅持就會對思維很有幫助。
extern char *strlwr(char *s);只轉(zhuǎn)換s中出現(xiàn)的大寫字母，不改變其它字符。返回指向s的指針。＃i nclude <string.h>
extern char *strchr(char *s,char c);返回首次出現(xiàn)c的位置的指針，如果s中不存在c則返回NULL。