魔术球问题
题意简述
题目希望我们在个柱子放上最多的球，并且要求相邻的球之间满足相加为完全平方数的条件。
题解
较显然的一点是，对于递增的来说，其所能放的最多球的数量一定是单调上升的。因为新增加的柱子至少可以比前一个的最大方案多放一个。同时，如果编号为的球已经找不到放下的方案，根据题目要求，大于的球数也一定是不合法的。
再从另一个角度考虑，球数增加时所需要的最少柱子数量也是单调不增的。于是就可以将这题转化为求最大的球数，使得其最小覆盖恰不大于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;
}