当前位置:首页 >> 其它课程 >> ACM简单题秒杀和C++STL

ACM简单题秒杀和C++STL


Part I ACM竞赛简单题秒杀攻略

简单题
? 简单题的特点:
? 没有算法或者只有基本的算法 ? 编程复杂度不高

? 分辨简单题:
? 简单题一般题目较短 ? 校赛的第一题往往是简单题 ? 观察rank list和场上气球情况

简单题是校赛决胜的关键
年份 总题数

简单题数量 AC所有简单题可获奖项 2005 2006 2007 2008 2009 8 8 8 9 9 4 4 4 4 4 二等奖 三等奖 二等奖 三等奖 三等奖

如何秒杀简单题
? 提高代码正确率 ? 提高写代码的速度 ? 熟练掌握各种基本算法

Step 1: 解析题目
? ? ? ? 背景介绍、问题提出 输入输出要求 输入输出样例 时间、空间限制以及其他信息

Step 2: 了解输入输出
? 输入输出是分离的
? <输入文件 >输出文件

? 输入,以EOF结束(例题:ZOJ 1001)<- acm.zju.edu.cn
? while (scanf(“%d”, &n) != EOF) ,


? } ? while (cin >> n) { ? … ? }

? 输入,以0结束(例题:ZOJ 1115)
? while (scanf(“%d”, &n) != EOF && n != 0) ,


? }

Step 2: 了解输入输出
? 输入,先输入case数
? scanf(“%d”, &nCases); ? for (i = 0; i < nCases; ++i) { ... ? }

? 整行输入
? ? ? ? char buffer[256]; gets(buff); string buf; getline(cin, buff);

Step 2: 了解输入输出
? 输出,case之间用空行分隔(例题:ZOJ 1152)
? int nCases = 0; ? {
if (nCases++) printf(“\n”); …

? }

? 输出,每个case之后输出空行(例题:ZOJ 1457)
? {
… printf(“%d\n\n”, ans);

? }

Step 3: 了解常见错误类型
? ? ? ? ? ? ? ? Compilation Error Segmentation Fault Time Limit Error Memory Limit Error Wrong Answer Presentation Error Output Limit Error Restricted Function 编译错误 数组越界、堆栈溢出等 运行时间超限 内存超限 答案错误 格式错误 输出超限 非法函数

Step 4: 程序调试
? 重新读题、检查代码
? 数组是否开的够大(大数组开到全局,避免堆 栈溢出) ? int -2^31 ~ 2^31 – 1 ? long long largenumber; // -2^63 ~ 2^63 - 1 ? printf(“%lld\n”, largenumber);

? 构造测试数据
? 题目提供的测试数据一般较弱 ? 边界数据、特殊数据

Step 5: 复杂度估计
? 估计程序空间复杂度
? 默认空间限制:32M ? char c[1000000]; // 1M ? int a[1000][1000]; // 4M

? 估计程序时间复杂度
? 一般ZOJ可以接受的时间复杂度为10^6~10^7

Step 5: 复杂度估计
? ? ? ? ? ? ? ? 数据范围 10^20 10^9 10^6 10^5 10^4 10^3 10^2 允许的时间复杂度 O(logN) O(logN) O(sqrt(N)) O(N) O(N logN) O(N logN) O(N sqrt(N)) O(N^2) O(N^3)

如何秒杀简单题
? 提高代码正确率 ? 提高写代码的速度 ? 熟练掌握各种基本算法

Step 1: 熟悉编程环境
? VC6.0、Dev-C++等与ZOJ编译器的区别
? for (int i = 0; i < 10; ++i) {


?} ? i = i * i // <-VC6.0编译通过,但是在ZOJ编译出错 ? Dev-C++ 中long long 的输入格式为%I64d,而ZOJ 中为%lld ? 变量名的选取,避免常用单词(xor and等)

Step 2: 熟悉ZOJ环境
? 比赛前至少要在ZOJ上过题
? ? ? ? 熟悉题目的各个组成部分 熟悉输入输出格式 熟悉交题、查看返回信息的方法 熟悉Runs中的Search功能

