Dec 7

水不是不负责任的理由 不指定

felix021 @ 2008-12-7 01:40 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(7466) | Via 本站原创 | |
momodi同学說得很对,嗯。

--
貌似新人们总会遇到几个问题,提一下吧。

1. 64Bit整型的问题
这个东西比较纠结阿。一般来说
在VC下面,定义的时候要用__int64
用g++/gcc的时候,则应该用long long定义
在Windows下面,输入输出的时候要用%I64d这个格式
在类Unix(包括Solaris/Linux等)下面,输入输出的时候要用%lld这个格式
对于各类OJ,不妨自己在A+B这道题上试试
参加比赛的时候,务必向工作人员或者judge问清楚编译环境
——包括操作系统和编译器。

2. 大数组RE的问题
emingCup的时候就有队伍遇到这个问题
自己运行的时候都RE还交过来。
这个涉及到编译器对不同类型变量的内存分配规则。
在C/C++中
对于在函数内定义的变量(包括main()函数)
都是在程序的栈空间内分配的(这个空间相对有限)
如果定义一个内存使用量达到MB级别的数组
一般就会Stack Overflow,RE了。
所以遇到大数组的时候建议大家都定义成全局变量
这样就可以在编译的时候就为它们分配好足够的空间。
更具体的可以参见luoxi同学的这篇日志。
http://hi.baidu.com/luoxi0209/blog/item/50364c39b1c2622597ddd8b0.html
另外,想起snoopy大牛的建议,如果你的算法递归稍会微深一点(比如30层),那就考虑优化,或者写非递归的吧。

3. cin/cout的TLE危险
C++中cin/cout这两个预定义好的变量内部都有个缓冲区
对于实际使用是非常有好处的
但是不适合用来做acm:它们常常会导致TLE
原因大概是没有及时把它们的缓冲区输出吧。
特别要注意的是不止cin/cout
其它所有的C++流都可能有缓冲区
所以做题目的时候,特别是有大量I/O的题目
尽量使用scanf和printf (它们的格式化输出功能非常好)。
对于字符串,string确实很好用,但是只能用cin输入
必要的时候,变通的方法是
定义一个比较大的char数组,scanf到这个数组,然后再赋给string
char a[1024];
string b;
scanf("%s", a);
b = string(a);
输出的时候就:
printf("%s", b.c_str());

4. scanf的\n遗留问题以及gets的RE问题
有些题目的输入格式很BT阿
scanf默认用空白字符(包括空格,tab,回车,换行)作为分隔符
在输入完一个数据以后,接下来的空白符不会被处理
会继续留在系统的输入缓冲区(特别是\n)
所以如果这个时候要输入一个字符,很可能的就是输入的是\n
这时候可以用一个getchar()来处理这个\n。
有时候需要读入完整的一行,因为scanf的默认分隔符问题
所以有时候需要换个读入方式
而gets的RE问题是这样的
gets遇到\n或者EOF才会结束
所以可能就会导致数组越界错误
因此尽量不要使用,
推荐使用scanf("%1024[^\n]", a)
或者 fgets(a, 1024, stdin);
限制输入的字符数。

5. 精度问题
对于float/double的比较,通常可能会有舍入误差
(比如0.1这个东西在IEEE754标准下永远不可能精确存储)
导致本来应该相等的不相等,所以建议这样
先定义一个常量,比如精度在10^-9这个额度(要根据具体问题判断这个额度!)
#define EPS (1e-9)
然后用这样一个比较函数:
int cmpDouble(double a, double b){
    if(fabs(a - b) < EPS) return 0; // a == b
    else if(a - b > 0) return 1; // a > b
    else return -1; // a < b
}
对于float/double的取整也很有技巧:
floor和ceil不一定能给你你想要的结果(why?)
对于一个double类型的a,想想这些表达式的意义:
(提示:取(?)整,四舍五入)
(int)(a + EPS)
(int)(a + EPS + 0.5)
以上对于正数成立,对于负数呢?最好还是自己想想,嗯。

其它还有一些建议,比如
~ 定义数组的时候开大些
  比如题目告诉最多5000个数据,那就开到5010或者更多一些吧

~ 不要太依赖vc的调试功能吧
  比赛的时候大多是没这个条件的,学习gdb,或者用printf什么的自己动手调。

~ 学习vim吧,用熟了它你才会知道什么叫做编辑器。

~ 学习STL吧!
最起码一些简单的算法和容器得会使阿,不然你很吃亏的。那些代码都是最牛的那些人写的东西,效率绝对不会比你写的代码差——而且还省大量coding的时间。
举个例子说,对于int a[5] = {3,4,5,2,7};
sort(a, a+5);以后a就是升序了。
如果要降序,自己写一个简单的比较函数就好了。
sort用的是随机化快速排序,绝对比你随便写的qsort以及stdlib.h里面的qsort牛B(它还要一个很费解的比较函数)。同样还有使用归并的stable_sort,堆排的heap_sort(附送全套heap操作函数)。
再有,map和set以RB-tree为底层数据结构,你肯定不会怀疑它们的重要性的;priority_queue对于A*也是很有帮助的。
请永远记住这2点:
STL的区间都是左闭右开的,begin和end之间的区间就是:[begin, end)
比较函数一定要遵循严格弱序化原则: 对于相等的两个元素,不能返回true。
更详细的请参考《Effective STL》

~ 每次测试输入用复制粘贴多累阿,试试这两个语句:
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);

~ BT输入
有时候出题的人他心情不爽,不告诉你有多少个数字
——反正就是塞在一行里面,你自己读去吧
这时候可以选择自己模拟scanf的方式输入整数或者字符串
但是这个代码写起来稍微有点痛苦,是吧。
试试ungetc()和strtok()函数吧。

~ 多到机房去吧,大牛们都在机房等你问问题,嗯。

欢迎大牛们补充。



欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
july
2009-2-11 12:30
hao ~~~a ~~~~you yong
slyar Homepage
2008-12-12 14:37
飘过。。。考虑要不要打劫走~~
felix021 回复于 2008-12-12 17:17
- -||
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]