枚舉

成都創(chuàng)新互聯(lián)公司長(zhǎng)期為1000+客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為達(dá)日企業(yè)提供專業(yè)的做網(wǎng)站、成都網(wǎng)站建設(shè)，達(dá)日網(wǎng)站改版等技術(shù)服務(wù)。擁有10余年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。

對(duì)于一些簡(jiǎn)單的題目，我們或許不需要用什么太巧妙的方法，只需要把所有的可能性列舉出來，然后逐一試驗(yàn)就可以了。

總的來說，枚舉就是通過列舉所有的可能性進(jìn)行一一判斷檢查。

方法

通過事先把各種可能發(fā)生的事情都列舉一遍，為后面求解提供結(jié)果。

總的來說，兩種方法：

遞歸枚舉，這種方法往往更直觀；

遞推（循環(huán)）枚舉，這種方法往往寫起來更簡(jiǎn)潔。

常見類型

枚舉排列

枚舉子集

優(yōu)化

在某些情況下，直接枚舉可能會(huì)帶來較差的效果，在這種時(shí)候，我們實(shí)際上可以分析題目，根據(jù)題目的一些性質(zhì)或特點(diǎn)去除大部分的列舉，減小枚舉量，從而提高枚舉的效率。

搜索

搜索，某種意義上就是對(duì)于枚舉算法的一種改進(jìn)，通過在枚舉的過程中，不斷排除一些不可能達(dá)到的情況，從而達(dá)到優(yōu)化復(fù)雜度的效果。

深度優(yōu)先搜索（DFS）

深度優(yōu)先搜索的思想就是：從一個(gè)頂點(diǎn)沿一條路一直走，如果發(fā)現(xiàn)到不了目標(biāo)節(jié)點(diǎn)，則返回上一個(gè)節(jié)點(diǎn)，沿另一條路一直走到底。

總的來說，DFS就是一個(gè)一個(gè)處理到底，發(fā)現(xiàn)無法得到結(jié)果之后，逐步返回尋求其它的出路。

DFS的應(yīng)用并不局限于一般的圖上，其往往用于一些狀態(tài)圖上。

剪枝

指通過過程當(dāng)中的一些量確定不可行或不符合最優(yōu)的情況。

寬度優(yōu)先搜索（BFS）

寬度優(yōu)先搜索的核心思想在于：首先訪問起始節(jié)點(diǎn)的所有鄰接點(diǎn)，然后再訪問較遠(yuǎn)的區(qū)域，逐步擴(kuò)大范圍，直到找到目標(biāo)節(jié)點(diǎn)。

BFS也主要運(yùn)用于處理狀態(tài)圖，尤其在一些尋求最優(yōu)方案的題目中有較大的用處。

BFS處理不含邊權(quán)的圖的求解最短路徑問題非常有效。

兩種方法的優(yōu)缺點(diǎn)

深度優(yōu)先搜索，優(yōu)點(diǎn)在于能較高效地逼近解，缺點(diǎn)在于初始遞歸方向錯(cuò)誤會(huì)帶來很嚴(yán)重后果；

寬度優(yōu)先搜索，優(yōu)點(diǎn)在于能迅速找到答案不算大的解，缺點(diǎn)在于解答案較大時(shí)所耗時(shí)間與空間都比較大。

迭代加深搜索

在綜合以上兩種算法之后，出現(xiàn)了一個(gè)折中的方法：

通過限定下界k，然后先深度優(yōu)先搜索k層，如果仍沒有找到有效解，則增大下界。

這個(gè)方法的優(yōu)點(diǎn)在于：相對(duì)于深度優(yōu)先搜索并沒有大很多的時(shí)間開銷，但能部分解決深度優(yōu)先搜索的局限，沒有寬度優(yōu)先搜索一般的大空間需求。

分治

分治算法的基本思想：將一個(gè)較大規(guī)模的問題分成多個(gè)（一般是2個(gè)）較小規(guī)模的互相獨(dú)立且與原問題相同的子問題，那么只需要通過對(duì)子問題的求解，就可以得到原問題的解。

往往子問題會(huì)采取相同的方法繼續(xù)分治下去，因此分治算法一般會(huì)采取遞歸的方式表現(xiàn)。

步驟

分解：將要解決的問題劃分成若干規(guī)模較小的同類問題；

求解：當(dāng)子問題劃分得足夠小時(shí)，用較簡(jiǎn)單的方法解決；

合并：按原問題的要求，將子問題的解逐層合并構(gòu)成原問題的解。

應(yīng)用

二分查找

