P2765 魔术球问题

题目描述

«问题描述：

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

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

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

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

«编程任务：

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

输入格式

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

输出格式

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

输入输出样例

输入 #1

输出 #1

说明/提示

感谢 @PhoenixEclipse 提供spj

4<=n<=55

？就是说说样例看

有4个柱子就是相当于有4条路径问这些路径上最多能一共有多少个点并且路径上相邻的两个点必须和为完全平方数

也就是说。。。找出来最大数量使得放在4个柱子上

是二分答案吗？QAQ 仿佛明白了什么

二分答案枚举放多少个球

然后先把球的编号预先处理好连边

求一下最小路径看是不是小于等于4 如果是就把球数再增多一些否则就减少QAQ 看起来像是能跑过的样子诶~

答案是x

x^3匈牙利 x^2建图 logx跑二分答案

那么怎样输出方案呢？？

hav里不是就存储着匹配吗

具体看代码QAQ

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
const int maxn=2005;
int n;
vector<int> v[maxn];
bool Check[maxn<<1];
int vis[maxn],hav[maxn];int tim;
bool beprint[maxn];
bool Dfs(int rt)
{
    for(int i=0;i<v[rt].size();i++)
    {
        int to=v[rt][i];
        if(vis[to]!=tim)
        {
            vis[to]=tim;
            if(!hav[to]||Dfs(hav[to]))
            {
                hav[to]=rt;
                return true;
            }
        }
    }
    return false;
}
void Print(int mid)
{
    for(int i=1;i<=mid;i++)
        if(!beprint[i])
        {
            int x=i;
            while(x!=0)
            {
                printf("%d ",x);
                beprint[x]=true;
                x=hav[x];
            }
            putchar('
');
        }
}
bool Judge(int mid,bool ff=false)
{
    for(int i=1;i<=mid;i++)
        for(int j=1;j<i;j++)
            if(Check[i+j])
                v[i].push_back(j);//j比i小 
    int res=0;
    for(int i=1;i<=mid;i++)
        tim++,res+=Dfs(i);
    if(ff)
        Print(mid);
    for(int i=1;i<=mid;i++)
        hav[i]=0,v[i].clear();
    return mid-res<=n;
}
int main()
{
    scanf("%d",&n);    
    for(int i=1;i*i<maxn*2;i++)
        Check[i*i]=true;
    int l=1,r=1605,mid,ans;
    while(l!=r)
    {
        mid=(l+r)>>1;
        if(Judge(mid))
            l=mid+1;
        else
            r=mid;     
    }
    ans=l-1;
    printf("%d
",ans);
    Judge(ans,1);
    
}