Step 3: 多做在线比赛、练习
? ? ? ? ? ? ? TopCoder : www.topcoder.com/tc ZOJ : acm.zju.edu.cn POJ : acm.pku.edu.cn HDOJ: acm.hdu.edu.cn USACO: ace.delos.com/usacogate SGU: acm.sgu.ru Timus: acm.timus.ru

Step 4: 团队合作、赛场动向
? ACM是注重合作的竞赛
? 三人分工看题、讨论、写题,协调上机时间 ? 三人根据各自特点定位角色、分工 ? 遇到卡题的时候,交换检查、测试

? 一些比赛经验(Special Thanks to LCLL)
? 优先做简单题 ? 观察气球和排名,了解简单题动向,避免卡题 ? 90%以上的队伍曾经赛后发现自己全场看错题了,因此 每个题的题意至少要两人以上看过

Step 4: 团队合作、赛场动向
? 一些比赛经验续
? 过sample,并且尽量稍微测试后再交题 ? 注意使用打印功能,调试程序尽量下机,把时 间留给写题的队友 ? 对题目有疑问、比赛时候出现意外的,马上联 系巡场工作人员 ? 学会放弃

如何秒杀简单题
? 提高代码正确率 ? 提高写代码的速度 ? 熟练掌握各种基本算法

Step 1: 学好数据结构
? 常用数据结构
? ? ? ? ? ? ? 链表 堆栈/队列 优先队列 树 图 Hash 并查集

Step 2: 学习常见算法
? 常用的题型(ZOJ论坛有题目分类信息)
? ? ? ? ? ? ? 简单题 模拟题 搜索题 贪心题 动态规划(DP)题 图论题 数学题

Step 3: 日常学习
? 周围的算法讨论区
? 编程答疑@cc98 ? Algorithm@88(飘渺水云间)

? 做题+看书,算法真有趣 ? 满世界做题、参加比赛 ? 在ZOJ上多做题,参加浙江大学ACM集训队
? 关注ZOJ、编程答疑、Algorithm最新通知

Part II Standard C++ Library

C++风格头文件
? ? ? ? ? ? ? #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <vector> #include <algorithm>

? using namespace std;

输入输出流
? ? ? ? cin >> n >> m; cout << x << “=” << y << endl; getline(cin, str); 输出控制:
? ? ? ? #include <iomanip> cout.setf() cout.unsetf() cout.precision()

输入输出流
? 使用方法示例
? ? ? ? double a = 1234; cout.setf(ios::fixed); cout.precision(3); cout << a << endl;

? 输出
? 1234.000

string类
? #include <string>
? ? ? ? ? s = “hello world”; s += “h”; s = t + “asdf”; if (s > t) s.substr(3);

string类
? 常用成员函数
? s.size() 字符串长度 ? s.c_str() 返回char *类型的字符串 ? s.find(“hi”) 查找子串,返回起始位置, 不存在返回string::npos ? s.find_last_of(“hi”) 特定方式查找子串 ? s.substr(0, 5) 获取子串 ? s.substr(5)

stringstream类
? #include <sstream>
? istringstream, ostringstream, stringstream ? 使用方法和cin, cout相似

? istringstream使用示例
? string s = “a b c”, t; ? istringstream is(s); ? while (is >> t) cout << t << endl;

? 输出
? a ? b ? c

stringstream类
? ostringstream使用示例
? ostringstream os; ? os << 3 << “ solutions”; ? cout << os.str() << endl;

? 输出
? 3 solutions

STL容器
? STL容器实现了一些常用的数据结构
? ? ? ? ? ? ? vector list queue deque set map priority_queue 数组/堆栈 链表 队列 双向队列 集合 字典、映射 优先队列

Iterator
? ? ? ? ? 可以把Iterator看成某种指针,指向容器内部 C语言中的指针就是一种特殊的Iterator Iterator和指针一样支持*和->操作 可以使用Iterator的++运算符来遍历容器 一般的容器都提供了begin()和end()两个函数 来得到指向容器头、尾的两个Iterator。其中 begin指向头元素,end指向最后一个元素的 后一个位置。

