ACM竞赛模板：算法与数据结构的融合

5星 · 超过95%的资源需积分: 9 115 浏览量更新于2024-07-19 2 收藏 1.38MB PDF 举报

"ACM模板-f_zyj v" 这篇文档主要介绍了ACM竞赛中的模板，由作者f_zyj精心整理而成，包含了数学、图论、动态规划等多方面的算法。作者强调了模板的重要特性，如正确性、可读性、严谨性和通用性，并指出这些特性在模板代码中是不可或缺的。模板中的代码大多经过多人的不断修正和完善，形成了相对成熟的标准写法。作者f_zyj在文档中提到，他花费了大约五十天的时间来整理这个模板，并且在之后的时间里持续进行调整和改进，力求使其接近完美。他还表示，原稿在他的个人博客上，他会定期更新模板，并欢迎大家提出问题和建议，甚至欢迎贡献代码来优化模板。模板的分类是一个关键点，作者意识到算法和数据结构之间的紧密关系，但为了便于学习，他还是进行了分类。尽管有些内容可能同时属于多个类别，但他根据常规理解进行了取舍，最终确定了八种分类。虽然具体的分类细节未在提供的内容中列出，但可以推断，这八种分类可能涵盖了ACM竞赛中常见的问题类型，例如基础算法、排序与搜索、图的遍历等。此外，文档还提到了STL（Standard Template Library，标准模板库），这是一个在C++中广泛使用的库，包含容器（如vector、list、set）、迭代器、算法和函数对象等，对于ACM竞赛中处理数据和执行算法是非常有用的工具。作者可能在模板中包含了如何有效利用STL进行编程的示例和技巧。这份"ACM模板-f_zyj v"是ACM竞赛参与者和算法学习者的宝贵资源，它不仅集合了多种算法的实现，还反映了模板设计的最佳实践和持续改进的精神。通过这份模板，学习者可以更好地理解和应用各种算法，提升在竞赛中的表现。同时，作者开放的社区参与方式鼓励了知识的共享和进步。

priority_queue<int, vector<int>, greater<int> > qqq; // 定义的先出队

priority_queue的基本操作与queue的󰉝微同。

priority_queue的基本操作：

q.empty() // 如果队为空，则返回true，否则返回false

q.size() // 返回队中元素的个数

q.pop() // 删除队󰶳元素，但返回其值

q.top() // 返回具有最󰷼优先级的元素值，但删除该元素

q.push(item) // 在基于优先级的适当位置插新元素

初学者在使󰉁priority_queue时，最困难的可能就是如何定义较算。如果是基本数据类

型，或已定义较运算符的类，可以直接使󰉁STL的less算和greater算——默认为使󰉁less算

。如果要定义󰙵的较算，法有多种，这󰮟介绍其中种：重载较运算符。优先队试

图这两个元素x和y代较运算符（对于less算，调󰉁x < y，对于greater算，调󰉁x > y），若

结果为真，则x排在y前󰴯，y将先出队，反之，则y排在x前󰴯，x将先出队。

Ex（算实现示）:

class T

{

public:

int x, y, z;

T(int a, int b, int c) : x(a), y(b), z(c) {}

};

bool operator < (const T &tOne, const T &tTwo)

{

return tOne.z < tTwo.z; // 按照z的顺序来决定tOne和tTwo的顺序

}

int main()

{

priority_queue<T> q;

q.push(T(4, 4, 3));

q.push(T(2, 2, 5));

q.push(T(1, 5, 4));

q.push(T(3, 3, 6));

while (!q.empty())

{

T t = q.top();

q.pop();

cout << t.x << " " << t.y << " " << t.z << '\n';

}

return 0;

}

* 输出结果为：

* 4 4 3

* 1 5 4

* 2 2 5

* 3 3 6

如果我们将第个中的较运算符重载为：

! /!16 358

v 2.1 2017.09.21

bool operator < (const T &tOne, const T &tTwo)

{

return tOne.z > tTwo.z; // 按照z的顺序来决定tOne和tTwo的顺序

}

则会得到和第个样的结果，所以，决定算的是较运算符重载函数内部的返回值。

8. STL map

8.1 关于map

在STL的头件中<map>中定义模版类map和multimap，󰉁有序叉树表存储类型为

pair<const Key, T>的元素对序。序中的元素以const Key部分作为标识，map中所有元素的Key

值必须是唯的，multimap则允许有重复的Key值。

8.2 使󰉁map

可以将map看作是由Key标识元素的元素集合，这类容也被称为“关联容”，可以通过个

Key值来快速决定个元素，因此󰴬常适合于需要按照Key值查找元素的容。

map模版类需要四个模版参数，第个是键值类型，第个是元素类型，第三个是较算

，第四个是分配类型。其中键值类型和元素类型是必要的。

定义map对象：

map<string, int> m;

map的基本操作：

/* 向map中插元素 */

m[key] = value; // [key]操作是map很有特󰚬的操作,如果在map中存在键值为

key的元素对, 则返回该元素对的值域部分,否则将会创建个键值为key的元素对,值域为默认值。

所以可以󰉁该操作向map中插元素对或修改已经存在的元素对的值域部分。

m.insert(make_pair(key, value)); // 也可以直接调󰉁insert法插元素对,insert操作会返回个

pair,当map中没有与key相匹配的键值时,其ﬁrst是指向插元素对的迭代,其second为true;若

map中已经存在与key相等的键值时,其ﬁrst是指向该元素对的迭代,second为false。

/* 查找元素 */

int i = m[key]; // 要注意的是,当与该键值相匹配的元素对存在时,会创建键

值为key（当另个元素是整形时，m[key]=0）的元素对。

