题目
（戳我）[https://www.luogu.com.cn/problem/P2765]
思路
两种思路，第一种贪心很明显了，我们直接从第一个开始放球，可以放就放，不能放就新开一个。第二种的话建图，首先我们应该发现这个东西的特点，一个柱子可以放多个球，有多个柱子，但是每个柱子的球是不可能一样的，这和图论里面二分图的最小路径覆盖很像，因此我们选择拆点建图，然后对这个图不断加点，当我的顶点数-最大匹配大于最小路径的时候，就是答案了。贪心大法好！！！
代码实现
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=start;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define MOD 1000000007
#define exp 1e-8
#define N 1000005
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef vector <int> VI;
typedef pair<int ,int> PII;
typedef pair<int ,PII> PIII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
char ch=getchar(); int x=0, f=1;
while(ch<'0'||ch>'9') {
if(ch=='-') f=-1;
ch=getchar();
} while('0'<=ch&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
} return x*f;
}
const int maxn=1e4+10;
const int M=5e5+10;
struct edge {
int u,v,flow,next;
}e[M];
int head[maxn],cnt=-1;
inline void add (int u,int v,int flow) {
e[++cnt]=(edge) {u,v,flow,head[u]};
head[u]=cnt;
}
inline void add_edge (int u,int v,int flow) {
add (u,v,flow);
add (v,u,0);
}
int dis[maxn],cur[maxn];
int ss,s,t,n,m,x,y,ans;
int bfs () {
MT (dis,0);
queue<int > q;
q.push (ss);
dis[ss]=1;
while (q.size ()) {
int x=q.front (); q.pop ();
for (int i=head[x];i!=-1;i=e[i].next) {
if (dis[e[i].v]==0&&e[i].flow) {
dis[e[i].v]=dis[x]+1;
q.push (e[i].v);
}
}
}
return dis[t];
}
int dfs (int now,int nowflow) {
if (now==t) return nowflow;
for (int &i=cur[now];~i;i=e[i].next) {
if (dis[e[i].v]==dis[now]+1&&e[i].flow) {
int canflow=dfs (e[i].v,min (nowflow,e[i].flow));
if (canflow>0) {
e[i].flow-=canflow;
e[i^1].flow+=canflow;
return canflow;
}
}
}
return 0;
}
inline int Dinic () {
int ans=0;
while (bfs ()) {
memcpy (cur,head,sizeof (head));
while (int val=dfs(ss,inf)) ans+=val;
}
return ans;
}
int pre[maxn],vis[maxn];
int main () {
MT (head,-1);
scanf ("%d",&n);
t=10000;
while (1) {
ans++,s++;
rev (i,1,s) if (sqrt (i+s)==(int) (sqrt (i+s))) {
add_edge (i,s+5000,1);
}
add_edge (0,s,1);
add_edge (s+5000,t,1);
int st=Dinic ();
ans-=st;
if (ans>n) break;
}
printf ("%d
",s-1);
rev (i,1,s) {
int k=head[i];
while (k) {
if (!e[k].flow) {
pre[i]=e[k].v-5000;
break;
}
k=e[k].next;
}
}
rev (i,1,s) {
if (vis[i]) continue;
int p=i;
while (p!=-5000) {
vis[p]=1;
printf ("%d ",p);
p=pre[p];
}
cout<<endl;
}
return 0;
}
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=start;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define exp 1e-8
#define N 1000005
#define fi first
#define se second
#define pb push_back
const int mod=1e9+7;
typedef long long ll;
typedef vector <int> VI;
typedef pair<int ,int> PII;
typedef pair<int ,PII> PIII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
char ch=getchar(); int x=0, f=1;
while(ch<'0'||ch>'9') {
if(ch=='-') f=-1;
ch=getchar();
} while('0'<=ch&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
} return x*f;
}
const int maxn=60;
VI v[maxn];
set <int> s;
int n;
void prework () {
rep (i,1,maxn) {
s.insert (i*i);
}
}
int main () {
cin>>n;
int cnt=0,ans=1;
prework ();
while (true) {
rep (i,1,cnt) {
int x=v[i].back ()+ans;
if (s.count (x)) {
v[i].pb (ans);
ans++;
i=0;
continue;
}
}
if (cnt<n) v[++cnt].pb (ans++);
else break;
}
cout<<ans-1<<endl;
rep (i,1,n) {
for (auto it:v[i]) {
printf ("%d ",it);
}
cout<<endl;
}
return 0;
}