Iterator的分类
? ? ? ? Input Iterator Output Iterator Forward Iterator Bidirectional Iterator
? 双向移动,只支持++和--操作 ? list/map/set

? Random Access Iterator
? 支持所有的指针操作 ? vector

vector
? #include <vector>
? ? ? ? ? ? ? 动态数组 vector<int> arr; arr = vector<int>(10); arr.push_back(3); cout << arr[2] << endl; arr = arr2; if (arr < arr2)

vector
? 常用的操作
? ? ? ? ? ? ? ? arr.clear(); arr.push_back(5); arr.pop_back(); arr.front(); arr.back(); arr.erase(arr.begin() + 5); arr.erase(arr.begin(), arr.end()); arr.insert(arr.begin() + 5, 4);

vector
? vector的初始化
? vector<int> arr(100, 0); ? 或者 ? arr = vector<int>(100, 0);

? vector VS 数组
? vector的灵活性比较好,不需要考虑长度问题, 可以减少编程复杂度,使用起来和数组一样方 便。但是vector的效率远低于数组,在效率要求 较高时慎用。

vector
? vector的遍历
? for (vector<int>::iterator vi = arr.begin(); vi != arr.end(); ++vi) { cout << *vi << endl; ? } ? 或者

? for (int i = 0; i < v.size(); ++i) { cout << v[i] << endl; ? }

list
? #include <list>
? 双向链表 ? push_back, pop_back, push_front, pop_front ? 由链表的特性可知,list的迭代器不支持算数运 算。例如l.begin() + 5是非法的,而list也不支持[] 运算符,因此遍历list只能使用Iterator方式。

deque
? #include <deque>
? 双向队列 ? deque是vector和list的中间产物,其内部结构是 若干小段被连接起来的连续空间。 ? deque支持push_front和pop_front ? deque和vector一样支持下标访问 ? deque的实现比vector和list都要复杂,因此直接 影响了它的效率。

priority_queue
? #include <deque>
? 用最大堆实现的优先队列 ? priority_queue中的元素需要支持<操作符。 ? priority_queue不支持clear操作。

? 常用操作
? pq.top(); ? pq.push(5); ? pq.pop();

priority_queue
? 相关题目
? ZOJ 2724,2006年校赛预赛题 ? 模拟windows消息队列机制,随着时间不断有新 的消息加入到队列,不同的消息有不同的权重, 权重高的要先处理。

set
? #include <set>
? 有序的元素集合,set中的元素也要支持<操作符 ? 支持元素插入、删除和查找,复杂度为O(logN) ? 双向迭代器,不支持随机访问

? 常用操作
? ? ? ? set<int> s; s.insert(3); s.erase(5); if (s.find(5) == s.end())

// 5不在集合中

set
? set的遍历
? for (set<int>::iterator si = s.begin(); si != s.end(); ++si) { cout << *si << endl; ? } ? 遍历的顺序是有序的

map
? #include <map>
? ? ? ? ? ? ? ? 实现任意两个类型元素之间的映射 map<string, int> m; // key, value 要求key支持<运算符,1个key最多只能对应1个value 效果与set<pair<string, int> > 类似 map<string, int> m; m*“haha”+ = 5; if (m.find(“hoho”) != m.end()) m.erase(m.find(“heihei”));

? 常用操作

map
? map的遍历
? for (map<string, int>::iterator mi = m.begin(); mi != m.end(); ++mi) { cout << mi->first << “ “ << mi->second << endl; ? }

? 相关题目
? ZOJ 1109 ? 实现字典,每个单词有一个解释,然后对于一 些单词查询,输出对应的解释。 ? map<string, string> m;

map和set
? map和set的实现
? map和set使用红黑树的实现,红黑树是一种平 衡二叉搜索树,因此插入、查找和删除的操作 都是O(logN)的复杂度。但是由于复杂的算法实 现,效率并不是很高。

