题目：

分析：做这个题目的时候是在图论的题目里面看到的。到时读了题目推了一下，发现好像有点规律。试了一下果然过了。

后来看了一下数据，才50。那么试了一下模拟，也过了。

好像zoj有一道题目卡模拟，模拟的时候必须贪心一下才干过

这道题出题人的意图在于考大家的：二分图最小路径覆盖。

把每个球看做一个点，然后假设两个和为平方数的话就给这两个点之间连接一条边，然后用一个特殊的匹配算法。类似于匈牙利算法。可是每次找匹配的时候增加一条边上连接的有匹配的话就不能匹配，最后求一个最大匹配就好了。这个题目50个点，当然要预处理成离线的。

假设每次都建图跑的话时间复杂度是非常高的，所以我们能够用标记的方法。假设匹配过的就不用再匹配了。

这样能减少非常多时间，可是还是非常长。

找规律代码：

#include 
     
      int ans[55];void isit(){    ans[1]=1,ans[2]=3;    for(int i=3;i<51;i++)        ans[i]=ans[i-1]+(i+1)/2 * 2;}int main(){    int T,n;isit();    scanf("%d",&T);    for(;T--&&scanf("%d",&n);printf("%d\n",ans[n]));}
     

暴力代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;stack
        
          st[60];int ans[60];void isit(){    int tmp=1,i=1;    while(i<55)    {        int ok=0;        for(i=1;!st[i].empty();i++)        {            int zhi = st[i].top()+tmp;            int sq=sqrt(zhi);            if(sq * sq == zhi)            {                st[i].push(tmp);                ok=1;                break;            }        }        if(!ok){            st[i].push(tmp);            ans[i]=tmp-1;        }        tmp++;    }}int main(){    int T,n;isit();    scanf("%d",&T);    for(;T--&&scanf("%d",&n);printf("%d\n",ans[n+1])){}}
        
       
      
     

二分图匹配代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 60;const int M = 1500;int ans[N];bool  ok[M*2+10];bool mp[M][M];int mx[M],my[M]; //mx保存正向边 my保存反向边bool used[M]; //bool dfs(int v) {     for (int u = 1; u < v; ++u) //优化         if (mp[v][u] && !used[u]) {            used[u] = true;             if (my[u] == -1 || dfs(my[u])) {  //一直向下找                 my[u] = v;                 mx[v] = u;                 return true;             }         }     return false;}int Max_Pi(int ans,int n)  //最大匹配{    for(int i=1;i<=n;i++)    {        if(mx[i]<0){            memset(used,false,sizeof(used));            if(dfs(i))                ans++;        }    }    return ans;}void Min_Road()  //最小路径覆盖{    memset(mx,-1,sizeof(mx)); //优化    memset(my,-1,sizeof(my));    for(int i=1;i*i<=2*M;i++)        ok[i*i]=true;    ans[1]=1;    int tmp=0;    for(int i=2;i<=M;i++)    {        for(int j=1;j
         
          55)            break;    }//    for(int i=1;i<=50;i++)//        printf("%d ",ans[i]);}int main(){    int T,n;Min_Road();    scanf("%d",&T);    for(;T--&&scanf("%d",&n);printf("%d\n",ans[n])){}}