黑书上是用二分图的最小路径覆盖来理解这题的，用最小路径覆盖求得后，发现，这个解满足一个公式，我就直接套公式A掉了 = =。。

后用最大匹配做，发现是基本不能做的，因为是倒着匹配的，等于说是，已知有N个柱子，然后找一个数满足最大，等于说是需要枚举这些个数的，啊，我表示压力很大。。。

再者就是，用最大二分匹配打表，从p = 1开始，刚才试了N久，终于打成功了，不过TLE了。。。= =。。。如果把生成数据打下表的话，还是能过滴~

I 公式 n*n/2+n-0.5向下取整

#include <queue>#include <stack>#include <math.h>#include <stdio.h>#include <stdlib.h>#include <iostream>#include <limits.h>#include <string.h>#include <algorithm>using namespace std;int main(){ int n,ncases; scanf("%d",&ncases); while( ncases-- ) { scanf("%d",&n); int ans = (int)(n*n/2.0+n-0.5); printf("%d/n",ans); }return 0;} 

II 打表 = =。。。把生成数据输出再弄个程序打表就好了，懒得弄了。。

#include <queue>#include <stack>#include <math.h>#include <stdio.h>#include <stdlib.h>#include <iostream>#include <limits.h>#include <string.h>#include <algorithm>#define MAX 1500using namespace std;int s[MAX*4];int map[1500][1500];int used[MAX],mat[MAX];void init(){ int i; memset(s,0,sizeof(s)); for(i=1; i*i<MAX*3; i++) s[i*i] = 1;}int Augment(int n,int x){ int i; for(i=1; i<=n; i++) if( !used[i] && map[x][i] ) { used[i] = 1; if( mat[i] == 0 || Augment(n,mat[i]) ) { mat[i] = x; return 1; } } return 0;}int Hungary(int n){ int i,sum = 0; memset(mat,0,sizeof(mat)); for(i=1; i<=n; i++) { memset(used,0,sizeof(used)); if( Augment(n,i) ) sum++; } return sum;}int a[MAX*MAX];int main(){ int n,ncases,i,k; init(); int p = 1; while( p < MAX*4-1 ) { for(i=1; i<p; i++) if( s[i+p] == 1 ) map[i][p] = 1; int ans = Hungary(p); a[p-ans] = p; if( p - ans > 50 ) break; p++; } scanf("%d",&ncases); while( ncases-- ) { scanf("%d",&n); printf("%d/n",a[n]); }return 0;}