歸并排序

快速冪

貪心

貪心算法指的是在對(duì)問題求解過程中，總是做出目前來看最優(yōu)的選擇，也就是說貪心算法不會(huì)考慮全局最優(yōu)解，只會(huì)不斷考慮局部最優(yōu)解。

但是，我們需要注意到，局部最優(yōu)解不一定就是全局最優(yōu)解。

貪心算法往往可以以較低的代碼復(fù)雜度與時(shí)間復(fù)雜度而得到較優(yōu)的結(jié)果，對(duì)于求解近似值的作用很大。

而對(duì)于相當(dāng)一部分需要求解最優(yōu)值的問題，我們會(huì)發(fā)現(xiàn)通常可以采用動(dòng)態(tài)規(guī)劃或者網(wǎng)絡(luò)流的方法取代貪心算法。

考試技巧

STL

STL 是“Standard Template Library”的縮寫，中文譯為“標(biāo)準(zhǔn)模板庫”。

#include<algorithm>

#include<bits/stdc++.h>（推薦）

sort()

sort函數(shù)用于給一個(gè)數(shù)組進(jìn)行排序,在algorithm庫里。

使用方法為sort(v.begin(),v.end(),cmp)),這里的v.begin()是開始的指針位置，v.end()是結(jié)束的指針位置（這里的表示是左閉右開，也就是說v.end()并不在排序內(nèi)容里），cmp可要可不要，如果使用的是自定義類型且沒有重載運(yùn)算符就一定需要。

這個(gè)數(shù)組的類型可以是自定義類型或者STL中的vector，需要注意的是如果采用的是自定義類型則需要重載運(yùn)算符（也可以如上面說的一樣用cmp）。

stack

模擬棧，在<stack>里。

stack <Type> A;

常用函數(shù)

A.push(a)；

入棧

A.pop()；

出棧

A.top()；

返回棧頂元素（但不出棧）

queue

模擬隊(duì)列，在<queue>里。

queue <Type> A;

常用函數(shù)

A.push(a)；

入隊(duì)

A.pop()；

出隊(duì)

A.front()；

返回隊(duì)首元素（但不出隊(duì)）

deque

雙端隊(duì)列

priority queue

優(yōu)先隊(duì)列，一個(gè)類似于堆的數(shù)據(jù)結(jié)構(gòu),在<queue>里。

默認(rèn)是大根堆，如果想讓他是小根堆的話有兩種辦法，其中一種是重載小于號(hào)。

能以O(shè)(logN)復(fù)雜度完成插入元素，刪除最值，尋找最值。

Priority_queue <Type> A;

常用函數(shù)

A.push(a)；

插入

A.pop()；

刪除最值（默認(rèn)為最大值）

A.top()；

返回最值（但不刪除）

pair

一個(gè)包含兩個(gè)可以不同的數(shù)據(jù)值的類型。

pair <Type1,Type2> A;

往往Type1,Type2都是標(biāo)準(zhǔn)類型，但如果是自定義類型，需要重定義運(yùn)算符；

常用函數(shù)

賦值:make_pair(t1,t2)；

返回對(duì)應(yīng)的值:A.first,A.second；

vector

向量（Vector）是一個(gè)封裝了動(dòng)態(tài)大小數(shù)組的順序容器。跟任意其它類型容器一樣，它能夠存放各種類型的對(duì)象?？梢院?jiǎn)單的認(rèn)為，向量是一個(gè)能夠存放任意類型的不定長(zhǎng)的動(dòng)態(tài)數(shù)組，在vector庫里。

定義方式:vector <Type> A；

容器特性

順序序列

順序容器中的元素按照嚴(yán)格的線性順序排序。可以通過元素在序列中的位置訪問對(duì)應(yīng)的元素。

動(dòng)態(tài)數(shù)組

支持對(duì)序列中的任意元素進(jìn)行快速直接訪問，甚至可以通過指針?biāo)闶鲞M(jìn)行該操作。提供了在序列末尾相對(duì)快速地添加/刪除元素的操作。

能夠感知內(nèi)存分配器的（Allocator-aware）

容器使用一個(gè)內(nèi)存分配器對(duì)象來動(dòng)態(tài)地處理它的存儲(chǔ)需求。

相當(dāng)于是個(gè)動(dòng)態(tài)數(shù)組，每次可以往末端插入一個(gè)元素，下標(biāo)從0開始。

實(shí)現(xiàn)方式是每次不夠大的時(shí)候暴力倍長(zhǎng)，可以發(fā)現(xiàn)均攤是線性的。