map<string, int>::iterator it = m.ﬁnd(key); // 如果map中存在与key相匹配的键值时,ﬁnd操作将返

回指向该元素对的迭代,否则,返回的迭代等于map的end()(参󰤁vector中提到的begin()和end()

操作)。

/* 删除元素 */

m.erase(key); // 删除与指定key键值相匹配的元素对,并返回被删除的元素的个数。

m.erase(it); // 删除由迭代it所指定的元素对,并返回指向下个元素对的迭代。

/* 其他操作 */

m.size(); // 返回元素个数

m.empty(); // 判断是否为空

m.clear(); // 清空所有元素

Ex_One:

typedef map<int, string, less<int> > M_TYPE

typedef M_TYPE::iterator M_IT

typedef M_TYPR::const_iterator M_CIT

int main()

{

! /!17 358

v 2.1 2017.09.21

cout << "Erased " << m.erase(key) << endl;

}

return 0;

}

9. STL bitset

9.1 关于bitset

在STL的头件中<bitset>中定义模版类bitset，󰉁来地管󰇹系的bit位类。bitset除

可以访问指定下标的bit位以外，还可以把它们作为个整数来进󰢩某些统计。

9.2 使󰉁bitset

bitset模板类需要个模版参数，󰉁来明确指定含有多少位。

定义bitset对象：

const int MAXN = 32;

bitset<MAXN> bt; // bt 包括 MAXN 位，下标 0 ~ MAXN - 1，默认初始化为 0

bitset<MAXN> bt1(0xf); // 0xf 表示六进制数 f，对应进制 1111，将 bt1 低 4 位初始化为 1

bitset<MAXN> bt2(012); // 012 表示进制数 12，对应进制 1010，

// 即将 bt2 低 4 位初始化为 1010

bitset<MAXN> bt3("1010"); // 将 bt3 低 4 位初始化为 1010

bitset<MAXN> bt4(s, pos, n); // 将 01 字符 s 的 pos 位开始的 n 位初始化 bt4

bitset基本操作：

bt.any() // bt 中是否存在置为 1 的进制位？

bt.none() // bt 中存在置为 1 的进制位吗？

bt.count() // bt 中置为 1 的进制位的个数

bt.size() // bt 中进制位的个数

bt[pos] // 访问 bt 中在 pos 处的进制位

bt.test(pos) // bt 中在 pos 处的进制位是否为 1

bt.set() // 把 bt 中所有进制位都置为 1

bt.set(pos) // 把 bt 中在 pos 处的进制位置为 1

bt.reset() // 把 bt 中所有进制位都置为 0

bt.reset(pos) // 把 bt 中在pos处的进制位置为0

bt.ﬂip() // 把 bt 中所有进制位逐位取反

bt.ﬂip(pos) // 把 bt 中在 pos 处的进制位取反

bt[pos].ﬂip() // 同上

bt.to_ulong() // 󰉁 bt 中同样的进制位返回个 unsigned long 值

os << bt // 把 bt 中的位集输出到 os 流

Ex:

const int MAXN = 32;

bitset<MAXN> bt(0x3f3f3f3f);

int main()

{

cout << bt << '\n';

! /!19 358

v 2.1 2017.09.21

return 0;

}

* 程序执󰢩的输出结果为：

* 00111111001111110011111100111111

10. STL iterator

10.1 关于iterator

iterator（迭代）是󰉁于访问容中元素的指示，从这个意义上说，iterator（迭代）相

当于数据结构中所说的“遍历指针”，也可以把iterator（迭代）看作是种泛化的指针。

STL中关于iterator（迭代）的实现和使󰉁时相当复杂的，这󰮟我们暂时去详细讨论关于

iterator（迭代）的实现和使󰉁，󰖳只对iterator（迭代）做点简单的介绍。

简单的说，STL中有以下类iterator（迭代）：

输iterator（迭代），在容的连续区内向前移动，可以读取容内任意值；

输出iterator（迭代），把值写进它所指向的容中；

前向iterator（迭代），读取队中的值，并可以向前移动到下个位置(++p, p++)；

双向iterator（迭代），读取队中的值，并可以向前后遍历容；随机访问向iterator（迭

代），可以直接以下标式对容进󰢩访问，vector的iterator（迭代）就是这种iterator（迭代

）；

流iterator（迭代），可以直接输、输出流中的值。

10.2 使󰉁iterator

每种STL容都有󰙵的iterator（迭代）类，下󰴯先来看段简单的示代码：

int main()

{

vector<int> s;

for (int i = 0; i < 10; i++)

{

s.push_back(i);

}

for (vector<int>::iterator it = s.begin(); it != s.end(); it++)

{

cout << *it << " ";

}

cout << '\n';

return 0;

}

vector的begin()和end()法都会返回个vector::iterator对象，分别指向vector的󰶳元素位置

和尾元素的下个位置（我们可以称之为结束标志位）。

对个iterator（迭代）对象的使󰉁与个指针变󰮢的使󰉁极为相似，或者可以这样说，指针就是

个󰴬常标准的iterator（迭代）。

Ex:

int main()

{

vector<int> s;

s.push_back(1);

s.push_back(2);

s.push_back(3);

! /!20 358

v 2.1 2017.09.21

剩余357页未读，继续阅读

今天也要加油鸭！！！！！

粉丝: 5
资源: 1

ACM竞赛模板：算法与数据结构的融合

ACM模板-f_zyj 更新（内含 v 1.1 和 v 2.1 的 .pages 格式和 .pdf 格式）

ACM模板-f_zyj

ACM-ICPC模板整理

acm7060f-301T50

上海交通大学acm 模板

ACM-ICPC真题

acm模板整理和使用方法

中山大学acm模板.pdf

aws cli 上传证书到acm

最新资源