ACM经验分享[转]

时间:2021-08-07 05:36:39

明确规则

规则:以最少的时间过题

(这意味着0ms与1000ms是一样的)

了解规则,善用规则

虽然这个题我不会但是AC是没有问题的

--ACRush

大力出奇迹

  • 学会对拍数据,准备好对拍脚本:测试很重要;小数据很容易理解,大数据无法理解,给你也是白给
  • 打表找规律,打表直接提交,离线打表+在线打表

    敏锐的直觉 犀利的眼神 数学知识的灵活运用 各种姿势打表

弄清时间复杂度,理解数据提示

读题之后,数据的规模基本决定了算法的复杂度

通常 1e8的复杂度 是极限

1e6:n nlogn(慎用)

1e5、1e4:n n
logn n√n

1e3:n
n nnlogn(慎用)

对于1000ms来说的

当然还要考虑常数系数

有时恰恰相反,看上去暴力过不了,而实际上加上一些优化之后正好能过。

卡常数

  • 输入输出是整个程序的瓶颈,对于Java来说尤其如此

    数据规模较大时(>1e5)明显减少运行时间

    速度:getchar>scanf>cin

  • 递归改写:任何一个递归都可以用循环来实现,而循环比递归效率高

  • 广度优先效率比深度优先效率高

  • 要用memset,而非循环进行初始化

memset(num,0,sizeof(int)*n)
memset(num,-1, sizeof num);
memset(num,0x3f,sizeof num);
memset(num,0,sizeof num);
  • 预先开辟好大空间,完全不需要考虑内存释放,自己管理开辟的内存
  • 自己动手,丰衣足食。自己实现一些数据结构,如队列、链式前向星、栈

掌握必要的技能

  • 输入输出重定向
  • 位操作

善用工具

  • 模板,整理代码库
  • STL:一些数据结构、小函数非常有用
int loc=lower_bound(num,num+n,value)-num;
loc:排好序的数组里二分查找第一个>=value的下标 m=unique(num,num+n)-num;
unique将排好序的数组去重且顺序不变
m:去重后的数组大小
  • 使用宏

代码速度

手速=读题+思维+代码

不是你编码慢错误就可以少,不要把时间浪费在打字上,一有思路马上实现、快速实现,闻斯行之,行斯到之。

善用工具是提高代码速度的必由之路。君子生非异也,善假于物也。