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 ;

}

最新文章

  1. Neutron Vlan Network 原理- 每天5分钟玩转 OpenStack（92）
  2. 声明提前js变量
  3. spring 事务管理方式及配置
  4. Android 中 SQLite 数据库的查看
  5. java 导出Excel文件
  6. atitit.提升开发效率---使用服务器控件生命周期 asp.net 11个阶段 java jsf 的6个阶段比较
  7. 手机响应式wap网页最佳方案
  8. 【翻译】《深入解析windows操作系统第6版下册》第10章:内存管理
  9. Qt之Tab键切换焦点顺序
  10. Mysql之EXPLAIN显示using filesort
  11. apache开源项目--ApacheDS
  12. 拦截器getmodel方法什么时候被调用（没搞懂有什么鸟用，自己搭的项目中用到了这个）
  13. POJ 3280 Cheapest Palindrome 简单DP
  14. Eclipse汉化后怎么改回英文版 （中文 改 英文）
  15. opencv 图像修复函数
  16. C random C ++rand函数应用
  17. Akka（19）： Stream：组合数据流，组合共用-Graph modular composition
  18. Tengine 安装配置全过程（nginx 同理）
  19. python通过token登录，并爬取数据实例
  20. HSRP(Hot Standby Router Protocol)

热门文章

  1. ubuntu如何实现访问实际网络中windows共享文件夹
  2. cmd 下登陆ftp及相关操作
  3. ASP.NET ValidationGroup 属性和CssClass 属性
  4. thinkphp的目录结构设计经验总结1
  5. mybatis 总结(1)
  6. Mysql 锁机制
  7. Python 线程，进程
  8. onPostCreate——Activity彻底运行起来之后的回调
  9. 1.4 测试各阶段（单元、集成、系统 、Alpha、Beta、验收）
  10. 【java图形计算器】 java awt swing组件应用