ACM简单题秒杀和C++STL

ACM简单题秒杀和C++STLnullPart I ACM竞赛简单题秒杀攻略Part I ACM竞赛简单题秒杀攻略简单题简单题简单题的特点：没有算法或者只有基本的算法编程复杂度不高分辨简单题：简单题一般题目较短校赛的第一题往往是简单题观察rank list和场上气球情况简单题是校赛决胜的关键简单题是校赛决胜的关键如何秒杀简单题如何秒杀简单题提高代码正确率提高写代码的速度熟练掌握各种基本算法Step 1: 解析题目Step 1: 解析题目背景介绍、问题提出输入输出要求输入输出样例时间、空间限制以及其他信息Step 2...

nullPart I ACM竞赛简单题秒杀攻略Part I ACM竞赛简单题秒杀攻略简单题简单题简单题的特点：没有算法或者只有基本的算法编程复杂度不高分辨简单题：简单题一般题目较短校赛的第一题往往是简单题观察rank list和场上气球情况简单题是校赛决胜的关键简单题是校赛决胜的关键如何秒杀简单题如何秒杀简单题提高代码正确率提高写代码的速度熟练掌握各种基本算法Step 1: 解析题目Step 1: 解析题目背景介绍、问题提出输入输出要求输入输出样例时间、空间限制以及其他信息Step 2: 了解输入输出Step 2: 了解输入输出输入输出是分离的 <输入文件 >输出文件输入，以EOF结束（例题：ZOJ 1001） while (scanf(“%d”, &n) != EOF) { … } while (cin >> n) { … } 输入，以0结束（例题：ZOJ 1115） while (scanf(“%d”, &n) != EOF && n != 0) { … } <- acm.zju.edu.cnStep 2: 了解输入输出Step 2: 了解输入输出输入，先输入case数 scanf(“%d”, &nCases); for (i = 0; i < nCases; ++i) { ... } 整行输入 char buffer[256]; gets(buff); string buf; getline(cin, buff); Step 2: 了解输入输出Step 2: 了解输入输出输出，case之间用空行分隔（例题：ZOJ 1152） int nCases = 0; { if (nCases++) printf(“\n”); … } 输出，每个case之后输出空行（例题：ZOJ 1457） { … printf(“%d\n\n”, ans); } Step 3: 了解常见错误类型Step 3: 了解常见错误类型Compilation Error 编译错误 Segmentation Fault 数组越界、堆栈溢出等 Time Limit Error 运行时间超限 Memory Limit Error 内存超限 Wrong Answer 答案错误 Presentation Error 格式错误 Output Limit Error 输出超限 Restricted Function 非法函数Step 4: 程序调试Step 4: 程序调试重新读题、检查代码数组是否开的够大（大数组开到全局，避免堆栈溢出） int -2^31 ~ 2^31 – 1 long long largenumber; // -2^63 ~ 2^63 - 1 printf(“%lld\n”, largenumber); 构造测试数据题目提供的测试数据一般较弱边界数据、特殊数据Step 5: 复杂度估计Step 5: 复杂度估计估计程序空间复杂度默认空间限制：32M char c[1000000]; // 1M int a[1000][1000]; // 4M 估计程序时间复杂度一般ZOJ可以接受的时间复杂度为10^6~10^7Step 5: 复杂度估计Step 5: 复杂度估计数据范围允许的时间复杂度 10^20 O(logN) 10^9 O(logN) O(sqrt(N)) 10^6 O(N) 10^5 O(N logN) 10^4 O(N logN) O(N sqrt(N)) 10^3 O(N^2) 10^2 O(N^3) 20 O(2^N)如何秒杀简单题如何秒杀简单题提高代码正确率提高写代码的速度熟练掌握各种基本算法Step 1: 熟悉编程环境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环境Step 2: 熟悉ZOJ环境比赛前至少要在ZOJ上过题熟悉题目的各个组成部分熟悉输入输出格式熟悉交题、查看返回信息的方法熟悉Runs中的Search功能Step 3: 多做在线比赛、练习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.ruStep 4: 团队合作、赛场动向Step 4: 团队合作、赛场动向ACM是注重合作的竞赛三人分工看题、讨论、写题，协调上机时间三人根据各自特点定位角色、分工遇到卡题的时候，交换检查、测试一些比赛经验（Special Thanks to LCLL）优先做简单题观察气球和排名，了解简单题动向，避免卡题 90%以上的队伍曾经赛后发现自己全场看错题了，因此每个题的题意至少要两人以上看过，特别是没过题时Step 4: 团队合作、赛场动向Step 4: 团队合作、赛场动向一些比赛经验续过sample，并且尽量稍微测试后再交题注意使用打印功能，调试程序尽量下机，把时间留给写题的队友对题目有疑问、比赛时候出现意外的，马上联系巡场工作人员学会放弃如何秒杀简单题如何秒杀简单题提高代码正确率提高写代码的速度熟练掌握各种基本算法Step 1: 学好数据结构Step 1: 学好数据结构常用数据结构链表堆栈/队列优先队列树图 Hash 并查集Step 2: 学习常见算法Step 2: 学习常见算法常用的题型（ZOJ论坛有题目分类信息）简单题模拟题搜索题贪心题动态规划（DP）题图论题数学题Step 3: 日常学习Step 3: 日常学习周围的算法讨论区编程答疑@cc98 Algorithm@88（飘渺水云间）做题+看书，算法真有趣满世界做题、参加比赛在ZOJ上多做题，参加浙江大学ACM集训队关注ZOJ、编程答疑、Algorithm最新通知 Part II Standard C++ LibraryPart II Standard C++ LibraryC++风格头文件C++风格头文件#include #include #include #include #include #include #include using namespace std; 输入输出流输入输出流cin >> n >> m; cout << x << “=” << y << endl; getline(cin, str); 输出控制： #include cout.setf() cout.unsetf() cout.precision()输入输出流输入输出流使用方法示例 double a = 1234; cout.setf(ios::fixed); cout.precision(3); cout << a << endl; 输出 1234.000string类string类#include s = “hello world”; s += “h”; s = t + “asdf”; if (s > t) s.substr(3);string类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类stringstream类#include istringstream, ostringstream, stringstream 使用方法和cin, cout相似 istringstream使用示例 string s = “a b c”, t; istringstream is(s); while (is >> t) cout << t << endl; 输出 a b cstringstream类stringstream类ostringstream使用示例 ostringstream os; os << 3 << “ solutions”; cout << os.str() << endl; 输出 3 solutionsSTL容器STL容器STL容器实现了一些常用的数据结构 vector 数组/堆栈 list 链表 queue 队列 deque 双向队列 set 集合 map 字典、映射 priority_queue 优先队列IteratorIterator可以把Iterator看成某种指针，指向容器内部 C语言中的指针就是一种特殊的Iterator Iterator和指针一样支持*和->操作可以使用Iterator的++运算符来遍历容器一般的容器都提供了begin()和end()两个函数来得到指向容器头、尾的两个Iterator。其中begin指向头元素，end指向最后一个元素的后一个位置。Iterator的分类Iterator的分类Input Iterator Output Iterator Forward Iterator Bidirectional Iterator 双向移动，只支持++和--操作 list/map/set Random Access Iterator 支持所有的指针操作 vectorvectorvector#include 动态数组 vector arr; arr = vector(10); arr.push_back(3); cout << arr[2] << endl; arr = arr2; if (arr < arr2)vectorvector常用的操作 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);vectorvectorvector的初始化 vector arr(100, 0); 或者 arr = vector(100, 0); vector VS 数组 vector的灵活性比较好，不需要考虑长度问题，可以减少编程复杂度，使用起来和数组一样方便。但是vector的效率远低于数组，在效率要求较高时慎用。vectorvectorvector的遍历 for (vector::iterator vi = arr.begin(); vi != arr.end(); ++vi) { cout << *vi << endl; } 或者 for (int i = 0; i < v.size(); ++i) { cout << v[i] << endl; }listlist#include 双向链表 push_back, pop_back, push_front, pop_front 由链表的特性可知，list的迭代器不支持算数运算。例如l.begin() + 5是非法的，而list也不支持[]运算符，因此遍历list只能使用Iterator方式。dequedeque#include 双向队列 deque是vector和list的中间产物，其内部结构是若干小段被连接起来的连续空间。 deque支持push_front和pop_front deque和vector一样支持下标访问 deque的实现比vector和list都要复杂，因此直接影响了它的效率。priority_queuepriority_queue#include 用最大堆实现的优先队列 priority_queue中的元素需要支持<操作符。 priority_queue不支持clear操作。常用操作 pq.top(); pq.push(5); pq.pop();priority_queuepriority_queue相关题目 ZOJ 2724，2006年校赛预赛题模拟windows消息队列机制，随着时间不断有新的消息加入到队列，不同的消息有不同的权重，权重高的要先处理。setset#include 有序的元素集合，set中的元素也要支持<操作符支持元素插入、删除和查找，复杂度为O(logN) 双向迭代器，不支持随机访问常用操作 set s; s.insert(3); s.erase(5); if (s.find(5) == s.end()) // 5不在集合中setsetset的遍历 for (set::iterator si = s.begin(); si != s.end(); ++si) { cout << *si << endl; } 遍历的顺序是有序的mapmap#include 实现任意两个类型元素之间的映射 map m; // key, value 要求key支持<运算符，1个key最多只能对应1个value 效果与set > 类似常用操作 map m; m[“haha”] = 5; if (m.find(“hoho”) != m.end()) m.erase(m.find(“heihei”));mapmapmap的遍历 for (map::iterator mi = m.begin(); mi != m.end(); ++mi) { cout << mi->first << “ “ << mi->second << endl; } 相关题目 ZOJ 1109 实现字典，每个单词有一个解释，然后对于一些单词查询，输出对应的解释。 map m;map和setmap和setmap和set的实现 map和set使用红黑树的实现，红黑树是一种平衡二叉搜索树，因此插入、查找和删除的操作都是O(logN)的复杂度。但是由于复杂的算法实现，效率并不是很高。算法算法#include 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 sort默认从小到大排序，如果我们要以从大到小的顺序排序，可以给sort函数加上第三个参数 sort(arr.begin(), arr.end(), greater()); 其中greater()就是仿函数，实现了()运算符，可以对两个元素进行大小的比较自定义仿函数自定义仿函数实现自定义排序事实上，只要支持()运算符的就可以是仿函数，因此普通的函数就是仿函数，可以以此来构造复杂的排序顺序 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 侯捷祝大家校赛取得好成绩！谢谢！祝大家校赛取得好成绩！谢谢！联系我~~~ 姓名：杭航 QQ： 54621399 Email: Hang.Hang.ZJU@gmail.com

                    本文档为【ACM简单题秒杀和C++STL】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

ACM简单题秒杀和C++STL

你可能还喜欢