2015浙江财经大学ACM有奖周赛（一） 题解报告

2015浙江财经大学ACM有奖周赛（一） 题解报告

命题：丽丽&&黑鸡

这是命题者原话。

题目涉及的知识面比较广泛，有深度优先搜索、广度优先搜索、数学题、几何题、贪心算法、枚举、二进制等等...

有些题目还需要大家对程序的效率做出优化..大一的小宝宝可能有一些吃不消..当成是一种体验就好了。

题解目录：

ZUFE OJ 2307: 最长连续不下降子串

ZUFE OJ 2308: Lucky Number

ZUFE OJ 2309: 小明爱吃面

ZUFE OJ 2310: 小明爱消除

ZUFE OJ 2311: 找数字

ZUFE OJ 2312: 简单数学题

ZUFE OJ 2313: 字符串还原

ZUFE OJ 2314: 矩形周长

ZUFE OJ 2315: 小明的智力

ZUFE OJ 2316: 水题

ZUFE OJ 2317: 画个圈圈

ZUFE OJ 2318: 跳格子

ZUFE OJ 2320: 高中几何没学好

ZUFE OJ 1606: 清洁公司

ZUFE OJ 2323: 黑鸡跑1000

/*

ZUFE OJ 2307: 最长连续不下降子串

时间复杂度：o(n)

题解：输入a[1]到a[n]

补上a[0]为负无穷大，a[n+1]为无穷大

初始化k为1，ans为0

然后一个一个a[i]扫下去 (1<=i<=n+1)

如果a[i]<a[i-1]，那么更新ans=max(ans,k);

否则k=k+1;

最后ans就是答案

*/

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

using namespace std;

const int maxn=+;

const int INF=0x7FFFFFFF;

int a[maxn],ans,k,n;

void init()

{

    for(int i=; i<=n; i++) scanf("%d",&a[i]);

    a[]=INF;a[n+]=-INF;

}

void slove()

{

    while(~scanf("%d",&n))

    {

        init();

        ans=;

        k=;

        for(int i=; i<=n+; i++)

        {

            if(a[i]<a[i-])

            {

                ans=max(ans,k);

                k=;

            }

            else k++;

        }

        printf("%d\n",ans);

    }

}

int main()

{

    slove();

    return ;

}

/*

ZUFE OJ 2308: Lucky Number

题解：设输入的n有x位，设Q等于10的x次方

n*n最后的x位就是 (n*n)%Q

那么只要判断 (n*n)%Q 和 n 是否相等就可以了

要注意的一点就是 0<n<1e9

n*n会超出int范围，所以用long long存储

*/

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

using namespace std;

long long n;

long long _n;

long long n2;

int x;//n有x位

void slove()

{

    while(~scanf("%lld",&n))

    {

        _n=n; x=;

        while(_n) x=x+, _n=_n/; //得到n有几位

        if((n*n)%((long long)pow(10.0,x))==n) printf("Yes\n");

        else printf("No\n");

    }

}

int main()

{

    slove();

    return ;

}

/*

ZUFE OJ 2309: 小明爱吃面

时间复杂度：o(n)

题解：一个简单的贪心题

对于第i天，简单的说就是：是今天买，还是之前买？

当然是要选择从第1天到当前天，价格最小的那一天买下今天所需的粮食。

今天吃的价格其实就是之前那些天中最小的价格

处理出每天的价格之后，求和即可。

PS：语文不好...描述的可能不是很清楚。

*/

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

using namespace std;

const int maxn=+;

int a[maxn],p[maxn];

int n,ans;

void init()

{

    for(int i=;i<=n;i++)

        scanf("%d%d",&a[i],&p[i]);

    ans=;

}

void slove()

{

    while(~scanf("%d",&n))

    {

        init();

        for(int i=;i<=n;i++)

            p[i]=min(p[i-],p[i]);//找出每一天的价格

        for(int i=;i<=n;i++)

            ans=ans+a[i]*p[i];

        printf("%d\n",ans);

    }

}