常用操作

A.clear()；

清空

A.push_back(a)；

尾部添加元素

A.pop_back()；

尾部刪除元素

A.empty()；

檢查是否為空，空返回true

v.size()

這個(gè)一個(gè)unsigned int類型。也就是說對(duì)空的vector的size()-1會(huì)得到2^32-1。因此寫代碼的時(shí)候應(yīng)帶盡量避免這種寫法。（或者強(qiáng)制類型轉(zhuǎn)化成int）

v.resize()

其復(fù)雜度是O(max(1, resize()中的參數(shù)-原來的size()))的。

如果是大小變大的resize()，且可以指定新擴(kuò)展的位置的值。若未指定則調(diào)用其默認(rèn)構(gòu)造函數(shù)，例如int之類的會(huì)默認(rèn)是0。

v.clear()和vector<int>().swap(v)的區(qū)別。

前者是假裝清空了，實(shí)際內(nèi)存沒有被回收。

后者是真的回收了，不過需要和v.size()的大小成正比的時(shí)間。

后者的意思是使用vector<>()這句話調(diào)用無參的構(gòu)造函數(shù)生成一個(gè)vector<>類型的對(duì)象，然后和v交換，之后其生存期結(jié)束被銷毀會(huì)自動(dòng)調(diào)用其~vector<>()析構(gòu)函數(shù)。注意<>里面要寫v一樣的類型（例如int）

set

一個(gè)存儲(chǔ)集合的容器，在set庫里。

map相當(dāng)于是一個(gè)下標(biāo)可以是任何數(shù)值的數(shù)組，如果訪問時(shí)沒有賦值就會(huì)返回零。

內(nèi)部使用紅黑樹（一種平衡樹）實(shí)現(xiàn)。

當(dāng)set<>中的第一個(gè)參數(shù)是自定義類型的時(shí)候需要重新定義小于號(hào)。

復(fù)雜度基本上是O(log(當(dāng)前大小))。

定義方式:set <Type> A；

常用函數(shù)

A.insert(a)；

插入a

A.erase(a)；

刪除a:

A.find(a)；

查找a，如果查找成功，返回對(duì)應(yīng)指針，查找失敗返回尾指針

A.begin(),A.end()；

返回頭指針與尾指針，尾指針不存儲(chǔ)具體內(nèi)容

map

存儲(chǔ)一個(gè)從key到value的映射。某種意義上就是“廣義”數(shù)組，在map庫里。

map相當(dāng)于是一個(gè)下標(biāo)可以是任何數(shù)值的數(shù)組，如果訪問時(shí)沒有賦值就會(huì)返回零。

內(nèi)部使用紅黑樹（一種平衡樹）實(shí)現(xiàn)。

當(dāng)map<,>中的第一個(gè)參數(shù)是自定義類型的時(shí)候需要重新定義小于號(hào)。

復(fù)雜度基本上是O(log(當(dāng)前大小))

map <Type1,Type2> A;Type1是key類型，Type2是value類型。

可以通過A[B]=C這種形式賦值，B為Type1，C為Type2。

常用函數(shù)

A.clear()；

清空

A.empty()；

判斷是否為空

A.insert(pair<Type1，Type2> (C,D))；

插入（不建議這么寫）

A.erase(B)；

刪除，B可以是key值也可以是指針

A.begin(),A.end()；

頭指針，尾指針

m[x]

哪怕你什么也不干只寫一個(gè)m[x];也會(huì)新建一個(gè)點(diǎn)。

因此當(dāng)你想知道m(xù)ap中是否存在這個(gè)映射的時(shí)候最好使用m.count(x)。

很多時(shí)候可以有效卡常。

multiset和multimap

是可重集合和可重映射。

有兩個(gè)注意的：第一個(gè)是count函數(shù)復(fù)雜度變成了O(lg(集合大小)+答案)的，也就是如果有很多相同元素，那么count函數(shù)代價(jià)很大。

第二個(gè)是刪除x的話，使用s.erase(x)會(huì)把所有權(quán)值為x的刪除。

如果只想刪掉一個(gè)需要s.erase(s.find(x))。

unordered_set和unordered_map

基于哈希實(shí)現(xiàn)的集合和映射。

基本上里面的類型只能是int,long long,double這種非自定義類型。 因?yàn)槠浠诠＃?/p>

在c++11及以后存在，之前沒有，亂用可能會(huì)CE。

空間常數(shù)比較大，時(shí)間常數(shù)不小，比數(shù)組訪問慢很多，慎用。

不能順序遍歷，不支持lower_bound。

