null
一些初学者必须要知道的问题
一些初学者必须要知道的问题1.如何用C/C++处理输入输出
2.复杂度和程序优化
3.初学者如何进行修炼1.如何用C/C++处理输入输出
2.复杂度和程序优化
3.初学者如何进行修炼1.如何用C/C++进行输入输出1.如何用C/C++进行输入输出null
相对次要的问题,但成为很多初学者的拦路虎
C/C++(尤其是C)输入输出方法较复杂,需要一定时间实践才能精通
我的任务:通过实例提供处理各种输入输出任务的方法,并讲解一些原则性的问题,同学们可以举一反三
首先,几个基本概念null什么是标准输入、标准输出?
标准输入(stdin):键盘(scanf, cin)
标准输出(stdout):屏幕(printf, cout)
建议程序中只使用stdin和stdout
要打开文件怎么办?
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);nullACM/ICPC中基本上都是要求从键盘输入,屏幕输出
是人工评测?
否,测试前程序被做了重定向,就向上面一样,只不过重定向是外部的
比如,Linux Shell下
$ ./prog < input > output
$ diff output answer
所以,严格按照题目描述来进行输入输出,不要打印任何题目未做要求的信息
nullACM/ICPC的输入输出特点:流式、ASCII
顺序输入、输出,避免使用文件定位函数(如:fseek)
不需要把所有的输出放在一处进行,随时都可以输出,只要顺序是对的,因为只有当你的程序终止了,与正确答案的比较才会开始
字符格式,12345是5个字符‘1’,’2’,’3’,’4’,’5’构成
所以,C中只能使用处理ACSII文件的输入输出函数(getchar,putchar,scanf,printf,gets,fgets,puts)null使用C++进行输入输出
cin,cout
优点
数据类型自识别,使用简单
缺点
速度慢!
ACM/ICPC的测试数据规模非常大,cin/cout在这种情况下会成为性能瓶颈,引发超时
除非输入规模小,否则不推荐使用cin!
输出规模相对较小,在某些情况下使用cout会很方便,但是cout控制输出格式不如printf灵活null一个重要的误区
不要在一个程序中同时使用cin和C输入函数(如:scanf)
也不要同时使用cout和C输出函数(如:printf)
但是,可以C输入函数和cout搭配使用,反之亦然
违反以上原则可能导致输入/输出结果错误(会发生乱序)!
null推荐使用C函数进行输入输出
输出:printf(putchar,puts),其用法请查阅相关书籍,比较简单,不做重点讲解
每一行输出完后要打印回车’\n’,包括最后一行
输入:scanf, fgets(gets), getchar
scanf
输入格式
%d %lld %c %s %lf
对每种格式搞清楚一个重要问题
是否自动跳过前导空白?
什么是空白:空格,TAB,回车
null%d %lld %lf自动扫描前导空格
比如:读入5个整数到A[5]
输入文件中,数的排布是这个样子
35 26 78
99
206
不管它,直接5次%d
for ( int i = 0; i < 5; i++ ) scanf(“%d”, A + i);
%lld用于输入和输出长整数(long long,64位)
%lf用于输入输出double
null%s 读一个字符串,自动扫描前导空白,读到空白结束
如: abcd efgh,将读出”abcd”
%c读一个字符,但是不扫描前导空白
如何读一个非空白字符呢?
比如,读取某人的信息,其性别用M/F表示
Nathan M Flying
Claire F Self-healing
名字和能力用%s读,性别怎么办,自己扫描空格?麻烦!null读一个非空白字符,方法一
char str[2];
scanf(“%1s”, str);
// %s扫描前导空白,并且只读一个字符
char c = str[0];
方法二
强制扫描空白
在%前面加上一个空格表示“强制扫描前导空白”
scanf(“ %c”, &ch);
前面那个读人物信息的完整scanf语句:
scanf(“%s %c %s”, name, &gender, ability);
null同理,格式后面加一空格表示“读完这个变量后扫描空白”,注意空白是包括回车的
读一行:gets, fgets
gets会导致很讨厌的warning message,所以可改用fgets
fgets(str, sizeof str, stdin) = gets(str)
注意应使“下一个字符”处于这一行开头
有n个整数在一行上,但是n不知,只知道整数是空格分开的,怎么读?
拿getchar+ungetc扫描?麻烦!
介绍一个函数:strtoknullstrtok示例
5 38 29 38 28 58 82 58
char str[100];
char *input = str, *token;
gets(str);
while ( (token = strtok(input, “ “)) != NULL ) {
input = NULL;
int number = atoi(token);
// 处理number
}
null也可用istringstream处理
istringstream in(str);
while ( in >> k ) {
// 处理k
}
如果数据不多,不失为一个好办法
学习C函数输入输出,尤其是各种格式串,最好查阅相关手册
Linux $ man 3 printf2.复杂度和程序优化2.复杂度和程序优化null复杂度计算出来后有什么用?
估计程序能否在规定时间内处理题目指定规模的数据
“规模”的举例
给N个数排序
规模:N
判断字符串P是否是字符串T的子串
规模:串的长度|P|和|T|
判断一个整数是否属于整数集合S
|S|
要判断多少次(查询次数)
图中某两个点的最短路径/求连通图的最小生成树
顶点数
边数
给一个整数集合S,问是否存在S的一个非空子集T,满足T中所有元素的和为零
|S|
null重要的事实:当代计算机1s内可做10^7左右次计算
配置好的机器可到k*10^7~10^8
在这个限制下时间复杂度一定的算法存在能处理的规模上限
复杂度 数量级 最大规模
O(logN) >>10^20 很大
O(N^1/2) 10^12 10^14
O(N) 10^6 10^7
O(NlogN) 10^5 10^6
O(N^2) 1000 2500
O(N^3) 100 500
O(N^4) 50 50
O(2^N) 20 20
O(N!) 9 10 null几点说明
以上只是大概数据,具体的情况还和实际问题中的其他因素有关
算法的常数因子
2N和16N
测试机的配置
复杂度是上界还是上确界
程序中使用的剪枝和数据的关系
应用
抛弃无希望的算法
举例:如果规模是2000,你设计出来的算法是O(N^3),应该想办法把它改进到O(N^2)
2006 UESTC校内赛题目:Simple Task II
X^2=1(mod n)的解的个数(n<2^31≈2*10^9)
枚举x [1,n) 复杂度是O(n)
标程的复杂度O(n^1/2) 可算到n<=10^12null无需过度优化
ICPC不是比谁的复杂度更低,谁的程序更快,而是比谁能够在给定的时间内把答案正确的计算出来
复杂度足够好即可
给N个整数,求他们的一个排列,使得相邻元素的差的绝对值之和最小
N<=8 枚举所有可能的排列!
给一个整数集合S,问是否存在S的一个非空子集T ,满足T中所有元素的和为零
|S|<=20 枚举所有可能的子集 O(2^|S|)
事实上,这是一个NP完全问题,目前没有比O(2^|S|)更快的算法,你去想复杂度更好的算法可能根本就是在浪费时间null无需过度优化 – 反例
上述原则并不是绝对的,如果你有兴趣,完全可以去思考一下复杂度更好的算法,如果你发现了一个很好的算法,不妨去出道题,考考别人!给北大OJ(http://acm.pku.edu.cn)出题是有奖金的哦!
空间复杂度
当代32位PC上空间最大限制一般是10^7Byte≈10MB,比如你可以开几个大小为10^6的整型数组: int A[10^6]; 开更大的数组,比如A[10^7]一般会遇到Memory Limit Exceed; 即使不超内存根据前面的运算次数限制可知时间复杂度也不会好
有一些缩减空间的技巧,但是卡空间ACM/ICPC一般不推荐null空间复杂度(两种常见空间溢出错误)
栈溢出(递归程序)
递归程序很常见
大多数情况下你不必担心栈溢出的问题
在函数里面开很大的数组
解决方案 开成全局数组
代码优化
少做或不做代码级优化
“给使用低效算法的程序进行代码优化就好比给一头猪喷香水” --USACO
ACM/ICPC很少卡常数因子
只要复杂度相同,一般都能过
即使做,也要选择正确的地方下手
循环密集,执行次数多的地方
使用profiler工具,找出程序中执行次数最多的地方,进行优化(包括算法优化)
Linux
$ g++ -pg –g –o prog prog.cpp
$ ./prog < input > output
$ gprof prog | vim -
null使用STL
STL包含一些复杂度很好的标准算法和数据结构(container)
算法
sort O(NlogN)
push_heap pop_heap O(logN)
nth_element O(N)
容器
set 相当于集合,插入、删除、查询一个元素是否存在都是O(logN)的
map O(logN)把一种类型对应到另一种类型,比如字符串对应到整数
multiset multimap多值
vector
list
queue
stack
priority_queue 优先队列,不过有push_heap和pop_heap这个没有什么太大的用武之地
一定要清楚各种算法和容器操作的复杂度,不要想当然的乱用
http://www.cppreference.com/
http://www.sgi.com/tech/stl/
有了STL仍然要学习基本算法和数据结构,即使不实现也要知道原理3.初学者如何进行修炼3.初学者如何进行修炼null推荐两个网站
ace.delos.com/usacogate(USACO)
基本功训练
基本算法讲解、训练
每个题做出后有讲解、代码
闯关模式
初学者推荐Chapter1-4,Chapter5-6挑战性较强
www.topcoder.com/tc
Algorithm Competition - Single Round Match(SRM)
一个月4次左右,有rating
分两个版(Div I, Div II)
参加人数众多
每次比赛后有详细的解题报告、代码
比赛结束后有Practice Room可以继续做
可以查看每一个人的代码
Forum很热闹,外国人非常乐于助人
有$哦,Room前三
null国内题库
http://acm.pku.edu.cn 北京大学
http://acm.zju.edu.cn 浙江大学
http://acm.tju.edu.cn 天津大学
http://acm.hit.edu.cn 哈工大
http://acm.whu.edu.cn 武汉大学
国外题库
http://acm.timus.ru 数学题较多,OI选手必做
http://acm.uva.es 国外最大题库,人很多,Forum也很热闹
http://acm.sgu.ru 题较难null建议
初学时做一定量的题目打基础
针对特定的经典算法,做相应的题目练习
过题数并不重要,做题数的排名也不重要
参考书
算法导论英文版
入门级读物
初读时,前面的数学部分建立基本概念即可,无需深究
算法的正确性证明、复杂度分析一定要扎实掌握(Master Theorem要会用,摊还分析了解)
数据结构部分理解是关键,一些过于复杂的数据结构对于初学者并不一定要求实现(红黑树、二项堆、Fibbonacci 堆),但基本的数据结构一定要熟练掌握,要能熟练实现
图论经典算法要熟练掌握
动态规划要熟练掌握
高级部分只用选学一些
null参考书
算法艺术与信息学竞赛 刘汝佳、黄亮
较难 适合有一定基础的同学
对于初学者仍然推荐第一章和第三章
BBS
acm.pku.edu.cn的Web Board(现在已经龙蛇混杂,最好只作为了解新信息和讨论题目的渠道)
各大高校BBS的算法版(分类讨论区->电脑技术->Algorithm(或ACM、ICPC),精华区往往有很多资料和指南
推荐
bbs.whu.edu.cn(武大)
bbs.zsu.edu.cn(中山)
bbs.freecity.cn(浙大)
bbs.sjtu.edu.cn(上交)
bbs.hit.edu.cn(哈工大)
bbs.tju.edu.cn(天大)
bbs.nju.edu.cn(南大)
bbs.scu.edu.cn(川大)
本文档为【复赛上机注意事项】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。