文档介绍：//bywanda1416版权归原作者第二题(Hankson的趣味题,son)Gcd(x,a0)=a1,Gcd(x,b0)=xb0/b1设f(a,b),若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的质因子按如上方法逐个检查这个质因子在x里面的取值范围(若为空则说明无解),:由于b1不会超过2*10^9,大于50000的质因子不会超过1个,所以我们只要打出50000以内的素数表即可,若最后除剩的b1仍未除尽,(最优贸易,trade):做法1:设Low[i][i][1]=P[1],Low[2..n]=infinity,Profit[1..n]=,:(i,j)[j]>Low[i]或Profit[j]<Profit[i]做法2:首先考虑没有环的情况,此时1,n之间要么无法连通,,由于不能”回头”,走到某个点i的极优获利显然是i的费用-路径上此点之前的点的最小费用,,也就是对于有些点对(a,b),在a走到b之后,,我们把点集V,其中任意两个点可以互达,,所以在一个强连通中的最大获利就是强连通中最贵的-,:把一个强连通缩为a,b两个点,连(a,b)边,a的费用为强连通中最便宜的,,(靶形数独,sudoku)注:很直白的搜索,由于数独是NP-H问题,所以我们肯定只能用搜索,那么关键就在于剪枝了,我们发现,对于每个格子都有一个取值范围,这个范围由其横行/纵行/小九宫格中已填的数决定,,今天终于解出来了。以下是我的解题报告:【题目大意】给出一个数独,部分位置已经填上了数,每个格子(x,y)(1<=x,y<=9)有一个权值w(x,y),试找出一种填数独的方案,使得所有格子所填的数字乘以权值之积的和最大,并将这个最大值输出。如果该数独无解,输出-1。【题目分析】数独问题是个非常经典的NP完全问题,没有多项式的算法,只能搜索。首先可以想到枚举,但数据给出的数独空格非常多,最多可能有9^57种状态,是效率极低的算法,对于本题的数据是无法得分的。进一步分析可以想到递归回溯,遇到每个空格,枚举该空格所在的行、列、小九宫已填了哪些数,得出空格可填的数,分别填上这些数并进行下一层的搜索。这样的方法已经远优于枚举,但对于本题大部分数据还是无法出解(实际测试可以得到40%的分数)。为了加快计算一个格子可填的数的速度,我们可以把每行、每列、每个九宫格可填的数用二进制集合表示,每个格子(x,y)当前可填的数的集合就是第x行、第y列以及(x,y)所在小九宫的可填的数集求交。这个操作可以用位运算实现。这样,找可填的数的时间就大大缩短了。实际测试中可以得到75%的分数。上面的方法所得的分数在考场上已经是相当可观,但本题还有进一步的优化余地。有时在数独下方会有一些格子只有一两个可填的数字,而在数独上方的一些格子可能会有很多可填的数字。这时如果按照从上往下搜索的顺序搜索,将会扩展出很多无用的状态。如果是用人脑来做数独的话,必定会先填可行方案少的格子,来给其它格子更多的限制,这样可以剪去很多不可行的分支。所以我们可以预处理求出每个空格可填的方案数,并对它们进行排序。按照这个顺序搜索,将可以得到85%的分数。注意到前面填的数会对后面与它同行、同列、同小九宫的格子造成影响,后面的可填数大小顺序可能有改变。可以考虑在填了一个格子之后,找出后面待填的格子中可填数最少的格子,进行进一步的搜索。这个方法的表现非