2 weixin_40736501

尚未进行身份认证

暂无相关描述

等级
TA的排名 13w+

贪心的用法

https://www.luogu.org/problem/P3853找到判断的方法,一般是贪心,再配合上二分的模板,就完成了!当遇到二分不知道如何来判断时,要试着用贪心的想法来判断某个值是否满足要求。...

2019-09-16 21:10:18

预处理

https://www.luogu.org/problem/P3088双向队列的模板本应该是寻找距离某个点最近的大于它的值,这题却换成了寻找距离某个点最近的大于等于它的两倍的值,一个高的无法挡住它前面所有的点,所以,只能预处理每个点的两倍数值。当遇到变体时,要预处理!...

2019-09-12 21:25:43

边的数量很多时如何来预处理而导致原来的稠密图变为稀疏图从而躲过RE或TLE的方法

https://www.jisuanke.com/course/2459/257590我开始建了所有边,就变成了n2条边,如果n是20万,这个图不可能存下来导致RE。实际上,可以先做一遍并查集,确立所有的a[i]+a[j]型边,然后再做m条边的最小生成树。当遇到边的数量非常多时,可以先用并查集去掉多余的边。...

2019-09-10 11:38:32

两侧相遇

https://www.jisuanke.com/course/2460/238325如果单纯枚举,复杂度就是2n,而用两侧相遇法,复杂度是n*kn,其中k大约为1.4,复杂度明显降低。当遇到大数据范围时,要用两侧相遇。...

2019-09-04 12:23:54

分辨要用小于还是小于等于

https://www.luogu.org/problem/P1759当有并列情况选前面的情况时,要用小于。当有并列情况选后面的情况时,要用小于等于!

2019-08-27 12:37:43

dp找状态

https://www.luogu.org/problem/P2072在求危险值时,要从后往前反推,如果改成从前往后,就变成单纯枚举了。找好dp的状态,就可以秒杀!

2019-08-26 21:48:18

01背包反向枚举

https://www.luogu.org/problem/P1509如果用01背包时,需要反向枚举,否则同一个物品就会重复计算。当遇到01背包时,要反向枚举!

2019-08-26 12:48:33

预处理

https://www.luogu.org/problem/P2642开始,我想到需要枚举每个位置当作第一个区间的结尾点。然后再算两边的最大子段和,复杂度就变成了n²。实际上,可以先预处理每个前缀和后缀的最大子段和,在扫描时就可以直接用。当遇到超时问题时,要做预处理!...

2019-08-26 12:46:38

数组初始化

https://www.luogu.org/problem/P3399开始,我认为二维数组dp的初始化只要设前m行,实际上,需要把整个数组的1100列都要初始化,才能保证。

2019-08-25 21:16:00

特判

https://www.luogu.org/problem/P1620当mx和mo两个值其中有一个是0时,要把对应的cx或co也置为0。当某个变量的范围可以为0时,要特判!

2019-08-21 15:38:16

判断边界

https://www.luogu.org/problem/P1033开始,我只计算了起点和终点坐标的差,实际上,不是每个整数点都有小球,所以要判断边界!

2019-08-21 15:32:57

剪枝的重要性

开始,我用带权并查集,任意两个区间都要判断一次,就变成了平方的复杂度。后来,我发现合并次数正好为n-1,就加上了这个判断,50分瞬间变成了100分!当遇到某个次数确定时,要在次数到达某个确定的值时跳出循环!...

2019-08-20 21:00:26

while(gets(s))

https://www.luogu.org/problem/P1906开始我用while(1)循环来读入,实际上,当输入很长时,缓冲器会溢出,导致OLE。所以要用EOF来判断是否停止。当输入没有具体停止标记时,或输入很长时,要用while(gets(s))来判断!...

2019-08-10 21:19:36

分裂

https://www.luogu.org/problem/P1114数组的每一项都是0或者1,可以拆成两列来储存。当遇到只有0或者1的动规时,要分成两列!

2019-08-09 21:23:42

防止数组越界

https://www.luogu.org/problem/P1210当整体是一个回文时,要在字符串末尾添加一个字符,否则会数组越界。

2019-08-09 21:19:46

预处理

https://www.luogu.org/problem/P1629如果每走一条路,就选择一次,就会超时。如果用Floyd预处理,就可以成功。当遇到多次询问时,要预处理!

2019-08-06 12:05:56

带权并查集

https://www.luogu.org/problem/P3379在并查集的路径压缩时,要记录每条边的长度,否则,就会破坏掉一些边。当用并查集时,要注意边是否有权值。

2019-08-02 22:09:14

用Tarjan优化

https://www.luogu.org/problem/P3387如果用记忆化搜索,就会有不从根节点走的情况。然后就会变成m*n的复杂度。所以,要用Tarjan来遍历联通块,才能变成线性复杂度。...

2019-08-01 22:22:49

稀疏图

https://www.luogu.org/problem/P2812开始,我先用Tarjan缩点,然后枚举任意两个点,是否有相同的color,然后再添加链表并查集。由于并查集是链表式的(不能有路径压缩,路径压缩会断掉图上本来有的边。),复杂度会非常的高。所以,就会在大数据的时候,超时。我的改进方法是,枚举每一条边,如果这条边不是在联通块之内的,才记录入度和出度。复杂度就可以变为O(m),由于...

2019-08-01 21:57:38

Prim

https://www.luogu.org/problem/P1265因为任意两个点都能连边,所以有n^2条边。克鲁斯卡尔复杂度是O(n²logn),Prim是O(n²)。当遇到稠密图时,要用Prim。

2019-07-31 11:09:06

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!