Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

08/7
09:22
费用流

[bzoj 2661] [BeiJing wc2012]连连看

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 凡是考智商的题里面总会有这么一种消除游戏。不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏。我们的规则是,给出一个闭区间[a,b]中的全部整数,如果其中某两个数x,y(设x>y)的平方差x2-y2是一个完全平方数z2,并且y与z互质,那么就可以将x和y连起来并且将它们一起消除,同时得到x+y点分数。那么过关的要求就是,消除的数对尽可能多的前提下,得到足够的分数。快动手动笔算一算吧。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

只有一行,两个整数,分别表示a,b。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

两个数,可以消去的对数,及在此基础上能得到的最大分数。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

1 15

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

2 34

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

对于30%的数据,1<=a,b<=100
对于100%的数据,1<=a,b<=1000

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

就是一个最大费用最大流的模型,直接做就好了..

c++:

pascal:

 

[bzoj 2661] [BeiJing wc2012]连连看