noip2009题解 + a星算法

《noip2009题解 + a星算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、专题三NOIP2009//bywanda1416版权归原作者第二题(Hankson的趣味题,son)Gcd(x,a0)=a1,Gcd(x,b0)=xb0/b1设f(a,b)代表b这个质因子在a中有多少个.对于a0的任意质因子t,若f(a0,t)=f(a1,t)则只需保证f(x,t)≥f(a1,t),否则f(x,t)=f(a1,t)对于b1的任意质因子t,若f(b1,t)=f(b0,t)则只需保证0≤f(x,t)≤f(b1,t),否则f(x,t)=f(b1,t)由于x的所有因子都是b1的子集,所以我们只需对b1的质因子按如上方法逐个检查这个质因子

2、在x里面的取值范围(若为空则说明无解),并按照乘法原理统计即可.关于分解质因子:由于b1不会超过2*10^9,大于50000的质因子不会超过1个,所以我们只要打出50000以内的素数表即可,若最后除剩的b1仍未除尽,说明此时b1一定是一个大于50000的素数.第三题(最优贸易,trade):做法1:设Low[i]为从1到i当前所有路径中最便宜的价格.Profit[i]为从1到i当前所有路径中最大获利.初始时Low[1]=P[1],Low[2..n]=infinity,Profit[1..n]=0.那么我们可以从1开始广搜,要注意一个点有可能多次

3、被更新.从i可以更新到j的条件是:1.存在有向/无向边(i,j)2.Low[j]>Low[i]或Profit[j]

4、,所以在一个强连通中的最大获利就是强连通中最贵的-最便宜的.我们把所有强连通分量求出来缩为两个点之后.1与n之间只存在一些无环路径,对于这些单向的无环路径我们只需要扫描一遍便可求出最大获利.强连通缩为两个点的具体做法:把一个强连通缩为a,b两个点,连(a,b)边,a的费用为强连通中最便宜的,b的费用为强连通中最贵的.把指向强连通中任何一个点的所有边改为指向a,把强连通中任何一点指向强连通外部的边改为由b指出.这样构出来的保证与原图等价.第四题(靶形数独,sudoku)注：很直白的搜索,由于数独是NP-H问题,所以我们肯定只能用搜索,那么关键就在

5、于剪枝了,我们发现,对于每个格子都有一个取值范围,这个范围由其横行/纵行/小九宫格中已填的数决定,那么无疑我们每次搜索选取值范围最小的格子搜是比较优的.NOIP2009靶形数独解题报告这题困扰了我差不多有一年之久，今天终于解出来了。以下是我的解题报告：【题目大意】给出一个数独，部分位置已经填上了数，每个格子(x,y)(1<=x,y<=9)有一个权值w(x,y)，试找出一种填数独的方案，使得所有格子所填的数字乘以权值之积的和最大，并将这个最大值输出。如果该数独无解，输出-1。【题目分析】数独问题是个非常经典的NP完全问题，没有多项式的算法，只能搜

6、索。首先可以想到枚举，但数据给出的数独空格非常多，最多可能有9^57种状态，是效率极低的算法，对于本题的数据是无法得分的。进一步分析可以想到递归回溯，遇到每个空格，枚举该空格所在的行、列、小九宫已填了哪些数，得出空格可填的数，分别填上这些数并进行下一层的搜索。这样的方法已经远优于枚举，但对于本题大部分数据还是无法出解（实际测试可以得到40%的分数）。为了加快计算一个格子可填的数的速度，我们可以把每行、每列、每个九宫格可填的数用二进制集合表示，每个格子(x,y)当前可填的数的集合就是第x行、第y列以及(x,y)所在小九宫的可填的数集求交。这个操作

7、可以用位运算实现。这样，找可填的数的时间就大大缩短了。实际测试中可以得到75%的分数。上面的方法所得的分数在考场上已经是相当可观，但本题还有进一步的优化余地。有时在数独下方会有一些格子只有一两个可填的数字，而在数独上方的一些格子可能会有很多可填的数字。这时如果按照从上往下搜索的顺序搜索，将会扩展出很多无用的状态。如果是用人脑来做数独的话，必定会先填可行方案少的格子，来给其它格子更多的限制，这样可以剪去很多不可行的分支。所以我们可以预处理求出每个空格可填的方案数，并对它们进行排序。按照这个顺序搜索，将可以得到85%的分数。注意到前面填的数会对后面

8、与它同行、同列、同小九宫的格子造成影响，后面的可填数大小顺序可能有改变。可以考虑在填了一个格子之后，找出后面待填的格子中可填数最少的格子，进行进一步的