IAML's Blog

Find passion in coding

poj3373 Changing Digits

经过几天不屈不挠地思考这一题,最后还是不会,主要是想不到判重的方法。看了解题报告,正确来说,是代码。然后发现一直想不通的问题竟然是那么简单地被解决(用余数判重)。这个涉及到模n同余的特性。另外的两点就是搜索的顺序和高精度。搜索的话要按照以下规则:

1.从最高位开始,逐渐往低位搜;

2.先搜小于原来的数的,然后搜大于原来的数的;

3.先搜一位,然后两位,如此类推。

这样一来就可以保证第一个搜到的答案就是要求的答案。但是就这样直接算的话,还是会超时。所以需要优化一下。主要优化的地方就是求大数的余数的方法。

 

继续阅读

poj1724 Roads

经过无数TLE,终于让我用超级广搜过了这一题(这题其实和sicily的1702差不多思路)。这题的主要难点有两个,1.存放图,2.剪枝。由于同一对点有可能有多条边,所以直接用二维数组是不可行的。然后最容易想到的是用邻接表。然后就是搜索了。搜索的话,我是用一个二维数组dist[i][cost]来记录从原点到i这一点耗费为cost时的最短路径。这样一来,最终的结果就是dist[n][]中的最小值。剪枝方法就是:当当前结点的的距离小于dist[][]相应值时,才把结点放入队列里面,当然不能忘记的是当前的金钱耗费不能大于k。但是仅仅这样是不够了。这样只会TLE。整个上午就纠结在如何剪枝上,结果还是没什么收获,就去吃饭&看动漫,看完之后突然灵机一闪,发现可以用一个变量minimum记录d[n][]中的最小值,然后如果当前的距离如果不小于minimum的话,就不能加入扩展队列。加上这个剪枝后,终于AC了~哈哈

继续阅读