NOIP2009提高组 解题报告
少说多做- -||
1.潜伏者
简单的字符替换,需要注意的是,‘A’..’Z’需要建立一一对应的关系,而不是映射的关系(因为这点错了1个数据,可见数据弱爆了)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
2.Hankson的趣味题
其实这题朴素做法也可以过,甚至比普及组相对应的那题更简单。朴素做法如下: 题目求方程组:gcd(a0,x)=a1 && lcm(b0,x)=b1 由于lcm(a,b)=ab/gcd(a,b),所以方程组化为: gcd(a0,x)=a1 && gcd(b0,x)b1=b1*x 并且题目已知b1,x必定小于b1,并且b1能够整除x。因此可以考虑枚举x,枚举范围就是1..sqrt(b1),之所以只枚举到sqrt(b1),是因为另一半必定为b1 div x,这样可以减少很多没必要的浪费。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
3.最优贸易
此题可以两遍SPFA解决。第一遍SPFA,求出从1出发,达到i点的最便宜收购价Min[i]。然后把边倒置,第二遍SPFA,求出从n出发,到达i点的最贵售价Max[i]。然后枚举最大的Max[i]-Min[i](也就是路径1->i->n)。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
|
4.靶形数独
此题NP-Hard,所以只能搜索了。由于格子数众多,因此必须优化。 优化1:初始的时候,每个格子能填入的方案数就受到了限制。我们考虑从方案数最少的格子开始搜索,这样可以使无法成功构造数独的状态数大大降低了。我们每次填入(i,j),都需要更新每行、每列、每小九宫格能填的数。每一次搜索,都需要从方格中找出状态数最少的格子(x,y),代价是O(n2),考虑到n=9且整题的复杂度为O(n2!),所以还是可以忽略的。 优化2:对于每行、每列、每九宫格,都要保存0..9是否可用。若用布尔数组保存,浪费空间、转移也比较慢,可以考虑用二进制压缩,一个word就可以存下来。更新的时候通过and 和 or操作就可实现快速置0/1。 有几个二进制技巧,写在程序中: count1(x):统计x的二进制位中有几个1——详见Matrix67大牛博客 搜索中,ps表示的是该行中1..9是否能填,其中二进制位是1的表示能填。p=ps and -ps可以取出ps最右边的一个1。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
|
另外有个很高端的做法:Dancing Links。下次有空研究下