NYIST_12周赛（1）题目题解

NYIST_12周赛（一）题目题解

题目链接：http://acm.nyist.net/JudgeOnline/problemset.php?cid=167

比赛的时候做出来三道，按顺序贴出代码：
先做出来E题：又见Alice and Bob

这道题目是一道博弈题目：思路就是先求出所有数的最大公约数gcd，然后用这组数中的最大值MAX，和值得数量n，结果就是（MAX/gcd-n），然后判断它的奇偶性就行，比较恶心的地方是测试样例的答案是错的，导致只有我一个人A出了这道题目：代码

 

#include <cstdio>
#include <string>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int gcd(int a,int b)
{
    while(b)
    {
        int c=a%b;
        a=b;
        b=c;
    }
    return a;
}
int main()
{
    int n,a[120];
    while(~scanf("%d",&n))
    {
        int Max=1<<31,ans=0,ok=0;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            if(a[i]>Max)
                Max=a[i];
        }
        //sort(a,a+n);
        int count=a[0];
        for(int i=1;i<n;i++)
        {
            count=gcd(count,a[i]);
        }
        if(count!=1)
        {
            ans=Max/count-n;
        }
        else
            ans=Max-n;
        printf(ans%2==0?"Bob\n":"Alice\n");
    }
    return 0;
}

后面坐了F题：plits the string

是第一次比赛的一道题目，正好联系过，敲上去就对了、

动态规划入门题

题目大意：求一个字符串的最少可以分为多少个回文子串

解题思路：

状态：用dp[ i ] 记录从开始到第i个字符结尾的这一段的最少回文子串数

dp[ i ] 的值初始化为i ；

状态转移方程：

dp[ i ] = dp[ j - 1 ] + 1 (字符串i到j为回文串)；

代码：

 
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#define min(a,b) a>b?b:a
using namespace std;
char str[1005];
int dp[1005];
char vis[1005][1005];

int solve(int a,int b)
{
    if(vis[a][b]!=-1)
        return vis[a][b];
    for(int i=a,j=b; i<=j; i++,j--)
    {
        if(str[i]!=str[j])
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    int i,j,k,l;
    string s;
    while(~scanf("%s",str+1))
    {
        /*for(int i=0;i<s.size();i++)
            str[i+1]=s[i];*/
        l=strlen(str+1);
        memset(vis,-1,sizeof(vis));
        for(i=1; i<=l; i++)
        {
            dp[i]=1<<30;
            vis[i][i]=1;

        }
        dp[0]=0,dp[1]=1;
        for(i=1; i<=l; i++)
        {
            for(j=1; j<=i; j++)
            {
                if(solve(j,i))
                    dp[i]=min(dp[i],dp[j-1]+1);
                else
                    dp[i]=min(dp[i],dp[j-1]+i-j+1);
            }
        }
        printf("%d\n",dp[l]);
    }
    return 0;
}

后面看了c题目：how many hairstyles can they see?

这道题目很多人都做出来了，我也就看了，题意就是给出一组数表示牛的身高，问所有牛一共能看到多少个牛？

比如：
There are six cows, heights are 10 2 7 3 12 2.

Now Cow#1 can see the hairstyle of cows #2, 3, 4

Cow#2 can see no cow's hairstyle

Cow#3 can see the hairstyle of cow #4

Cow#4 can see no cow's hairstyle

Cow#5 can see the hairstyle of cow 6

Cow#6 can see no cows at all!

开始用暴力，提交超时，时间980ms。题目要求1000ms然后接下来各种优化提交各种超时，然后我就考虑换算法。

开始想到优先队列，但是不知道怎么操作，后面想到用栈。每次求栈里面元素的和就可以，代码：

 
#include <cstdio>
#include <iostream>
#include <stack>
using namespace std;

int main()
{
    stack<long> s;
    int n;
    while(~scanf("%d",&n))
    {
        int p,x,ans=0;
        scanf("%d",&p);
        s.push(p);
        for(int i=1;i<n;++i)
        {
            scanf("%d",&x);
            while(!s.empty()&&x>=s.top())
                s.pop();
            s.push(x);
            ans+=s.size();
        }
        printf("%d\n",ans-n+1);
        while(!s.empty())
            s.pop();
    }
    return 0;
}

后面题目ing。。。

how many hairstyles can they see?

NYIST_12周赛（1）题目题解

相关推荐