迭代器

只介紹set/map的迭代器。

bitset

高精度壓位二進(jìn)制。

一個(gè)用于處理二進(jìn)制串的“數(shù)組”,在<bitset>里。

所有時(shí)間復(fù)雜度是線性的操作，常數(shù)都是1/32大概。

下標(biāo)從0開始。

bitset <n> A;//n為長(zhǎng)度；

支持所有位運(yùn)算： << , >> , & , | , ^ ；

常用函數(shù)

A.count()；

統(tǒng)計(jì)1的個(gè)數(shù)

A.reset()；

清0

A.set()；

全賦為1

A.size()；

返回位數(shù)

lower bound()/upper bound()

lower_bound(v.begin(),v.end(),c)可以在一個(gè)有序數(shù)組當(dāng)中找出剛好大于或等于c的數(shù)，在algorithm庫里,可以使用自定義類型，用法與sort相類似。

upper_bound函數(shù)類似，這個(gè)函數(shù)則是在有序數(shù)組中找出剛好大于c的數(shù)。

next permutation/prev permutation(全排列算法)

algorithm頭文件中包含了next_permutation(v.begin(),v.end())和prev_permutation(v.begin(),v.end())兩個(gè)全排列函數(shù)，分別給出一個(gè)序列在全排列中的下一個(gè)和上一個(gè)序列(按字典序)，如果存在這樣的序列則返回true，不存在則返回false，但仍會(huì)得到一個(gè)序列。

對(duì)于一個(gè)任意元素不相同的序列來說，正序排列是最小的排列方式，相應(yīng)的逆序排列是最大的排列方式，以整數(shù)序列{1,2,3}為例，{1,2,3}是第一個(gè)排列，{3,2,1}則是最后一個(gè)排列，因此序列{1,2,3}沒有上一個(gè)序列，{3,2,1}沒有下一個(gè)序列。

pq.swap(pq2)

優(yōu)先打暴力

考試中經(jīng)常會(huì)遇到想到正確解法卻由于寫錯(cuò)導(dǎo)致分?jǐn)?shù)掛零的現(xiàn)象，為了應(yīng)付這種情況，我們可以優(yōu)先寫暴力程序，一來做分?jǐn)?shù)保障，二來可以為對(duì)拍做準(zhǔn)備。

多貪心原則

當(dāng)一些題目的正解想不出來，并且一個(gè)貪心原則效果不好的情況下，可以采取多個(gè)貪心原則同時(shí)用，然后取最優(yōu)的方案。（時(shí)間問題一般不用貪心，因?yàn)樨澬乃惴〞r(shí)間復(fù)雜度往往比較?。?/p>

特判

有些時(shí)候在想不到正解的情況下，可以通過判斷一些特殊情況得到部分分；有些情況雖然想到了正解，卻忽略了一些特殊情況，也無法得全分。

打表

有一些題目，看上去非常復(fù)雜，但是我們實(shí)際上可以通過打表看出規(guī)律或者可能性不多，可以直接通過打表得到答案。

補(bǔ)充

基本位運(yùn)算

位與（&）

給定兩個(gè)長(zhǎng)度相同的二進(jìn)制串A、B（不同則在前面補(bǔ)0），A與B的結(jié)果的每一位由A與B的對(duì)應(yīng)位決定，如果A與B的對(duì)應(yīng)位均為1，則結(jié)果的那一位為1，否則為0。

位或（|）

A或B的結(jié)果的每一位同樣由A與B的對(duì)應(yīng)位決定，如果A或B的對(duì)應(yīng)位為1，則結(jié)果的那一位為1，否則為0。

位異或（xor）

A異或B的結(jié)果的每一位同樣由A與B的對(duì)應(yīng)位決定，如果A與B的對(duì)應(yīng)位不相同，則結(jié)果的那一位為1，否則為0。

左移（<<）

a<<b,左移，b以10進(jìn)制表示。表示將a的最右邊（最低位）加上b個(gè)0。（相當(dāng)于乘上了2?）。

右移（>>）

a>>b,右移，b以10進(jìn)制表示。表示將a最右面（最低位）的b位刪掉。（相當(dāng)于整除2?）。

并非原創(chuàng)，僅是整理，請(qǐng)見諒

當(dāng)前題目：noip基礎(chǔ)算法
分享鏈接：http://chinadenli.net/article38/dsoihsp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、網(wǎng)站建設(shè)、微信公眾號(hào)、小程序開發(fā)、微信小程序、網(wǎng)頁設(shè)計(jì)公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)