ACM之坑&套路

转载声明:本文来源于csdn,禁止二次转载。

写在前边:这些梗都是敝人自己做题和比赛时曾经坑过自己的地方,特别在这里记录一下,所有的链接都是本博客中的题解链接(有大致题意说明和代码),原题请到OJ上自行寻找。目的是提升自身姿势。欢迎大佬们给我提出更好的建议,十分感谢。

#1:一些写法的线段树需要开四倍空间。大概是因为:在很靠近叶子的地方,他的编号就很接近2倍了。然后他的孩子(超生)就接近4倍了。 例如:Codeforces 833B

#2:统计答案的时候 最前边乘上一个1LL,很多时候容易爆。例如:HDU 6058

#3:long long 占位符%I64d,如果只用%d会把低四个字节的值作为int输出,而且更会有奇怪的问题。更重要的是调试时候的输出一定别把占位符写错。或者直接用cout调试输出,否则自己把自己搞崩就不好了。

#4:背包注意循环次序(物品体积内外次序,升序降序)

#5:multiset可以当成堆用

#6:用rk数组来排序的时候,注意按序访问的时候,注意下标是rk[ i ] 不是 i

#7:POJ没有bits/stdc++.h

#8:读入优化要看好题目中有没有负数。

#9:LL最大值大约是9e18 .如果还不够请上Java

#10:比赛稳住,跟好榜。

#11:单点算贡献TLE的话。可以尝试用区间快速算贡献。例如:Codeforces 850B

#12:字符串题目,可以试试用特殊字符把字符串拼接然后跑ACAM/SA/SAM等。或者(自身+特殊字符+自身)等操作。例如:HDU 6096

#13:树的题目一定要测试一下不同长度的链的情况,再提交。

#14:位运算运算优先级特别低,比加法低,比逻辑运算低(x ^ y <N - - - - - - > x ^ ( y < N) )

#15:比较玄妙的题目,要大胆尝试分治,因为分治之后思路一般会有比较大的变化。比如按照二进制位分组做20次,直接将位划分位两半,将复杂度开根号。万一函数有加性,那就可以用2*sqrt的复杂度分别算玩,然后用lower_bound或者map做统计了。例如:HDU5936

#16:点分治的复杂度是N*logN*层复杂度,一般来讲,层复杂度是指组合答案时的复杂度,如果是可以接受的常数就可以用点分治。点分治一般用于统计满足条件的路径条数

#17:现场赛写第一题的时候最好拉队友扫一眼再交,防止第一题上头

#18:各种数据无限对,但是一直WA,检查一遍初始化。

#29:前缀是个好东西,很多区间的查询都可以等价拓展成前缀,并查询两个单点。

#20:如果用vector存答案的话,用之前clear一下,即使是声明在函数栈里的也会有奇妙的问题。例如:痛失2017ICPC新疆C一血。

#21:有spj,还非得用Java的题目,尽量用BigDecimal把大数的表打好,真正算法计算时候转成double计算,常数小很多很多。

#22:涉及到位运算一定全都套上括号,否则很可能因为运算优先级挂掉。例如:痛失2017ICPC新疆I题绝杀,并丢了Au,遗憾Ag。

#23:树的题目先想如何做链,然后集成一下。

#24:比较复杂的状压搜索或者类似的数组、概念特别多的题,先在纸上把每个数组的作用写好,不会把自己心态写爆炸。如Codeforces 919F

#25:常量的输出用字符串直接输出的形式,避免使用占位符以变量形式输出,防止出现战为符错误,比如printf("%I64d\n",2)会输出垃圾值,必须是2LL。因此更好的方式是printf("2\n")

#26: 最小值最大->(多源)bfs搜最小值->取最大。

#27:最大值最小->建图(多源)最长路->取最小

#28:最大值最小<->(反面)最小值最大

#29: 签到题不会做,直接考虑理论边界,然后发现理论边界可以达到,做完了。

#30:总长度固定为M,则本质不同的长度有根号M种,对每种长度可以统一求值,做完了。

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-11-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端吧啦吧啦

数据结构(一)之基础知识

11840
来自专栏数据结构与算法

P3376 【模板】网络最大流

题目描述 如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。 输入输出格式 输入格式: 第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个...

31780
来自专栏Eugene's Blog

一文总结学习 Python的14 张思维导图分类目录文章标签友情链接联系我们

13740
来自专栏苦逼的码农

从零打卡leetcode之day 3--最大子序列

看到三个for循环,时间复杂度的O(n3)。这速度,实在是太慢了。我们来优化优化。

8110
来自专栏AI科技大本营的专栏

你一定能看懂的算法基础书(代码示例基于Python)

本文引自图灵教育《算法图解》 你一定能看懂的算法基础书;代码示例基于Python;400多个示意图,生动介绍算法执行过程;展示不同算法在性能方面的优缺点;教会...

58270
来自专栏前端吧啦吧啦

数据结构(一)之基础知识

376100
来自专栏数据结构与算法

1163 访问艺术馆

 时间限制: 1 s  空间限制: 128000 KB  题目等级 : 大师 Master 题解  查看运行结果 题目描述 Description     皮尔...

29170
来自专栏Albert陈凯

数据结构与算法汇总

文章作者博客微信公共账号:hadoop123(微信号为:hadoop-123),分享hadoop技术内幕,hadoop最新技术进展,发布hadoop相关职位和求...

38250
来自专栏谦谦君子修罗刀

程序员面试闪充--UML类图关系

我们曾借白茶清欢等一个人,曾借花开花落叹宠辱不惊。今天借着类图来了解面向对象又有何不可呢? 小视频传送门:小视频传送门 ? 对象模型中,类图是来描述系统的静态结...

431120
来自专栏程序员叨叨叨

6.2 逻辑操作符(Logical Operators)

Cg语言中有3种逻辑操作符(也被称为boolean Operators),如表 2 所示,逻辑操作符运算后的返回类型均为bool类型。

9830

扫码关注云+社区

领取腾讯云代金券