算法合集之《論C語(yǔ)言在信息學(xué)競(jìng)賽中的應(yīng)用》

論C++語(yǔ)言在信息學(xué)競(jìng)賽中的應(yīng)用浙江省余姚中學(xué)韓文弢關(guān)于信息學(xué)競(jìng)賽信息學(xué)競(jìng)賽一般要求在一定的時(shí)間內(nèi)，理解并分析題意，設(shè)計(jì)符合給定時(shí)間和空間復(fù)雜度要求的算法，并在計(jì)算機(jī)上使用一定的程序設(shè)計(jì)語(yǔ)言正確地實(shí)現(xiàn)算法。由于整個(gè)競(jìng)賽存在時(shí)間限制，因此所使用的程序設(shè)計(jì)語(yǔ)言能否正確、快速地實(shí)現(xiàn)算法對(duì)競(jìng)賽的成績(jī)影響頗大。關(guān)于信息學(xué)競(jìng)賽所以，編程復(fù)雜度成為和算法的時(shí)間以及空間復(fù)雜度同等重要的因素。編程復(fù)雜度在很大程度上與所選用的程序設(shè)計(jì)語(yǔ)言有關(guān)。一般信息學(xué)競(jìng)賽中比較常用的程序設(shè)計(jì)語(yǔ)言有BASIC、Pascal、C++、Java等。信息學(xué)競(jìng)賽中常用語(yǔ)言的特點(diǎn)BASICPascalC++Java學(xué)習(xí)難度容易一般較難較難語(yǔ)言特點(diǎn)簡(jiǎn)單嚴(yán)謹(jǐn)靈活高度面向?qū)ο筮\(yùn)行速度慢較快快慢庫(kù)的功能弱一般很強(qiáng)強(qiáng)中學(xué)信息學(xué)競(jìng)賽的語(yǔ)言現(xiàn)狀BASIC語(yǔ)言正逐漸被淘汰。 ↘Pascal語(yǔ)言使用較為廣泛，基本保持穩(wěn)定。 →C++語(yǔ)言憑借其本身所具有的高度的靈活性，以及它所帶的庫(kù)的強(qiáng)大功能，被越來(lái)越多的選手所使用。 ↗本文的目的和結(jié)構(gòu)目的：使讀者在掌握Pascal語(yǔ)言的前提下，能盡快地掌握C++語(yǔ)言，并在此基礎(chǔ)上進(jìn)一步深入C++語(yǔ)言的高級(jí)應(yīng)用。結(jié)構(gòu)：1從Pascal到C++2深入C++語(yǔ)言3STL簡(jiǎn)介3STL簡(jiǎn)介閱讀本章的必要條件：了解C++面向?qū)ο蟪绦蛟O(shè)計(jì)的基礎(chǔ)知識(shí)、了解一定的算法知識(shí)本章的結(jié)構(gòu)：3.1STL概述3.2迭代器3.3算法3.4容器3.5本章小結(jié)3.1STL概述一般化編程一般化編程(genericprogramming)的提出void

swap(int&

x,

int&

y)

{

int

t

=

x;

x

=

y;

y

=

t;

}模板函數(shù)模板函數(shù)template<class

T>

void

swap(T&

x,

T&

y)

{

T

t

=

x;

x

=

y;

y

=

t;

}模板函數(shù)的調(diào)用模板函數(shù)的調(diào)用隱式調(diào)用swap(x,

y);顯式調(diào)用swap<int>(x,

y);模板類(lèi)模板類(lèi)template<class

T,

int

max>

struct

c_array

{

typedef

T

value_type;

typedef

T&

reference;

typedef

const

T&

const_reference;

T

v[max];

operator

T*();

reference

operator

[](size_t

i);

const_reference

operator

[](size_t

i)

const;

size_t

size()

const;

};模板類(lèi)的使用模板類(lèi)的使用c_array<int,

100>

a;c_array<double,

20>

b;c_array<c_array<int,

10>,

10>

