当前位置:首页 >> 其它课程 >> 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 侯捷


更多相关文档:

ACM算法题以及答案

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

ACM_入门简单试题[1]

ACM_入门简单试题[1]_英语考试_外语学习_教育专区。在线评判系统中,一道题目的...用键盘的输入方法是 Ctrl+Z 2.最好不要把 C 和 C++的输入输出语句混着用,...

整理的-----ACM题目及答案

可惜辽誓不甘心,辽国征南大将军<耶律 javac++>欲找出三人所在逐个击破,现在他...呢条题有个奇怪噶地方,就系用 STL 做的话,点都系 TLE,后来改翻用 C 语言...

c++第三章题目

c++第三章题目_教育学_高等教育_教育专区。1 题目: 设计函数,将小写英文字符...设计程序求 Acm(2,1),Acm(3,2)。 ---*/ #include<iostream> using namespac...

第六题 acm大赛原题 c、c++语言题目

第六题 acm大赛原题 c、c++语言题目_IT/计算机_专业资料。acm大赛原题 c、c++语言题目病毒侵袭持续中 Problem Description 小 t 非常感谢大家帮忙解决了他的上一...

C++经典面试题

C++经典面试题_专业资料。C++经典面试题经典C++面试题(a) 1.介绍一下 STL,详细说明 STL 如何实现 vector。 STL (标准模版库,Standard Template Library)它由容器...

标准模板库STL练习题

答案: (1)谓词(predicate) 第十一章 标准模板库(STL)习题 2 (2)小于比较操作符“<” 11.1.8 C++标准库中给出的泛型算法包括 (1) 种算法。主要包括以下...

ACM竞赛与STL

ACM竞赛与STL_工学_高等教育_教育专区。ACM竞赛与STL...(Standard Template Library,标准模板库)是 C++语言...如何秒杀ACM竞赛中的简单... 34页 1下载券 ACM中...

ACM第三次培训题目及答案

ACM第三次培训题目及答案_IT/计算机_专业资料。ACM第三次培训题目及答案 ACM第...(c++ ? " %d" : "%d", b + m - 1); b += m * 2; } printf(...

第一题 acm大赛原题 c、c++语言题目

第一题 acm大赛原题 c、c++语言题目第一题 acm大赛原题 c、c++语言题目隐藏>> 第一题 Max Sum Problem Description Given a sequence a[1],a[2],a[3]....
更多相关标签:
acm stl | acm简单题 | acm brainman简单 | 杭电acm简单题 | 故宫门票遭秒杀 | 淘宝秒杀 | 秒杀软件 | 淘宝秒杀软件 |
网站地图

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