求noip2009中的两道题的题解

2.Hankson的趣味题(son.pas/c/cpp)

分析

主要考察数学知识.辗转相除法求最大公约数应该是大家都熟悉的,不再多说.

算法一:

在[1,b1]范围内穷举x,按题目要求判断即可,算法效率O(b1),期望得分50.

算法二:

因为gcd(x,a0)=a1,不妨设x=p*a1.

所以lcm(x,b0)=lcm(p*a1,b0)=p*a1*b0/gcd(p*a1,b0)=b1

可以得到p=b1* gcd(p*a1,b0)/a1/b0,枚举gcd(p*a1,b0)后可以求得p,继而求得x,检验gcd(p*a1,a0)是否为a1即可.

因为gcd(p*a1,b0)是b1的约数,所以枚举量为O(sqrt(b1)),最后复杂度为O(N*sqrt(b1)*log(b1)),期望得分100.

算法三:

因为lcm(x,b0)=x*b0/gcd(x,b0)=b1,所以x/gcd(x,b0)=b1/b0.不妨把b1/b0分解质因数,又一位x有约数a1,结合素数表进行搜索也能快速出结果.效率不好分析,期望得分100.

3.最优贸易(trade.pas/c/cpp)

分析

算法一:

结合数据规模.对于30%的数据,可以用另类求最大最小的类似floyed的立方算法解决.对于50%的数据,由题意可知这部分数据死拓扑有序的,直接dp即可.用F表示从第一个点出发到达第i个点用最小钱能买到的水晶球.状态转移方程如下F=min(F[j],A),如果第i个点能到达第N个点,那么用A-F更新答案.这种算法需要结合数据,编程复杂度较大,如果拓扑排序写得较好可以得到超过50分的分数.期望得分(50-80).

算法二:

求强连通分支后,很显然图仍然是拓扑有序的.用类似的dp解决即可.但是强连通好像是超过联赛大纲的,而且编程复杂度较高,且由于方法十分经典,不再详细介绍.复杂度O(N+M),期望得分100.

算法三:

用另类spfa(即求出最大最小值),求出从第一个点出发到其他点能买到水晶球的最小代价.将所有边反向以后,从N个点出发求出第N个点到第i个点能卖出水晶球的最大代价,这个代价对应于原图中第i个点到第N个点能获得的最大收益.对于每个点,用最大收益-最小代价更新答案即可.复杂度不好估计,不过稀疏图spfa的效率是很有保证的,且编程复杂度较小,是一种比较优秀的算法.期望得分100.