c;STL概述STL就是建立在模板函數(shù)和模板類(lèi)基礎(chǔ)之上的功能強(qiáng)大的庫(kù)模板函數(shù)可以實(shí)現(xiàn)一般化的常用算法（如統(tǒng)計(jì)、排序、查找等）模板類(lèi)可以實(shí)現(xiàn)支持幾乎所有類(lèi)型的容器，用來(lái)實(shí)現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)（如鏈表、棧、隊(duì)列、平衡二叉樹(shù)等）STL頭文件一覽頭文件內(nèi)容頭文件內(nèi)容<iterator>迭代器<vector>向量<utility>輔助功能<deque>雙頭隊(duì)列<memory>內(nèi)存管理<list>鏈表<algorithm>算法<set>集合與多重集合<functional>函數(shù)對(duì)象<map>映射與多重映射<numeric>數(shù)值運(yùn)算<stack>棧<queue>隊(duì)列與優(yōu)先隊(duì)列3.2迭代器迭代器的定義和種類(lèi)迭代器(iterator)實(shí)際上是一種一般化的指針類(lèi)型，是對(duì)指針類(lèi)型的抽象。根據(jù)所支持操作的不同，迭代器被分為五大類(lèi)：輸出迭代器(inputiterator)輸入迭代器(outputiterator)前向迭代器(forwarditerator)雙向迭代器(bidirectionaliterator)隨機(jī)迭代器(randomaccessiterator)各種迭代器的功能迭代器類(lèi)型輸出迭代器輸入迭代器前向迭代器雙向迭代器隨機(jī)迭代器縮寫(xiě)OutInForBiRan讀取不支持x=*px=*px=*px=*p操作不支持p->xp->xp->xp->xp[i]寫(xiě)入*p=x不支持*p=x*p=x*p=x迭代++++++++--++--+-+=-=比較不支持==!===!===!===!=<><=>=更多關(guān)于迭代器的信息指針類(lèi)型就是一種特殊的隨機(jī)迭代器類(lèi)型。對(duì)于一般的迭代器，這些功能都是通過(guò)操作符重載來(lái)實(shí)現(xiàn)的。更多關(guān)于迭代器的信息各種迭代器類(lèi)型之間的關(guān)系：迭代器的作用訪(fǎng)問(wèn)元素算法與容器之間的紐帶輸出迭代器輸入迭代器前向迭代器雙向迭代器隨機(jī)迭代器模板類(lèi)pairtemplate<class

T1,

class

T2>

struct

pair

{

typedef

T1

first_type;

typedef

T2

second_type;

T1

first;

T2

second;

pair()

:

first(T1()),

second(T2())

{

}

pair(const

T1&

x,

const

T2&

y)

:

first(x),

second(y)

{

}

template<class

U,

class

V>

pair(const

pair<U,

V>&

p)

:

first(p.first),

second(p.second)

{

}

};模板類(lèi)pairtemplate<class

T1,

class

T2>

pair<T1,

T2>

make_pair(const

T1&

x,

const

T2&

y)

{

return

pair<T1,

T2>(x,

y);

}作用儲(chǔ)存一對(duì)密切相關(guān)的值使用在當(dāng)算法需要返回兩個(gè)值時(shí)作為映射的元素類(lèi)型（關(guān)鍵字和被映射的值）3.3算法與算法有關(guān)的知識(shí)算法(algorithm)每個(gè)算法都是一個(gè)或者一組模板函數(shù)，用來(lái)完成一項(xiàng)特定的操作。序列(sequence)序列用兩個(gè)迭代器來(lái)描述，表示一組連續(xù)的元素；其中，第一個(gè)迭代器指向序列中的第一個(gè)元素，第二個(gè)迭代器指向序列最后一個(gè)元素的后一個(gè)位置。與算法有關(guān)的知識(shí)函數(shù)對(duì)象(functionobject)函數(shù)對(duì)象重載了函數(shù)調(diào)用操作符(operator())，可以像普通函數(shù)一樣被使用。謂詞(predicate)返回值類(lèi)型為bool的函數(shù)對(duì)象函數(shù)對(duì)象舉例template<class

T>

class

Sum

