HNUCM 2020年湖南省大学生计算机程序设计竞赛第2场选拔赛

怼烎@ 2022-12-06 15:08 212阅读 0赞

#  HNUCM 2020年湖南省大学生计算机程序设计竞赛第2场选拔赛 #

[**比赛地址**][Link 1]

## A：最强班级 ##

#### 题意 ####

给定n行，每行给定一个编号和成绩（看样例可以发现：编号可以相同），求总得分最高的班级编号及其总分。

#### 题解 ####

**hash**。直接用c++ 中map即可。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define lowbit x x&(-x)
    #define inf 1e18
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    map<int,int>mp;
    int main(){
        
        //freopen("data/6.in","r",stdin);
        //freopen("data/6.out","w",stdout);
        int n;
        scanf("%d",&n);
        int x,y;
        for(int i=1;i<=n;i++){
        
            scanf("%d%d",&x,&y);
            mp[x]+=y;
        }
        map<int,int>::iterator it;
        int cnt,score=0;
        for(it=mp.begin();it!=mp.end();it++){
        
            if(it->second>score){
        
                score=it->second;
                cnt=it->first;
            }
        }
        printf("%d %d\n",cnt,score);
        return 0;
    }

## B：岛屿个数 ##

#### 题意 ####

给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。  
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右），计算岛屿个数。

#### 题解 ####

**四连通块问题。**  
比赛中途晖晖学长也有提到，矩阵不等于方阵，行列可以不同，同时需要考虑极端情况（也就是单行或单列情况）

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define lowbit x x&(-x)
    #define inf 1e18
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    int mp[1110][110],vis[110][110];
    int n,m;
    int dir[4][2]={
        -1,0,1,0,0,-1,0,1};
    void dfs(int x,int y){
        
        for(int i=0;i<4;i++){
        
            int fx=x+dir[i][0];
            int fy=y+dir[i][1];
            if(mp[fx][fy]==1&&vis[fx][fy]==0){
        
                vis[fx][fy]=1;mp[fx][fy]=0;
                dfs(fx,fy);
            }
        }
    }
    int main(){
        
        //freopen("data/3.in","r",stdin);
        //freopen("data/3.out","w",stdout);
        int x;n=0;
        while(~scanf("%d",&x)){
        
            mp[++n][1]=x;m=1;
            if(getchar()=='\n') continue;
            while(~scanf("%d",&x)){
        
                mp[n][++m]=x;
                if(getchar()=='\n') break;
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=m;j++){
        
                if(mp[i][j]==1){
        
                    ans++;
                    dfs(i,j);
                }
            }
        }
        printf("%d\n",ans);
        return 0;
    }

## C：最长括号子串 ##

#### 题意 ####

给定只包含’(’、’)'的字符串，求合法的最长括号子串。

#### 题解 ####

提供两种思路：

1.  用一个栈sta存每个左括号的位置，一个数组vis\[\]表示符合条件的字符串索引值（即下标），首先初始化全为0。在遍历字符串的同时，将左括号入栈，如果遇到右括号：当栈为空时则证明没有符合条件的括号子串；若栈不为空，则将栈顶元素出栈，此时栈顶元素和当前遍历到的右括号可以视为是一合法括号，于是将两个位置对应于vis\[\]标记为1。  
    再对数组vis\[\]进行遍历，求最长连续1即可。
2.  区间dp（晖晖学长的思路）。  
    对于区间 \[ i , j \] \[i,j\] \[i,j\]：  
    当s\[i\]!=’(’||s\[j\]!=’)‘时，直接不用考虑  
    当s\[i\]== ‘(’&&s\[j\]==’)’，首先dp\[i\]\[j\]=dp\[i+1\]\[j-1\]  
    然后再对区间\[i,j\]中以k为中断点，分别对两段求最长子串和然后相加取最大值，具体见代码。

#### AC代码1（cpp） ####