int main()

{

    slove();

    return ;

}

/*

ZUFE OJ 2310: 小明爱消除

时间复杂度：o(n)

题解：此题属于脑洞题，需要细细咀嚼

      （描述起来比较费劲，略）

*/

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

using namespace std;

const int maxn=+;

int tot[maxn*];

int ans,n;

void init()

{

    memset(tot,,sizeof tot);

    ans=;

}

void slove()

{

    while(~scanf("%d",&n))

    {

        init();

        for(int i=; i<=n; i++)

        {

            int x;

            scanf("%d",&x);

            tot[x]++;

        }

        int k=,m;

        while(k<*maxn)

        {

            m=tot[k]/;

            tot[k]=tot[k]%;

            tot[k+]=tot[k+]+m;

            k++;

        }

        for(int i=; i<*maxn; i++)

            ans=ans+tot[i];

        printf("%d\n",ans);

    }

}

int main()

{

    slove();

    return ;

}

/*

ZUFE OJ 2311: 找数字

时间复杂度：o(n*n)

题解：开一个数组记录每个数字有几个

      tot[x]=y 代表x有y个！

      然后两层循环枚举B和C

      枚举到的时候 tot[B]--,tot[C]--;

      然后验证tot[B+C]是否大于0，即A是否存在

      大于零则表示存在。

      否则不存在。

*/

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

using namespace std;

const int maxn=+;

int tot[maxn],a[maxn];

int n;

void slove()

{

    while(~scanf("%d",&n))

    {

        memset(tot,,sizeof tot);

        for(int i=; i<=n; i++)

        {

            scanf("%d",&a[i]);

            tot[a[i]]++;

        }

        int ans=;

        for(int i=; i<=n; i++)

        {

            for(int j=i+; j<=n; j++)

            {

                tot[a[i]]--;

                tot[a[j]]--;

                if(tot[a[i]+a[j]]>)

                {

                    ans=;

                    break;

                }

                tot[a[i]]++;

                tot[a[j]]++;

            }

            if(ans==) break;

        }

        if(ans==) printf("NO\n");

        else printf("YES\n");

    }

}

int main()

{

    slove();

    return ;

}

/*

ZUFE OJ 2312: 简单数学题

题解：数学题，a的b次方和c的d次方都很大，直接判断是做不出来的。

如果我们能找到一个函数F(x)是单调的，

而F(X)的值又比较好算，那么可以通过比较F(X)的大小来判断自变量的大小。

令F(X)=log(X)，a的b次方和c的d次方当做自变量。

那么接下来只要判断log(a的b次方)和log(c的d次方)的大小

就可以判断a的b次方和c的d次方的大小了。

而log(a的b次方)=b*log(a)，log(c的d次方)=d*log(c)，很容易计算。

判断相等的时候注意一下精度问题。

*/

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

using namespace std;

double a,b,c,d;

int main()

{

    while(~scanf("%lf%lf%lf%lf",&a,&b,&c,&d))

    {

        double ans1=b*log(a);

        double ans2=d*log(c);

        if(fabs(ans1-ans2)<0.000001) printf("=\n");

        else if(ans1>ans2) printf(">\n");

        else printf("<\n");

    }

    return ;

}

/*

ZUFE OJ 2313: 字符串还原

时间复杂度：o(n)

题解：水题，搞之...

*/

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

using namespace std;

const int maxn=+;

char s[maxn];

int T;

void slove()

{

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s",s);

        int len=strlen(s);

        for(int i=;i<len;i++)

            if(i%==) printf("%c",s[i]);

        printf("\n");

        for(int i=len-;i>=;i--)

            if(i%==) printf("%c",s[i]);

        printf("\n");

    }

}

int main()

{

    slove();

    return ;

}

/*

ZUFE OJ 2314: 矩形周长

时间复杂度：o(sqrt(n))

题解：枚举一下边长就可以了

*/

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

using namespace std;

const int INF=0x7FFFFFFF;

int T,n;

