ACM简单题秒杀和C++STL

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

ACM简单题秒杀和C++STL

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

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

ACM简单题秒杀和C++STL

简单题是校赛决胜的关键年份 总题数 简单题数量 AC所有简单题可获奖项 2005 2006 2007 2008 2009 8 8 8 9 9 4 4 4 4 4 二等奖 三等奖 二等奖 三等奖 三等奖

ACM简单题秒杀和C++STL

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

ACM简单题秒杀和C++STL

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

ACM简单题秒杀和C++STL

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

输入，以EOF结束(例题：ZOJ 1001)<- http:// while (scanf(“%d”, &n) != EOF) ,…

} while (cin >> n) { … }

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

}

ACM简单题秒杀和C++STL

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

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

ACM简单题秒杀和C++STL

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

}

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

}

ACM简单题秒杀和C++STL

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

ACM简单题秒杀和C++STL

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

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

ACM简单题秒杀和C++STL

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

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

ACM简单题秒杀和C++STL

Step 5: 复杂度估计 数据范围 10^20 10^9 10^6 10^5 10^4 10^3 10^2 20 允许的时间复杂度 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) O(2^N)

ACM简单题秒杀和C++STL

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

ACM简单题秒杀和C++STL

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等)

ACM简单题秒杀和C++STL

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

ACM简单题秒杀和C++STL

Step 3: 多做在线比赛、练习 TopCoder : http:///tc ZOJ : http:// POJ : http:// HDOJ: http:// USACO: http:///usacogate SGU: acm.sgu.ru Timus: acm.timus.ru