#include<bits/stdc++.h>
    #define lowbit x x&(-x)
    #define inf 1e18
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    stack<int>sta;
    char s[110];
    int vis[110];
    int main(){
        
        scanf("%s",s+1);
        int len=strlen(s+1);
        memset(vis,0,sizeof(vis));
        int ans=0,num=0;
        for(int i=1;i<=len;i++){
        
            if(s[i]=='('){
        
                sta.push(i);
            }else{
        
                if(sta.empty()) continue;
                vis[sta.top()]=1;vis[i]=1;
                sta.pop();
            }
        }
        for(int i=1;i<=len;i++){
        
            if(vis[i]){
        
                num=0;
                for(int j=i;j<=len;j++){
        
                    if(vis[j]) num++;
                    else break;
                }
                ans=max(ans,num);
            }
        }
        printf("%d\n",ans);
        return 0;
    }

#### AC代码2（cpp） ####

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const int inf=0x3f3f3f3f;
    char s[105];
    int dp[105][105];
    int main() {
        
        scanf("%s",s+1);
        int ls=strlen(s+1),ans=0;
        memset(dp,-inf,sizeof(dp));
        for(int i=1;i<=ls;++i){
        
            dp[i][i-1]=0;
        }
        for(int len=2;len<=ls;++len){
        
            for(int i=1;i+len-1<=ls;++i){
        
                int j=i+len-1;
                if(s[i]!='('||s[j]!=')')continue;
                dp[i][j]=dp[i+1][j-1]+2;
                for(int k=i;k<j;++k){
        
                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
                ans=max(ans,dp[i][j]);
            }
        }
        printf("%d\n",ans);
        return 0;
    }

## D：过半 ##

#### 题意 ####

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。（必须超过一半，等于一半也不符合要求。）  
例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。  
如果不存在则输出0。

#### 题解 ####

**水题**。可以用map存数字与其对应的次数。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define lowbit x x&(-x)
    #define inf 1e18
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    int a[110];
    map<int,int>mp;
    int main(){
        
        int n=0;
        while(~scanf("%d",&a[n++]));
        n--;
        mp.clear();
        for(int i=0;i<n;i++){
        
            mp[a[i]]++;
        }
        map<int,int>::iterator it;
        int ans=0;
        int cnt=n/2+1;
        for(it=mp.begin();it!=mp.end();it++){
        
            if(it->second>=cnt){
        
                ans=it->first;
                break;
            }
        }
        printf("%d\n",ans);
        return 0;
    }

## E：小h的推理题 ##

#### 题意 ####

小h想加入一个高智商俱乐部，有一个测试，里面有一道题是这样的：有很多砝码，并没有标志重量，大小也一致，已经用天平称量了部分砝码间的重量大小关系，需要判断出最重和最轻的砝码是哪两个

#### 题解 ####

**思维题。**  
推荐先看这道题：[hdu 2094：产生冠军][hdu 2094]  
定义三个set，st：存储所有砝码；st1：存储在比较中重的砝码；st2：存储比较中轻的砝码。  
对st与st2求差集：如果只有一个元素则表示是最重的砝码，否则表示没有最重的砝码。  
对st与st1求差集：如果只有一个元素则表示是最轻的砝码，否则表示没有最轻的砝码。

#### AC代码1（cpp） ####

#include<bits/stdc++.h>
    #define lowbit x x&(-x)
    #define inf 1e18
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    set<int>st,st1,st2;
    int main(){
        
        int n,m,a,b;
        scanf("%d%d",&n,&m);
        while(m--){
        
            scanf("%d%d",&a,&b);
            st.insert(a);st.insert(b);
            st1.insert(a);st2.insert(b);
        }
        if(st.size()!=n){
        
            printf("-1 -1\n");return 0;
        }
        set<int>high,low;
        set_difference(st.begin(),st.end(),st2.begin(),st2.end(),insert_iterator<set<int> >(high,high.begin()));
        set_difference(st.begin(),st.end(),st1.begin(),st1.end(),insert_iterator<set<int> >(low,low.begin()));
        if(high.size()==1){
        
            cout<<*high.begin()<<' ';
        }else cout<<-1<<' ';
        if(low.size()==1){
        
            cout<<*low.begin()<<'\n';
        }else cout<<-1<<'\n';
        return 0;
    }

#### AC代码2（cpp） ####

晖晖学长的思路

#include<bits/stdc++.h>
    #include<string.h>
    #include<math.h>
    #include<stdio.h>
    #include<algorithm>
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const int inf=0x3f3f3f3f;
    int ma[maxn],mi[maxn];
    int main()
    {
        
        int n,m,a,b;
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;++i){
        
            ma[i]=mi[i]=1;
        }
        for(int i=1;i<=m;++i){
        
            scanf("%d %d",&a,&b);
            ma[b]=0;
            mi[a]=0;
        }
        int num=0,ans=-1;
        for(int i=1;i<=n;++i){
        
            if(ma[i]){
        
                ++num;
                ans=i;
            }
        }
        if(num==1){
        
            printf("%d ",ans);
        }else{
        
            printf("-1 ");
        }
        num=0,ans=-1;
        for(int i=1;i<=n;++i){
        
            if(mi[i]){
        
                ++num;
                ans=i;
            }
        }
        if(num==1){
        
            printf("%d\n",ans);
        }else{
        
            printf("-1\n");
        }
        return 0;
    }