{

T

res;

public:

Sum(T

i

=

T())

:

res(i)

{

}

void

operator

()(const

T&

x)

{

res

+=

x;

}

T

result

const

{

return

res;

}

};常用函數(shù)對(duì)象STL在頭文件<functional>中提供了一些常用運(yùn)算的函數(shù)對(duì)象。類(lèi)名類(lèi)型作用equal_to雙目arg1==arg2not_equal_to雙目arg1!=arg2greater雙目arg1>arg2less雙目arg1<arg2greater_equal雙目arg1>=arg2less_equal雙目arg1<=arg2logical_and雙目arg1&&arg2logical_or雙目arg1||arg2logical_not單目!argplus雙目arg1+arg2minus雙目arg1-arg2multiplies雙目arg1*arg2divides雙目arg1/arg2modulus雙目arg1%arg2negate單目-argSTL算法一覽訪(fǎng)問(wèn)元素類(lèi)for_each(),transform()順序查找類(lèi)find(),find_if(),find_first_of(),adjacent_find(),search(),find_end(),search_n()統(tǒng)計(jì)類(lèi)count(),count_if()STL算法一覽比較類(lèi)mismatch(),equal(),lexicographical_compare()復(fù)制類(lèi)copy(),copy_backward()交換類(lèi)swap(),iter_swap(),swap_ranges()STL算法一覽替換類(lèi)replace(),replace_if(),replace_copy(),replace_copy_if()填充發(fā)生類(lèi)fill(),fill_n(),generate(),generate_n()刪除類(lèi)remove(),remove_if(),remove_copy(),remove_copy_ifSTL算法一覽去重類(lèi)unique(),unique_copy()反轉(zhuǎn)類(lèi)reverse(),reverse_copy()旋轉(zhuǎn)類(lèi)rotate(),rotate_copy()隨機(jī)打亂類(lèi)random_shuffle()STL算法一覽排序類(lèi)sort(),stable_sort(),partial_sort(),partial_sort_copy(),nth_element()二分查找類(lèi)lower_bound(),upper_bound(),equal_range(),binary_search()合并類(lèi)merge(),inplace_merge()STL算法一覽分區(qū)類(lèi)partition(),stable_partition()集合運(yùn)算類(lèi)includes(),set_union(),set_intersection(),set_difference(),set_symmetric_difference()堆操作類(lèi)make_heap(),push_heap(),pop_heap(),sort_heap()STL算法一覽最大最小類(lèi)min(),max(),min_element(),max_element()排列類(lèi)next_permutation(),prev_permutation()數(shù)值運(yùn)算類(lèi)accumulate(),inner_product(),partial_sum(),adjacent_difference()常用算法介紹（排序）排序算法原型template<class

Ran>

void

sort(Ran

first,

Ran

last);

template<class

Ran,

class

Cmp>

void

sort(Ran

first,

Ran

last,

Cmp

cmp);時(shí)間復(fù)雜度：平均O(nlogn)，最壞O(n2)使用舉例sort(a,

a

+

n);sort(b,

b

+

m,

greater<int>());常用算法介紹（二分查找）二分查找算法原型：template<class

For,

class

T>

bool

binary_search(For

first,

For

last,

const

T&

val);template<class

For,

class

T>

For

lower_bound(For

first,

For

last,

const

T&

val);template<class

For,

class

T>

For

upper_bound(For

first,

For

last,

const

T&

val);template<class

For,

class

T>

pair<For,

For>

