NKOJ 1004

http://acm.nankai.edu.cn/p1004.html

看了下ac的大部分都是用一个高度总结的数学公式，有没有直接对应题目的算法？

//南开oj-1004
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
    int n,m=1,i,j,k,flag,*p;
    scanf("%d",&n);
    p=(int *)calloc(n,sizeof(int));
    while(1)
    {
        flag=0;
        for(i=0;i<n;i++)
            if(p[i]==0)
            {
                p[i]=m;
                flag=1;
                break;
            }
            else
            {
                k=p[i]+m;
                j=(int)sqrt(k);
                if(k==j*j)
                {
                    p[i]=m;
                    flag=1;
                    break;
                }
                else
                    continue;
            }
        if(!flag)
            break;
        m++;
    }
    m--;
    free(p);
    printf("%d\n",m);
    getchar();
    getchar();
    return 0;
}
这题用啥公式啊，我这样做的，AC！

贪心可以过，但我没有看出贪心性质。

/**
my code for this problem.

the formula can be found by

first try on a few test cases for n small
then apply mathematical induction
*/

main()
{
    int n;

    while (scanf("%d", &n) != -1)
        printf("%d\n", n*(n+1)/2+(n-1)/2);

}

搜索+贪心，但是也看不出贪心性质，猜的。

楼上的完全不懂，数学真好。

我也写了个：
#include <iostream>
#include <cmath>
using namespace std;
const int MAX=50;
int a[MAX]={0};
bool Sqn(int n)//判断是不是平方数
{
    if(floor(sqrt(n))*floor(sqrt(n))==n)
        return true;
    return false;
}
int main()
{
//    cout<<Sqn(9)<<endl;
    int N;
    int flag=1;
    while(flag)//输入
    {
        cout<<"Please input the number of stick(N):"<<endl;
        cin>>N;
        if(N>=1 && N<=50)
            flag=0;
        else
            cout<<"The number your input is boundary!"<<endl;
    }
    int cgd=1;//the candiedgound number
    int flg=1;
    while(flg)//put candiedgound
    {
        for(int i=0;i<N;i++)
        {
            if(a[i]==0 || Sqn(a[i]+cgd))
            {
                a[i]=cgd;
                cgd++;
                i=-1;//从零开始找
            }
        }
        cgd--;//减去不满足条件的最后一次加一
        flg=0;
        
    }
    cout<<"The largest number is:";
    cout<<cgd<<endl;
    return 0;
}