## F：手性二叉树 ##

#### 题意 ####

若一颗二叉树关于中间轴对称，我们则称这颗二叉树为手性二叉树。给定一先序遍历的二叉树，问是否是手性二叉树。

#### 题解 ####

**树的简单操作。**  
首先建树是重点，建树成功之后，直接遍历树，然后判断当前结点是否有子结点，以及子树是否满足关于中心轴对称。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define lowbit x x&(-x)
    #define inf 1e18
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    struct node{
        
        int l,r,v;
    };
    node tree[maxn];
    int cnt,flag;
    void build(int root){
        
        int x;
        scanf("%d",&x);
        tree[root].v=x;
        if(x!=-1){
        
            tree[root].l=++cnt;
            tree[root].r=++cnt;
            build(tree[root].l);
            build(tree[root].r);
        }
    }
    void dfs(int x,int y){
        
        if((tree[x].v==-1&&tree[y].v!=-1)||(tree[x].v!=-1&&tree[y].v==-1)){
        
            flag=0;return ;
        }
        if(tree[x].v==-1||tree[y].v==-1) return ;
        if(tree[x].v!=tree[y].v){
        
            flag=0;return ;
        }
        dfs(tree[x].l,tree[y].r);
        dfs(tree[x].r,tree[y].l);
    }
    int main(){
        
        cnt=1;
        build(1);
        flag=1;
        dfs(tree[1].l,tree[1].r);
        if(flag) printf("yes\n");
        else printf("no\n");
        return 0;
    }

## G：小红红要虫虫 ##

#### 题意 ####

小红红同学最近收到小斐同学的一份礼物，一盒来自R星的昆虫。小红红同学特别开心，但是小斐同学说这盒昆虫可不是让你白拿的，必须回答完我的问题才可以。  
小斐同学给出一个图，请问小红红同学能否判断把图的每个点用K种昆虫放置，且保证相邻两点不同种类的昆虫。

#### 题解 ####

**图的简单操作。**  
图比较小，使用邻接矩阵或邻接表存皆可。题目要求是相邻结点的昆虫种类不能相同，于是对每个结点的相邻点遍历判断即可。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define lowbit x x&(-x)
    #define inf 1e18
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    int a,b,k,n,u,v;
    vector<int>e[510];
    int tag[510];
    set<int>st;
    int solve(){
        
        for(int i=1;i<=a;i++){
        
            for(int j=0;j<e[i].size();j++){
        
                int v=e[i][j];
                if(tag[v]==tag[i]){
        
                    return 0;
                }
            }
        }
        return 1;
    }
    int main(){
        
        scanf("%d%d%d",&a,&b,&k);
        for(int i=1;i<=b;i++){
        
            scanf("%d%d",&u,&v);
            e[u].push_back(v);e[v].push_back(u);
        }
        scanf("%d",&n);
        while(n--){
        
            st.clear();
            for(int i=1;i<=a;i++){
        
                scanf("%d",&tag[i]);st.insert(tag[i]);
            }
            if(st.size()>k){
        
                printf("No\n");continue;
            }
            int flag=solve();
            if(flag) printf("Yes\n");
            else printf("No\n");
        }
        return 0;
    }

