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

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

};模板類的使用模板類的使用c_array<int,

100>

a;c_array<double,

20>

b;c_array<c_array<int,

10>,

10>

c;STL概述STL就是建立在模板函數(shù)和模板類基礎(chǔ)之上的功能強(qiáng)大的庫模板函數(shù)可以實(shí)現(xiàn)一般化的常用算法（如統(tǒng)計(jì)、排序、查找等）模板類可以實(shí)現(xiàn)支持幾乎所有類型的容器，用來實(shí)現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)（如鏈表、棧、隊(duì)列、平衡二叉樹等）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迭代器迭代器的定義和種類迭代器(iterator)實(shí)際上是一種一般化的指針類型，是對(duì)指針類型的抽象。根據(jù)所支持操作的不同，迭代器被分為五大類：輸出迭代器(inputiterator)輸入迭代器(outputiterator)前向迭代器(forwarditerator)雙向迭代器(bidirectionaliterator)隨機(jī)迭代器(randomaccessiterator)各種迭代器的功能迭代器類型輸出迭代器輸入迭代器前向迭代器雙向迭代器隨機(jī)迭代器縮寫OutInForBiRan讀取不支持x=*px=*px=*px=*p操作不支持p->xp->xp->xp->xp[i]寫入*p=x不支持*p=x*p=x*p=x迭代++++++++--++--+-+=-=比較不支持==!===!===!===!=<><=>=更多關(guān)于迭代器的信息指針類型就是一種特殊的隨機(jī)迭代器類型。對(duì)于一般的迭代器，這些功能都是通過操作符重載來實(shí)現(xiàn)的。更多關(guān)于迭代器的信息各種迭代器類型之間的關(guān)系：迭代器的作用訪問元素算法與容器之間的紐帶輸出迭代器輸入迭代器前向迭代器雙向迭代器隨機(jī)迭代器模板類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)

{

}

};模板類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í)作為映射的元素類型（關(guān)鍵字和被映射的值）3.3算法與算法有關(guān)的知識(shí)算法(algorithm)每個(gè)算法都是一個(gè)或者一組模板函數(shù)，用來完成一項(xiàng)特定的操作。序列(sequence)序列用兩個(gè)迭代器來描述，表示一組連續(xù)的元素；其中，第一個(gè)迭代器指向序列中的第一個(gè)元素，第二個(gè)迭代器指向序列最后一個(gè)元素的后一個(gè)位置。與算法有關(guān)的知識(shí)函數(shù)對(duì)象(functionobject)函數(shù)對(duì)象重載了函數(shù)調(diào)用操作符(operator())，可以像普通函數(shù)一樣被使用。謂詞(predicate)返回值類型為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ì)象。類名類型作用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算法一覽訪問元素類for_each(),transform()順序查找類find(),find_if(),find_first_of(),adjacent_find(),search(),find_end(),search_n()統(tǒng)計(jì)類count(),count_if()STL算法一覽比較類mismatch(),equal(),lexicographical_compare()復(fù)制類copy(),copy_backward()交換類swap(),iter_swap(),swap_ranges()STL算法一覽替換類replace(),replace_if(),replace_copy(),replace_copy_if()填充發(fā)生類fill(),fill_n(),generate(),generate_n()刪除類remove(),remove_if(),remove_copy(),remove_copy_ifSTL算法一覽去重類unique(),unique_copy()反轉(zhuǎn)類reverse(),reverse_copy()旋轉(zhuǎn)類rotate(),rotate_copy()隨機(jī)打亂類random_shuffle()STL算法一覽排序類sort(),stable_sort(),partial_sort(),partial_sort_copy(),nth_element()二分查找類lower_bound(),upper_bound(),equal_range(),binary_search()合并類merge(),inplace_merge()STL算法一覽分區(qū)類partition(),stable_partition()集合運(yùn)算類includes(),set_union(),set_intersection(),set_difference(),set_symmetric_difference()堆操作類make_heap(),push_heap(),pop_heap(),sort_heap()STL算法一覽最大最小類min(),max(),min_element(),max_element()排列類next_permutation(),prev_permutation()數(shù)值運(yùn)算類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()查找在序列中的位置。例題：最長單調(diào)遞增子序列題目描述給定一個(gè)長度為n的整數(shù)序列A={a1,a2,...,an}，求一個(gè)最大的整數(shù)m，使得存在另一個(gè)序列P={p1,p2,...,pm}，滿足，且。約束條件n不超過30,000ai在[0,1,000,000,00)的區(qū)間內(nèi)思路分析原算法設(shè)fi表示結(jié)尾元素為原序列中第i個(gè)元素的最長單調(diào)遞增序列的長度（為了簡便，設(shè)a0=-∞，f0=0），狀態(tài)轉(zhuǎn)移方程如下：時(shí)間復(fù)雜度O(n2)，不符合要求。思路分析改進(jìn)后的算法設(shè)gi表示到目前為止，所有長度為i的單調(diào)遞增子序列中最后一個(gè)元素的最小值。易知，gi-1≤gi。當(dāng)?shù)降趇-1個(gè)字符為止的{gi}已知時(shí)，fi就等于在{gi}中第一個(gè)大于或等于ai的元素的位置j。此時(shí)，令gj=ai，更新{gi}。一開始，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ǔ)一組相同類型的數(shù)據(jù)的對(duì)象。STL中的容器都是用模板類來實(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容器名稱描述所在頭文件迭代器類型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í)現(xiàn)類名：set,multiset,map,multimap分類按元素構(gòu)成來分集合：元素本身就是關(guān)鍵字，直接參與排序映射：元素由關(guān)鍵字和被映射的值構(gòu)成，只有關(guān)鍵字參與排序按關(guān)鍵字能否重復(fù)來分普通：關(guān)鍵字不能重復(fù)多重：關(guān)鍵字允許重復(fù)關(guān)聯(lián)容器的特殊成員函數(shù)查找類find()lower_bound()upper_bound()equal_range()復(fù)合類operator[]()例題：支付帳單題目描述比爾最近遇到了一件麻煩事。每天上午