void slove()

{

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        int MaxL=sqrt(1.0*n);

        int ans=INF;

        for(int i=;i<=MaxL;i++)

        {

            if(n%i!=) continue;

            else

            {

                if(*(i+n/i)<ans)

                    ans=*(i+n/i);

            }

        }

        printf("%d\n",ans);

    }

}

int main()

{

    slove();

    return ;

}

/*

ZUFE OJ 2315: 小明的智力

时间复杂度：o(n)

题解：简单的贪心题

      先排序，然后吃2，最后吃1

      找到第一个比p大的位置

      从这个位置开始吃2，吃完2 最后吃1

*/

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

using namespace std;

const int maxn=+;

int a[maxn];

bool flag[maxn];

int T,n,p;

void slove()

{

    scanf("%d",&T);

    while(T--)

    {

        memset(flag,,sizeof flag);

        scanf("%d%d",&n,&p);

        for(int i=;i<=n;i++)

            scanf("%d",&a[i]);

        sort(a+,a+n+);

        int now=n+;

        for(int i=;i<=n;i++)

        {

            if(a[i]>p)

            {

                now=i;

                break;

            }

        }

        for(int i=now;i<=n;i++)

            if(a[i]>p)

                flag[i]=,p=p+;

        for(int i=;i<=n;i++)

            if(flag[i]==) p=p+;

        printf("%d\n",p);

    }

}

int main()

{

    slove();

    return ;

}

/*

ZUFE OJ 2316: 水题

时间复杂度：o(n)

题解：水题，搞之...

*/

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

using namespace std;

const int INF=0x7FFFFFFF;

const int maxn=+;

int T,ans,n;

int a[maxn];

void slove()

{

    scanf("%d",&T);

    while(T--)

    {

        ans=-INF;

        scanf("%d",&n);

        for(int i=;i<=n;i++) scanf("%d",&a[i]);

        for(int i=;i<=n;i++)

            if(a[i]-a[i-]>ans)

                ans=a[i]-a[i-];

        printf("%d\n",ans);

    }

}

int main()

{

    slove();

    return ;

}

/*

ZUFE OJ 2317:画个圈圈

*/

#include<stdio.h>

#include<math.h>

#include<map>

#include<algorithm>

#include<string.h>

using namespace std;

const int maxn=+;

int ans,N,M;

char Map[maxn][maxn];

bool flag[maxn][maxn];

char sign;

int dir[][]= {{-,},{,},{,-},{,}};

void init()

{

    memset(flag,,sizeof flag);

    ans=;

}

void dfs(int x,int y,int Dir)

{

    if(flag[x][y]==&&Dir!=-)

    {

        ans=;

        return;

    }

    flag[x][y]=;

    for(int i=; i<; i++)

    {

        int NewX=x+dir[i][];

        int NewY=y+dir[i][];

        if(Dir==&&i==) continue;

        if(Dir==&&i==) continue;

        if(Dir==&&i==) continue;

        if(Dir==&&i==) continue;

        if(Map[NewX][NewY]!=sign) continue;

        if(NewX<||NewX>=N) continue;

        if(NewY<||NewY>=M) continue;

        dfs(NewX,NewY,i);

        if(ans) return;

    }

}

void slove()

{

    while(~scanf("%d%d",&N,&M))

    {

        for(int i=; i<N; i++)

            scanf("%s",Map[i]);

        init();

        for(int i=; i<N; i++)

        {

            for(int j=; j<M; j++)

            {

                sign=Map[i][j];

                memset(flag,,sizeof flag);

                dfs(i,j,-);

                if(ans) break;

            }

            if(ans) break;

        }

        if(ans==) printf("Yes\n");

        else printf("No\n");

    }

}

int main()

{

    slove();

    return ;

}

/*

ZUFE OJ 2318: 跳格子

时间复杂度：不会算

题解：BFS

*/

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

using namespace std;

const int INF=0x7FFFFFFF;

int dir[][]={{-,},{,},{,-},{,}};

