题解区的玄学公式：球的个数：(n*(n+2)+(n&1)-2)/2
既然能直接求出球的个数那么就会有贪心法emmm
#include <cstdlib> #include <cstdio> #include <algorithm> #include <iostream> #include <cstring> #include <queue> #include <cmath> using namespace std; #define ll long long #define re register const int N=1e7+10; const int inf=1e9; inline void read(int &a) { a=0; int d=1; char ch; while(ch=getchar(),ch>'9'||ch<'0') if(ch=='-') d=-1; a=ch^48; while(ch=getchar(),ch>='0'&&ch<='9') a=(a<<3)+(a<<1)+(ch^48); a*=d; } int a[60][60]; int f(int x){return x*x;} int main() { int n,m; read(n); m=(n*(n+2)+(n&1)-2)/2; printf("%d ",m); for(re int i=1;i<=m;i++) for(re int j=1;j<=n;j++) { int x=a[j][a[j][0]]; if(!x||f(int(sqrt(x+i)))==x+i) { a[j][++a[j][0]]=i; break; } } for(re int i=1;i<=n;i++) { for(re int j=1;j<=a[i][0];j++) printf("%d ",a[i][j]); putchar(' '); } return 0; }
但是作为一道网络流24题的题目，我觉得应该要用网络流的方法写才能锻炼自己，如果对最大流模板熟悉，那么这道题的难点只是建图。
这题只要把一个点分割成两个点，然后建图就ok了
#include <cstdlib> #include <cstdio> #include <algorithm> #include <iostream> #include <cstring> #include <queue> #include <cmath> using namespace std; #define ll long long #define re register const int N=1e6+10; const int inf=1e9; inline void read(int &a) { a=0; int d=1; char ch; while(ch=getchar(),ch>'9'||ch<'0') if(ch=='-') d=-1; a=ch^48; while(ch=getchar(),ch>='0'&&ch<='9') a=(a<<3)+(a<<1)+(ch^48); a*=d; } struct note { int next,v,dis; }edge[N]; int cnt=-1,head[N],n,dep[N],p[60],nxt[N]; bool vis[N]; inline void add(int u,int v,int dis) { edge[++cnt].next=head[u]; edge[cnt].v=v; edge[cnt].dis=dis; head[u]=cnt; edge[++cnt].next=head[v]; edge[cnt].v=u; edge[cnt].dis=0; head[v]=cnt; } queue <int> q; inline bool bfs(int s,int t) { memset(dep,0x7f,sizeof(dep)); while(!q.empty()) q.pop(); dep[s]=0; q.push(s); while(!q.empty()) { int now=q.front(); q.pop(); for(re int i=head[now];i!=-1;i=edge[i].next) { if(dep[edge[i].v]>inf&&edge[i].dis) dep[edge[i].v]=dep[now]+1,q.push(edge[i].v); } } if(dep[t]<inf) return 1; return 0; } inline int dfs(int now,int t,int limit) { if(now==t) return limit; for(re int i=head[now];i!=-1;i=edge[i].next) { if((dep[edge[i].v]==dep[now]+1)&&edge[i].dis) { int f=dfs(edge[i].v,t,min(limit,edge[i].dis)); if(f>0) { edge[i].dis-=f; edge[i^1].dis+=f; if(now!=0&&edge[i].v!=N-1) nxt[now>>1]=edge[i].v>>1; return f; } } } return 0; } inline int dinic(int s,int t) { int flow=0; while(bfs(s,t)) { while(int di=dfs(s,t,inf)) flow+=di; } return flow; } int main() { memset(head,0xff,sizeof(head)); int s=0,t=N-1,k; n=0; read(k); int now=0; while(now<=k) { n++; add(s,(n<<1),1); add((n<<1)|1,t,1); for(re int i=sqrt(n)+1;i*i<(n<<1);i++) add((i*i-n)<<1,(n<<1)|1,1); int x=dinic(s,t); if(!x) p[++now]=n; } printf("%d ",n-1); for(re int i=1;i<=k;i++) { if(vis[p[i]]) continue; int x=p[i]; vis[x]=1; while(x!=0) { printf("%d ",x); x=nxt[x]; vis[x]=1; } putchar(' '); } return 0; }