## G：化腾的前生 ##

#### 题意 ####

在小红红的班级内有阿珍和阿强两位同学，阿珍是阿强的同桌（阿珍是一位美女奥）。阿强借此机会询问阿珍的OICQ号码，阿珍没有直接告诉他，只是告诉了阿强一串密文。好巧不巧，阿强知道这串密文的解密规则。  
规则是这样的：首先将第一个数删除，紧接着把第二个数放到这个密文的末尾，再将第三个数删掉，把第四个数放到这个串的末尾。。。。。。。直到最后一个数也被删除，把之前删除的数连在一起就是阿珍的OICQ号码啦。

#### 题解 ####

**简单模拟题。**  
直接按照题意模拟即可。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define lowbit x x&(-x)
    #define inf 1e18
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    int a[maxn];
    vector<int>ans;
    int main(){
        
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
        
            scanf("%d",&a[i]);
        }
        int cnt=1;
        while(cnt<=n){
        
            ans.push_back(a[cnt]);
            ++cnt;a[++n]=a[cnt];
            ++cnt;
        }
        for(int i=0;i<ans.size();i++){
        
            printf("%d",ans[i]);
            if(i==ans.size()-1) printf("\n");
            else printf(" ");
        }
        printf("\n");
        return 0;
    }

## I：简单迷宫题 ##

#### 题意 ####

众多单机小游戏中都有王子救公主的情节，小波也脑补了一个迷宫游戏。现有一大小为n*m二维迷宫，告诉你王子和公主的位置，小波觉得没有点实力是不配当王子的，于是王子每次可以向他的八个方向走一步（即：上、下、左、右、左上、左下、右上、右下）。迷宫中存在一些墙壁（用’\#‘表示），同时还存在一些陷阱（用’*‘表示，在这个游戏中，保证王子能够快速的发现陷阱并绕开，即：王子可以走这个陷阱并巧妙的绕开），正常可以行走的路用’.'表示，王子的位置用’S’表示，公主的位置用’E’表示。现问你王子有多少条路可以营救公主（当然王子足够聪明，不会回头路）。

#### 题解 ####

请重新仔细看题，一定能有不一样的收获！请重新仔细看题，一定能有不一样的收获！请重新仔细看题，一定能有不一样的收获！

好了，这里默认已经重新看完题了。于是发现这题就是一个水题。陷阱不能走，墙壁不能走，直接对起点dfs即可。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define lowbit x x&(-x)
    #define inf 1e18
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    int n,m,sx,sy,ex,ey;
    char mp[110][110];
    int vis[110][110];
    int dirx[]={
        -1,-1,-1,0,0,1,1,1};
    int diry[]={
        -1,0,1,-1,1,-1,0,1};
    int ans;
    int check(int x,int y){
        
        if(x>=1&&x<=n&&y>=1&&y<=m&&vis[x][y]==0&&(mp[x][y]=='.'||mp[x][y]=='E')){
        
            return 1;
        }
        return 0;
    }
    void dfs(int x,int y){
        
        if(x==ex&&y==ey){
        
            ans++;
            return ;
        }
        for(int i=0;i<8;i++){
        
            int fx=x+dirx[i];
            int fy=y+diry[i];
            if(check(fx,fy)){
        
                vis[fx][fy]=1;
                dfs(fx,fy);
                vis[fx][fy]=0;
            }
        }
    }
    int main(){
        
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
        
            scanf("%s",mp[i]+1);
            for(int j=1;j<=m;j++){
        
                if(mp[i][j]=='S') sx=i,sy=j;
                else if(mp[i][j]=='E') ex=i,ey=j;
            }
        }
        //cout<<sx<<' '<<sy<<endl;
        //cout<<ex<<' '<<ey<<endl;
        ans=0;memset(vis,0,sizeof(vis));vis[sx][sy]=1;
        dfs(sx,sy);
        printf("%d\n",ans);
        return 0;
    }

[Link 1]: http://acm.hnucm.edu.cn/JudgeOnline/contest.php?cid=1133
[hdu 2094]: http://acm.hdu.edu.cn/showproblem.php?pid=2094