贪心做法

每次尽可能选择已经放过球的柱子

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int num[100][1000],n;bool chk(const int &a,const int &b){    int t=sqrt(a+b);    return t*t==a+b;}int main(){    cin>>n;    int cnt=0;    while(++cnt){        bool f=0;        for(int i=1;i<=n;i++){            if(num[i][0]&&chk(num[i][num[i][0]],cnt)) num[i][++num[i][0]]=cnt,f=1;            if(f) break;        }        for(int i=1;i<=n;i++){            if(!num[i][0]) num[i][++num[i][0]]=cnt,f=1;            if(f) break;        }        if(!f) break;    }    printf("%d\n",cnt-1);    for(int i=1;i<=n;i++){        for(int j=1;j<=num[i][0];j++){            printf("%d ",num[i][j]);        }        printf("\n");    }    return 0;}
        
       
      
     
    

网络流做法

我们可以将其转化成最小路径覆盖问题来做,

从小到大枚举答案,对于每一个新加进去的答案,寻找在已加进去的点中,满足题意的点,连一条边.

我们发现连好以后这是一个DAG图,其最小路径覆盖就是需要的最少柱子数,我们要找到一个最小路径覆盖<=n的最大解,即最后的答案

求最小路径覆盖可以用二分图做

这里有几个优化,具体见代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int init(){ int rv=0,fh=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); } while(c>='0'&&c<='9'){ rv=(rv<<1)+(rv<<3)+c-'0'; c=getchar(); } return fh*rv;}const int MAXN=5000,MAXM=50005;int head[MAXN],n,cur[MAXN],dep[MAXN],nume,s,t,maxflow;queue
           
             q;bool f[MAXN];struct edge{ int to,nxt,cap,flow;}e[MAXM<<1];void adde(int from,int to,int cap){ e[++nume].to=to; e[nume].nxt=head[from]; head[from]=nume; e[nume].cap=cap;}bool chk(const int &a,const int &b){ int t=sqrt(a+b); return t*t==a+b;}bool bfs(){ memset(dep,0,sizeof(dep)); while(!q.empty()) q.pop(); q.push(s);dep[s]=1; while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(!dep[v]&&e[i].flow
            
             n) break; } printf("%d\n",cnt-1); for(int k=1;k<=n;k++){ for(int i=1;i