NYIST_12周赛（一）题目题解

ゞ浴缸里的玫瑰 2022-09-17 12:23 184阅读 0赞

题目链接：[http://acm.nyist.net/JudgeOnline/problemset.php?cid=167][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。。。

今天一天都很忙，刚才抽空做了一下题目：D删除元素

我开始想的是排序，然后算出最小值的二倍跟最大值的1/2，然后用一个for循环遍历从开始找前面从一个值到1/2最大值的和从后面到前面可以删除的二倍的最小值的，然后取出他俩的最小值输出来，提交wa了。。。。然后胡乱的输入的1 2 3 4 5发现它不只是仅仅从前面取或者从后面取，还可以两边取。

所以思想就是从其中找出满足条件的最长李安，这是代码：

#include <cstdio>
    #include <algorithm>
    int main()
    {
        int a[100100];
        int n;
        while(~scanf("%d",&n))
        {
            for(int i=0;i<n;i++)
                scanf("%d",&a[i]);
            std::sort(a,a+n);
            int ans=0;
            for(int i=0,k=0;i<n;i++)
            {
                while(k<n&&a[k]<=2*a[i])
                {
                    k++;
                }
                if(k-i>ans)
                    ans=k-i;  //找出连续的长链
            }
            printf("%d\n",n-ans);
        }
        return 0;
    }

下面要做的是：华山论剑、

做了这道题之后发下原来杀死的人可以再下一轮活过来进行杀人，题目好大的坑啊。代码：

#include <cstdio>
    #define N 300000+10
    int father[N],runk[N];
    void makeset(int n)  //初始化
    {
        for(int i=1;i<=n+1;i++){
            father[i]=i;runk[i]=0;
        }
    }
    int find(int x)  //查找+状态压缩
    {
        return father[x] != x ? father[x]=find(father[x]) : x;//状态压缩、
    }
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            makeset(n);
            while(m--)
            {
                int a,b,c;
                scanf("%d%d%d",&a,&b,&c);
                for(int i=find(a);i<=b;i=find(i+1))
                {
                    if(i==c)
                        continue;
                    runk[i]=c;
                    if(i<c)
                        father[i]=c;
                    else
                        father[i]=father[b+1];
                }
            }
            for(int i=1;i<=n;i++)
                printf("%d%c",runk[i],i==n?'\n':' ');
        }
        return 0;
    }

下三角矩阵，很easy，比赛的时候没来得及看。

由分析可知，构成下三角矩阵实际上只与每行的最后一个非零位置有关

找出每行矩阵的最后一个非零位置。

然后根据最后一个非零位置将其移动到对应的位置即可，每一次移动符合条件的最近的一行，之后此行将不再考虑，记录移动的次数即为最少的次数。

把最后一个非零位置存在一个数组里，对数组处理就ok。

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    int Map[1005][1005];
    int a[1005],n;
    int main()
    {
        while(~scanf("%d",&n))
        {
            memset(a,-1,sizeof(a));
            for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=n; j++)
                {
                    scanf("%d",&Map[i][j]);
                    if(Map[i][j])
                    {
                        a[i]=j;
                    }
                }
            }
            int fg,ans = 0;
            for(int i=1;i<=n;i++)
            {
                if(a[i]>i)
                {
                    fg=-1;
                    for(int j=i;j<=n;j++)
                    {
                        if(a[j]<=i){fg=j;break;}
    
                    }
                    for(int k=fg;k>i;k--)
                    {
                        std::swap(a[k],a[k-1]);
                        ans++;
                    }
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[http_acm.nyist.net_JudgeOnline_problemset.php_cid_167]: http://acm.nyist.net/JudgeOnline/problemset.php?cid=167