2 weixin_40736501

尚未进行身份认证

暂无相关描述

等级
博文 21
排名 42w+

记忆化搜索的顺序

https://www.luogu.org/problemnew/show/P1238根据字典序,要上左右下才能按字典序排列,所以,要输出路径时,要注意顺序!

2019-06-17 12:51:34

迷宫

https://www.luogu.org/problemnew/show/P1331对于迷宫,边缘上要加一层围栏,否则,就可以通过数组越界绕到另一边了!

2019-06-17 12:48:31

数组越界的灾难

https://www.luogu.org/problemnew/show/P4017题目的数据范围是5000,但是为了防止MLE从而爆零,我的数组只开到了3000,从而数组越界。但是实际上,开成5000也不会发生MLE的现象。所以,不要因为担心程序可能是错的而去做肯定是错的事情。...

2019-06-15 16:46:02

归并排序求逆序对

https://www.luogu.org/problemnew/show/P2804开始用前缀和求每段的平均数,结果超时了。就改用归并排序求逆序对。

2019-06-15 12:01:59

排序的重要性

https://www.luogu.org/problemnew/show/P1690用Floyd预处理出两个房间最短距离,然后对P进行排序,最后做旅行商问题,复杂度不限(2^n或者n!都可以)。如果P数组没有排序,就无法遍历到所有的顺序,所以,在用next_permutation来枚举所有可能时,必须要先对数组排序,否则,就会在搜索时错过最优解,然后就WA掉了……...

2019-06-15 11:58:17

全局变量的坏处

https://www.luogu.org/problemnew/show/P1388在搜索时,会遇到很多重复,全局变量会在每层都修改,导致混乱,于是就WA了。如果把全局变量改为局部变量,上一层不会影响下一层,完美!...

2019-06-14 21:36:35

……

https://www.luogu.org/problemnew/show/P1656开始对每条边依次删除,分别判断超时,复杂度异常的高,可以到达O(n³mlogn+m²),要是预处理,就能变成O(n³logn),改造成功!...

2019-06-14 21:32:57

离散化

https://www.luogu.org/problemnew/show/P2207在这道题里,N的数值很大,甚至都不能出现在复杂度的公式里,但是,中间有很多空隙,可以用离散化来把数减少,复杂度变为O(k²),完美!当出现N<=1,000,000,000时,意味着要用离散化!...

2019-06-13 12:03:02

洛谷1351

https://www.luogu.org/problemnew/show/P1351如果简单地去计算像w[a]*w[b]+w[a]*w[c]+w[a]*w[d]+w[b]*w[a]+w[b]*w[c]+w[b]*w[d]+w[c]*w[a]+w[c]*w[b]+w[c]*w[d]+w[d]*w[a]+w[d]*w[b]+w[d]*w[c]一样的复杂算式,就会超时,可以简化为和的平方减平方的和来...

2019-06-09 21:55:59

洛谷2661

https://www.luogu.org/problemnew/show/P2661最开始的想法是从每个点开始,传递N步,看到哪步回到i,但是,如果样例碰巧是i到x,x到y,y又回到x,程序就会产生很多的循环从而超时,所以要剪枝,最明显的剪枝条件当然是重复之前到达过的点就break掉。这个优化,可以把某些特殊情况,简化为O!n!的!时!间!复!杂!度!所以:当搜索到重复状态时,要注意退出!...

2019-06-09 21:50:47

规律的重要性

https://www.luogu.org/problemnew/show/P3795开始,我用了next_permutation,结果超时了。后来我发现了递推公式,f(n)=f(n-1)+(n-1)*f(n-2),再配合滚动数组,成功!

2019-05-29 17:32:36

经常插入新元素怎么处理

https://www.luogu.org/problemnew/show/P2952最开始把队列存在数组开头,每次左插都得挪一遍,步骤非常繁琐,而右插是O(1)的,如果每次都左插,就会变为O(S^2),超时,如果开始把队列存在中间,维护两个指针分别指向队头和队尾,每次左插动左指针,每次右插动右指针,这样,就不会经常动很多的变量了,复杂度O(S),而S为10万,不会超时,完美!...

2019-05-10 21:34:23

背包

https://www.luogu.org/problemnew/show/P1507我开始做成了完全背包,可能一些体积非常小的物品就会出现多次,导致扭曲,但是01背包就不会重复。

2019-05-10 21:25:12

数组下标问题

https://www.luogu.org/problemnew/show/P1178在用数组存储每个月的天数时,需要在前面放一个0来占位,否则1月就跑到a[0]上去了。在存储每月的天数时,要添0占位。...

2019-05-08 21:46:15

遇到大数判奇偶

https://www.luogu.org/problemnew/show/P1885在提交暴力得到80分后,我用特征区分2个MLE的点,试了很多方法,最后发现两个大数输入的奇偶性不一样,'AC’了。

2019-05-04 21:14:05

输出细节

https://www.luogu.org/problemnew/show/P1898当两位数的十位为0时,不能输出为两位数,需要输出一位数,不能输出两位数!

2019-05-03 22:13:52

字典序的判断

https://www.luogu.org/problemnew/show/P1628在sort的cmp里面,需要判断字典序,比较时要比较到’\0’才能结束,所以是for(inti=0;i<=l;i++)而不是for(inti=0;i<l;i++),如果写成for(inti=0;i<l;i++),则当某个字符串和它的某一个前缀同时出现在输入中,并且前缀后出现,则排序时会认...

2019-05-02 21:47:31

平均距离

https://www.ijsuanke.com/course/1922/134375平均距离指的是两个不同节点的距离平均值,而不是所有n²个距离都算。

2019-05-01 10:45:13

布尔变量判断条件

https://www.jisuanke.com/course/1922/134375在枚举选定方法时,由于直接用Godel编码会爆int,所以只能用布尔数组来存。当布尔数组全是true时,而不是只在某些位置上是true,才能退出。...

2019-04-30 21:52:49

记忆化搜索

https://www.jisuanke.com/course/1922/134376题目中要求选恰好m个,只有C(n,m)种情况,而我又暴力,又在最内层循环算,成为O(n*2^n)算法,导致超时。实际上,只需要O(C(n,m))复杂度就够了。...

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