equal_range(For

first,

For

last,

const

T&

val);時(shí)間復(fù)雜度：隨機(jī)迭代器O(logn)，其他O(n)常用算法介紹（二分查找）算法的要求序列有序查找的謂詞與排序的謂詞相同算法的作用binary_search()返回val是否在序列中。lower_bound()返回指向序列中第一個(gè)大于或等于val的元素的迭代器。upper_bound()返回指向序列中第一個(gè)大于val的元素的迭代器。equal_range()返回一個(gè)pair，表示序列中與val相等的元素所構(gòu)成的子序列。算法的組合使用例如，要對(duì)一組范圍較大的整數(shù)進(jìn)行離散化，步驟如下：用sort()排序；用unique()去掉重復(fù)的元素；對(duì)于每個(gè)整數(shù)，用lower_bound()查找在序列中的位置。例題：最長(zhǎng)單調(diào)遞增子序列題目描述給定一個(gè)長(zhǎng)度為n的整數(shù)序列A={a1,a2,...,an}，求一個(gè)最大的整數(shù)m，使得存在另一個(gè)序列P={p1,p2,...,pm}，滿(mǎn)足，且。約束條件n不超過(guò)30,000ai在[0,1,000,000,00)的區(qū)間內(nèi)思路分析原算法設(shè)fi表示結(jié)尾元素為原序列中第i個(gè)元素的最長(zhǎng)單調(diào)遞增序列的長(zhǎng)度（為了簡(jiǎn)便，設(shè)a0=-∞，f0=0），狀態(tài)轉(zhuǎn)移方程如下：時(shí)間復(fù)雜度O(n2)，不符合要求。思路分析改進(jìn)后的算法設(shè)gi表示到目前為止，所有長(zhǎng)度為i的單調(diào)遞增子序列中最后一個(gè)元素的最小值。易知，gi-1≤gi。當(dāng)?shù)降趇-1個(gè)字符為止的{gi}已知時(shí)，fi就等于在{gi}中第一個(gè)大于或等于ai的元素的位置j。此時(shí)，令gj=ai，更新{gi}。一開(kāi)始，gi=∞。時(shí)間復(fù)雜度O(nlogn)，符合要求。改進(jìn)算法運(yùn)行實(shí)例n=10i12345678910ai3141592653figi1112233344∞∞∞∞∞∞∞∞∞∞31425396核心代碼原算法(O(n2))：for(int

i

=

0;

i

<

n;

i++)

{

f[i]

=

1;

for(int

j

=

0;

j

<

i;

j++)

if(a[j]

<

a[i])

f[i]

=

max(f[i],

f[j]

+

1);

}改進(jìn)后的算法(O(nlogn))：fill(g,

g

+

n,

infinity);

for(int

i

=

0;

i

<

n;

i++)

{

int

j

=

lower_bound(g,

g

+

n,

a[i])

-

g;

f[i]

=

j

+

1;

g[j]

=

a[i];

}3.4容器與容器有關(guān)的知識(shí)容器(container)是以一定的形式存儲(chǔ)一組相同類(lèi)型的數(shù)據(jù)的對(duì)象。STL中的容器都是用模板類(lèi)來(lái)實(shí)現(xiàn)的。STL中的容器提供了幾乎相同的接口。容器的成員函數(shù)迭代器操作begin(),end(),rbegin(),rend()元素操作front(),back(),operator[]()列表操作insert(),erase(),clear()容器的成員函數(shù)棧和隊(duì)列操作push_back(),pop_back(),push_front(),pop_front()其它操作size(),empty(),resize()關(guān)聯(lián)容器操作find(),lower_bound(),upper_bound(),equal_range()常用STL容器名稱(chēng)描述所在頭文件迭代器類(lèi)型vector向量<vector>隨機(jī)迭代器deque雙頭隊(duì)列<deque>隨機(jī)迭代器list鏈表<list>雙向迭代器stack棧<stack>不提供迭代器queue隊(duì)列<queue>不提供迭代器priority_queue優(yōu)先隊(duì)列<queue>不提供迭代器set集合<set>雙向迭代器multiset多重集合<set>雙向迭代器map映射<map>雙向迭代器multimap多重映射<map>雙向迭代器一般容器vectordequelist元素多余空間元素指針多余空間多余空間元素元素元素元素哨兵節(jié)點(diǎn)元素節(jié)點(diǎn)元素節(jié)點(diǎn)容器適配器棧stack隊(duì)列queue優(yōu)先隊(duì)列priority_queue關(guān)聯(lián)容器元素有序用平衡二叉樹(shù)實(shí)現(xiàn)類(lèi)名：set,multiset,map,multimap分類(lèi)按元素構(gòu)成來(lái)分集合：元素本身就是關(guān)鍵字，直接參與排序映射：元素由關(guān)鍵字和被映射的值構(gòu)成，只有關(guān)鍵字參與排序按關(guān)鍵字能否重復(fù)來(lái)分普通：關(guān)鍵字不能重復(fù)多重：關(guān)鍵字允許重復(fù)關(guān)聯(lián)容器的特殊成員函數(shù)查找類(lèi)find()lower_bound()upper_bound()equal_range()復(fù)合類(lèi)operator[]()例題：支付帳單題目描述比爾最近遇到了一件麻煩事。每天上午