【bzoj2661】[BeiJing wc2012]连连看

2014年6月5日1,4898

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

题解

拆点费用流。。

 

  • sad2015年5月28日 上午11:08 回复

    黄学长,你的代码好像WA掉了

    #1  
    • hzwer2015年5月29日 上午9:15 回复
      admin

      已更正

      #11
  • llama2015年11月20日 上午10:46 回复

    黄学长,为什么只建从大的数到小的数的边,然后输出an1,ans2就wa掉了

    #2  
  • Alisa2016年2月24日 下午4:51 回复

    黄学长,为什么是gcd(x,y)==1而不是gcd(y,z)==1,题目说的是y与z互质啊。。。

    #3  
    • hzwer2016年3月6日 上午12:51 回复
      admin

      已更正

      #31
  • DaD3zZ2016年3月21日 下午9:10 回复

    黄学长,同样的处理,跑的zkw就会WA,但是跑mcmf就能A,请问是怎么个情况QAQ…

    #4  
    • hzwer2016年4月11日 下午8:53 回复
      admin

      写错了。。。

      #41
  • YBJaiWYX2016年4月27日 下午9:07 回复

    这道题其实是一个二分图,但是需要打表验证一下,黄学长直接就说了=-=

    #5