AC日记——魔术球问题洛谷 P2765

题目描述

«问题描述：

假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。

（1）每次只能在某根柱子的最上面放球。

（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可放11 个球。

«编程任务：

对于给定的n，计算在n根柱子上最多能放多少个球。

输入输出格式

输入格式：

第1 行有1个正整数n，表示柱子数。

输出格式：

程序运行结束时，将n 根柱子上最多能放的球数以及相应的放置方案输出。文件的第一行是球数。接下来的n行，每行是一根柱子上的球的编号。

输入输出样例

输入样例#1：

输出样例#1：

说明

感谢 @PhoenixEclipse 提供spj

思路：

　　因为有数据范围，我们采取二分答案（枚举）；

　　然后，走最大流，当当前球数减去最大流数==n+1时，当前球数-1就是答案；

来，上代码：

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define maxn 4000

using namespace std;

struct EdgeType {

    int to,next,flow;

};

struct EdgeType edge[];

int if_z,n,mid,l,r,cnt,head[maxn],ans;

int s=,t=maxn-,deep[maxn],next[maxn];

bool if_[maxn];

char Cget;

inline void in(int &now)

{

    now=,if_z=,Cget=getchar();

    while(Cget>''||Cget<'')

    {

        if(Cget=='-') if_z=-;

        Cget=getchar();

    }

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

    now*=if_z;

}

inline void edge_add(int u,int v,int w)

{

    edge[++cnt].to=v,edge[cnt].next=head[u],edge[cnt].flow=w,head[u]=cnt;

    edge[++cnt].to=u,edge[cnt].next=head[v],edge[cnt].flow=,head[v]=cnt;

}

bool BFS()

{

    memset(deep,-,sizeof(deep));

    queue<int>que;que.push(s);deep[s]=;

    while(!que.empty())

    {

        int pos=que.front();que.pop();

        for(int i=head[pos];i;i=edge[i].next)

        {

            if(edge[i].flow>&&deep[edge[i].to]<)

            {

                deep[edge[i].to]=deep[pos]+;

                if(edge[i].to==t) return true;

                que.push(edge[i].to);

            }

        }

    }

    return false;

}

int flowing(int now,int flow)

{

    if(flow==||now==t) return flow;

    int oldflow=;

    for(int i=head[now];i;i=edge[i].next)

    {

        if(deep[edge[i].to]!=deep[now]+||edge[i].flow==) continue;

        int pos=flowing(edge[i].to,min(flow,edge[i].flow));

        if(edge[i].to>mid)

        {

            next[now]=edge[i].to-mid;

            if_[next[now]]=true;

        }

        flow-=pos;

        oldflow+=pos;

        edge[i].flow-=pos;

        edge[i^].flow+=pos;

        if(flow==) return oldflow;

    }

    return oldflow;

}

bool check()

{

    cnt=;

    memset(next,,sizeof(next));

    memset(head,,sizeof(head));

    memset(if_,false,sizeof(if_));

    for(int i=;i<=mid;i++)

    {

        for(int j=i+;j<=mid;j++)

        {

            int tmp=sqrt(i+j);

            if(tmp*tmp==i+j) edge_add(i,j+mid,);

        }

    }

    for(int i=;i<=mid;i++)

    {

        edge_add(s,i,);

        edge_add(i+mid,t,);

    }

    int pos=mid;

    while(BFS()) pos-=flowing(s,0x7ffffff);

    if(pos>n) return true;

    else return false;

}

int main()

{

    in(n);

    l=,r=;

    while(l<=r)

    {

        mid=(l+r)>>;

        if(check()) ans=mid,r=mid-;

        else l=mid+;

    }

    mid=ans-;

    check();

    printf("%d\n",mid);

    for(int i=;i<mid;i++)

    {

        if(if_[i]) continue;

        printf("%d",i);

        int pos=i;

        while(next[pos])

        {

            printf(" %d",next[pos]);

            pos=next[pos];

        }

        printf("\n");

    }

    return ;

}

巴特西

AC日记——魔术球问题洛谷 P2765

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章

巴特西

AC日记——魔术球问题 洛谷 P2765

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章

AC日记——魔术球问题洛谷 P2765