Eva

Time Limit: 10 Sec  Memory Limit: 128 MB
Description

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

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

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

1 15

2 34

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

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

/**************************************************************

    Problem: 2661

    User: ictsing

    Language: C++

    Result: Accepted

    Time:200 ms

    Memory:79464 kb

****************************************************************/

 

//BZOJ2661 [BeiJing wc2012]连连看

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <queue>

using namespace std;

const int inf = 1000000000;

int ans1=0,ans2=0;

const int mt = 2000+5;

const int mm = 2000000+5;

int cap[mm<<1],cost[mm<<1],adj[mt],fr[mm<<1],to[mm<<1],nxt[mm<<1];

int ecnt=1;

int dis[mt<<1],cur[mt];

bool inq[mt];

int s=0,t=2000+3;

queue<int>q;

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int gcd(int a,int b)

{

    if(b==0) return a;

    return gcd(b,a%b);

}

bool judge(int x,int y)

{

    if(x<y) swap(x,y);

    int zz=x*x-y*y;

    int tmp=sqrt(zz);

    if(tmp*tmp==zz&&gcd(x,y)==1) return true;

    return false;

}

void adde(int u,int v,int cc,int ccc)

{

    ecnt++,fr[ecnt]=u,to[ecnt]=v,nxt[ecnt]=adj[u],cap[ecnt]=cc,cost[ecnt]=ccc,adj[u]=ecnt;

    ecnt++,fr[ecnt]=v,to[ecnt]=u,nxt[ecnt]=adj[v],cap[ecnt]=0,cost[ecnt]=-ccc,adj[v]=ecnt;

}

bool spfa()

{

    while(!q.empty()) q.pop();

    for(int i=s;i<=t;i++) dis[i]=-inf,inq[i]=0;

    q.push(s),dis[s]=0,inq[s]=1;

    while(!q.empty())

    {

        int u=q.front();q.pop();inq[u]=0;

        for(int i=adj[u];i;i=nxt[i])

        {

            int v=to[i];

            if(dis[v]<dis[u]+cost[i]&&cap[i])

            {

                dis[v]=dis[u]+cost[i];cur[v]=i;

                if(!inq[v]) inq[v]=1,q.push(v); 

            }

        }

    }

    return dis[t]!=-inf;

}

void mcf()

{

    while(spfa())

    {

        int tmp=inf;

        for(int i=cur[t];i;i=cur[fr[i]]) tmp=min(tmp,cap[i]);

        ans2+=dis[t]*tmp;

        for(int i=cur[t];i;i=cur[fr[i]]) cap[i]-=tmp,cap[i^1]+=tmp;

    }

}

int main()

{

    int a=read(),b=read();

    for(int i=a;i<=b;i++)

        for(int j=a;j<=b;j++)

        {

            if(judge(i,j)&&i!=j)

            {

                adde(i,j+1000,1,i+j);

            }

        }

    for(int i=a;i<=b;i++)

        adde(s,i,1,0),adde(i+1000,t,1,0);

    mcf();

    for(int i=2;i<=ecnt;i+=2)

        if(to[i]==t&&!cap[i]) ans1++;

    printf("%d %d\n",ans1/2,ans2/2);

    return 0;

}