const int maxn=+;

int N,M,ans;

int Sx,Sy,Ex,Ey;

int Map[maxn][maxn];

int flag[maxn][maxn];

struct Point

{

    int x,y;

    int tot;

};

queue<Point>Q;

void BFS()

{

    while(!Q.empty()) Q.pop();

    for(int i=;i<maxn;i++)

        for(int j=;j<maxn;j++)

            flag[i][j]=INF;

    Point p;

    p.x=Sx; p.y=Sy; p.tot=;

    Q.push(p);

    ans=-;

    flag[Sx][Sy]=;

    while(!Q.empty())

    {

        Point h=Q.front(); Q.pop();

        if(h.x==Ex&&h.y==Ey)

        {

            ans=h.tot;

            break;

        }

        for(int i=;i<;i++)

        {

            int NewX=h.x+dir[i][];

            int NewY=h.y+dir[i][];

            if(NewX>=&&NewX<=N)

            {

                if(NewY>=&&NewY<=M)

                {

                    if(Map[NewX][NewY]!=)

                    {

                        if(flag[NewX][NewY]>h.tot+)

                        {

                            flag[NewX][NewY]=h.tot+;

                            Point x;

                            x.x=NewX;

                            x.y=NewY;

                            x.tot=h.tot+;

                            Q.push(x);

                        }

                    }

                }

            }

        }

    }

    printf("%d\n",ans);

}

void slove()

{

    while(~scanf("%d%d",&N,&M))

    {

        for(int i=;i<=N;i++)

            for(int j=;j<=M;j++)

                scanf("%d",&Map[i][j]);

        for(int i=;i<=N;i++)

            for(int j=;j<=M;j++)

            {

                if(Map[i][j]==) Sx=i,Sy=j;

                if(Map[i][j]==) Ex=i,Ey=j;

            }

        BFS();

    }

}

int main()

{

    slove();

    return ;

}

/*

ZUFE OJ 2320: 高中几何没学好

时间复杂度：o(1)

题解：连接AX

      设三角形AFX面积为e，三角形AXE面积为f

      得到三个方程

      e+f=d

      f/c=(a+d)/(b+c)

      e/a=(c+d)/(a+b)

      三个未知量都可以解出来

*/

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

double a,b,c,k;

double e,f;

int main()

{

    while(~scanf("%lf%lf%lf",&a,&b,&c))

    {

        k=(a+b)/(b+c);

        f=(a*c)/(b-c*k);

        e=k*f;

        printf("%.4lf\n",e+f);

    }

    return ;

}

/*

ZUFE OJ 1606: 清洁公司

题解：DFS求连通块

*/

#include<stdio.h>

char gird[][];

int m,n;

int dir[][]= {{-,-},{-,},{-,},{,}

    ,{,},{,},{,-},{,-}};

void dfs(int x,int y)

{

    int i,xx,yy;

    gird[x][y]='#';

    for(i=; i<; i++)

    {

        xx=x+dir[i][];

        yy=y+dir[i][];

        if(xx<||yy<||xx>=m||yy>=n) continue;

        if(gird[xx][yy]=='@') dfs(xx,yy);

    }

}

int main()

{

    int i,j;

    int count;

    while( scanf("%d%d",&m,&n)!=EOF)

    {

        for(i=; i<m; i++) scanf("%s",gird[i]);

        count=;

        for(i=; i<m; i++)

        {

            for(j=; j<n; j++)

            {

                if(gird[i][j]=='@')

                {

                    dfs(i,j);

                    count++;

                }

            }

        }

        printf("%d\n",count);

    }

    return ;

}

/*

ZUFE OJ 2323: 黑鸡跑1000

题解：水题..搞之..

*/

#include <stdio.h>

double a,b;

int main()

{

    while(~scanf("%lf%lf",&a,&b))

        printf("%.2lf\n",500.0/a+500.0/b);

    return ;

}

2015浙江财经大学ACM有奖周赛（一） 题解报告的相关教程结束。