魔术球问题

题意简述

题目希望我们在$n$个柱子放上最多的球，并且要求相邻的球之间满足相加为完全平方数的条件。

题解

较显然的一点是，对于递增的$n$来说，其所能放的最多球的数量一定是单调上升的。因为新增加的柱子至少可以比前一个的最大方案多放一个。同时，如果编号为$x$的球已经找不到放下的方案，根据题目要求，大于$x$的球数也一定是不合法的。

再从另一个角度考虑，球数增加时所需要的最少柱子数量也是单调不增的。于是就可以将这题转化为求最大的球数，使得其最小覆盖恰不大于n。如果你还没有做过最小覆盖相关的题目，简单来说，就是你需要把一些元素分成互不相交的集合，且使得集合数最小。参考最小路径覆盖问题，这两者的建模方式是类似的，在本题中每尝试增加一个球就让它尝试和之前的球连边即可。
这题就这么解决啦，关键的地方在于找出单调性和由最大转化为最小可行问题。

（关于球的枚举上界问题，可以先设一个较大的值再跑一下极限数据看看）

代码

#include <cstdio>
#include <cstring>
#include <cmath>
const int maxn=8000;
const int maxm=5e5+10;
const int INF=0x3f3f3f3f;
const double eps=1e-6;
int cur[maxn],head[maxn],to[maxm],nxt[maxm],val[maxm];
int tot=1;
int n,s,t;
int dep[maxn],l[maxn],r[maxn];
struct Queue
{
	int a[maxn];
	int l,r;
	Queue() {l=1,r=0;}
	void push(int x) {a[++r]=x;}
	void pop() {l++;}
	int front() {return a[l];}
	bool empty() {return l>r;}
}q;

int min(int x,int y) {return x<y?x:y;}
bool check(int x,int y)
{
	double tmp=sqrt(x+y);
	return tmp-(int)tmp<eps;
}
void add(int u,int v,int w)
{
	nxt[++tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	val[tot]=w;
}
void cancel()
{
	int u=to[tot],v=to[tot^1];
	head[u]=nxt[head[u]];
	head[v]=nxt[head[v]];
	tot-=2;
}
bool bfs()
{
	memset(dep, 0x3f, sizeof(dep));
	dep[s]=0;
	q=Queue();
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for (int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if (val[i]>0&&dep[v]>dep[u]+1)
			{
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[t]!=INF;
}
int dfs(int u,int minf)
{
	if (u==t)
		return minf;
	
	int used=0;
	for (int &i=cur[u];i;i=nxt[i])
	{
		int v=to[i];
		if (val[i]>0&&dep[v]==dep[u]+1)
		{
			int flow=dfs(v, min(minf-used, val[i]));
			if (flow)
			{
				used+=flow;
				val[i]-=flow;
				val[i^1]+=flow;
				if (used==minf)
					break;
			}
		}
	}
	return used;
}
int main()
{
	scanf("%d",&n);
	int lim=n*n;
	s=0,t=lim*2+1;
	int v;
	int pre_tot=1;
	for (v=1;v<=lim;v++)
	{
		for (int i=2;i<=tot;i++)
			val[i]=i&1?0:1;
		add(s, v, 1),add(v, s, 0);
		add(v+lim, t, 1),add(t, v+lim, 0);
		for (int u=v-1;u>=1;u--)
			if (check(u, v))
				add(u, v+lim, 1),add(v+lim, u, 0);

		int ans=0;
		while(bfs())
		{
			for (int i=s;i<=v+lim;i++)
				cur[i]=head[i];
			ans+=dfs(s, INF);
		}
		if (v-ans>n)
		{
			v--;
			break;
		}
		pre_tot=tot;
	}

	while(tot>pre_tot)
		cancel();
	for (int i=2;i<=tot;i++)
		val[i]=i&1?0:1;
	
	while(bfs())
	{
		for (int i=s;i<=v+lim;i++)
			cur[i]=head[i];
		dfs(s, INF);
	}

	for (int u=1;u<=v;u++)
		for (int i=head[u];i;i=nxt[i])
		{
			if (!val[i]&&to[i]!=s)
				r[u]=to[i]-lim,l[to[i]-lim]=u;
		}

	printf("%d\n",v);
	for (int i=1;i<=v;i++)
	{
		if (l[i])
			continue;
		int u=i;
		while(u)
		{
			printf("%d ",u);
			u=r[u];
		}
		putchar('\n');
	}
	return 0;
}