题目：http://www.
第一题：BFS+hash算法
第三题写出来了，但是估计肯定超时
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int number[1000000];
int state[1000000][2];
void print(int sum)
{
    int i,min;
    if(state[sum][0]>state[sum][1])
    min=state[sum][1];
    else
    min=state[sum][0];
    //printf("%d\n",min);
    for(i=2;i<=min;i++)
    {
    if(state[sum][0]%i==0&&state[sum][1]%i==0)
    {
    state[sum][0]=state[sum][0]/i;
    state[sum][1]=state[sum][1]/i;
    }
    }
    printf("%d/%d\n",state[sum][0],state[sum][1]);
}
int main()
{
    int i,j,k,count,max=0,n,m;
    int sum;
    scanf("%d %d",&n,&m);
    memset(number,0,sizeof(number));
    for(i=0;i<n;i++)
    scanf("%d",&number[i]);
    for(i=0;i<m;i++)
    max=max+number[i];
    max=max/m;
    for(i=0;i<n;i++)
    for(j=i;j<n;j++)
    {
    sum=0;count=0;
    for(k=i;k<=j;k++)
    {
    sum=sum+number[k];
    count++;
    }
    if(sum/count>max&&count>=m)
    {
    max=sum/count;
    state[max][0]=sum;
    state[max][1]=count;
    }
    }
    if(state[max][1]==1)
    printf("%d\n",state[max][0]);
    else
    print(max);
    //system("pause");
    return 0;
}


[ 本帖最后由 sunyh1999 于 2011-6-13 19:11 编辑 ]

题目呢？

发现有几个错误的地方，现在发上代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int number[1000000];
void print(int a,int b)
{
    int i,min;
    if(a>b)
    min=b;
    else
    min=a;
    //printf("%d\n",min);
    for(i=2;i<=min;i++)
    {
    if(a%i==0&&b%i==0)
    {
    a=a/i;
    b=b/i;
    }
    }
    if(b==1)
    printf("%d\n",a);
    else
    printf("%d/%d\n",a,b);
}
int main()
{
    int i,j,k,count,max=0,n,m;
    int a,b,sum;
    scanf("%d %d",&n,&m);
    memset(number,0,sizeof(number));
    for(i=0;i<n;i++)
    scanf("%d",&number[i]);
    for(i=0;i<m;i++)
    max=max+number[i];
    max=max/m;
    for(i=0;i<n;i++)
    for(j=i;j<n;j++)
    {
    sum=0;count=0;
    for(k=i;k<=j;k++)
    {
    sum=sum+number[k];
    count++;
    }
    if((float)sum/count>max&&count>=m)
    {
    max=sum/count;
    a=sum;
    b=count;
    }
    }
    if(b==1)
    printf("%d\n",a);
    else
    print(a,b);
    system("pause");
    return 0;
}

能解释一下吗？大虾

好久没上来了，差点忘记密码，支持一下！

是哪个僵尸的题？

第一题很显然吧，枚举起点，然后按照每个置换处理就行了，n^2就能过
第三题是凸壳优化的dp, O(n)

为什么是n^2就能过