算法
? #include <algorithm>
? ? ? ? ? sort(arr.begin(), arr.end()); stable_sort(arr.begin(), arr.end()); reverse(arr.begin(), arr.end()); next_permutation(arr.begin(), arr.end()); unique(arr.begin(), arr.end());

仿函数
? #include <functional>
? sort默认从小到大排序,如果我们要以从大到小 的顺序排序,可以给sort函数加上第三个参数 ? sort(arr.begin(), arr.end(), greater<int>()); ? 其中greater<int>()就是仿函数,实现了()运算符, 可以对两个元素进行大小的比较

自定义仿函数
? 实现自定义排序
? 事实上,只要支持()运算符的就可以是仿函数, 因此普通的函数就是仿函数,可以以此来构造 复杂的排序顺序
? bool comp(const int &a, const int &b) { ? return a % 5 < b % 5; ? } ? sort(arr.begin(), arr.end(), comp);

? 相同元素的比较一定要返回false(0)

自定义仿函数
? 相关题目
? ZOJ 2727,2006年校赛预赛题 ? 给定一些书的书名、出版年份、价格等信息, 然后根据输入的要求进行各种排序。

进一步学习
? 相关资料
? http://10.71.101.90/docz/STL_doc/ ? The C++ Standard Library ? STL源码剖析 by 侯捷


更多相关文档:

应用C++ STL以最小堆方法解决Top K 问题

应用C++ STL 以最小堆方法解决 Top K 问题问题的来源我想不必多言了,很多的面试题中,以及<编程之美>中都 有对问题的描述,以及相关的解法,写本文的目的是以 ...

ACM算法题以及答案

ACM 算法题 使用 C++实现 在做这些题目之前必须了解 vector(数组) ,list(链表...list 使用: STL 中的 list 就是一 双向链表,可高效地进行插入删除元素。 ...

ACM试题及答案

ACM试题及答案_其它_高等教育_教育专区。中国石油大学华东 ACM 试题(黄色高亮为...C++: g++ Main.cc -o Main -fno-asm -O2 -Wall -lm --static -DONLINE...

ACM竞赛辅导之STL

ACM竞赛辅导之STL,c++,STLACM竞赛辅导之STL,c++,STL隐藏>> 第01 篇 ACM/ICPC 竞赛之基础篇 一、ACM/ICPC 竞赛的特点 ACM/ICPC(国际大学生程序设计竞赛)是以...

c++STL库队列简单案例

c++STL库队列简单案例_计算机软件及应用_IT/计算机_专业资料。C++队列 Queue 类成员函数如下: back()返回最后一个元素 empty()如果队列空则返回真 front()返回第...

C++ STL基础及应用实验题目

C​+​+​ ​S​T​L​基​础​及​应​用​实​验​题​目 暂无评价|0人阅读|0次下载|举报文档...

C++笔试题大全

C++笔试题大全局部变量能否和全局变量重名 能,局部会...此时,基类的函数被隐藏(注意别覆盖混淆) STL 中...多态的基础是继承,需要虚函数的支持,简单的多态是很...

标准模板库STL练习题

标准模板库STL练习题_IT/计算机_专业资料。标准模板...答:C++标准模板库提供三种顺序容器:vector,list 和 ...

黑马程序员C语言教程:C++ STL 一般总结

传智播客 C/C++培训专家: C++ STL 一般总结 http://bbs.itcast.cn 分类: C/C++ 一、一般介绍 STL(Standard Template Library),即标准模板库,是一个具有工业...

c++STL容器适配器习题答案

c++STL容器适配器习题答案_工学_高等教育_教育专区。c++ 习题答案1.概念填空题 1.1 STL 是泛型程序设计的一个良好的范例。 标准 C++类库包含的组件既支持 面向...
更多相关标签:
acm stl | acm常用stl | acm简单程序题 | acm简单题 | 杭电acm简单题 | java实现秒杀简单实现 | 太极宗师回应秒杀 | 淘宝秒杀软件taovb |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com