【题解】吉首大学第九届＂新星杯＂大学生程序设计大赛（重现赛）

ゝ一纸荒年。 2023-06-27 08:45 12阅读 0赞

### 文章目录 ###

*  B - Y 老师的井字窗（签到）
 *  C - 始战（思维）
 *  D - 秒速五厘米（二分）
 *  E - 冬天怎么能够没有辣条（签到）
 *  H - 小李堆积木（模拟）
 *  I - Y 老师的乐高小镇（数学）
 *  J - 小阳排队（思维 + DP）
 *  K - 小阳数数（并查集 + set）

# B - Y 老师的井字窗（签到） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3667/B][https_ac.nowcoder.com_acm_contest_3667_B]

*  **思路：** 把每一行的数值相加起来存入 row\[ \] 数组，再把每一列的数值相加起来存入 col\[ \] 数组，最后输出这两个数组的最大值即可。

**Code（C++）：**

#include <iostream>
    using namespace std;
    const int N=1e6+10;
    int row[N],col[N];
    int main(){ 
        int n,m;    cin>>n>>m;
        int x,maxn=0;
        for(int i=1;i<=n;i++){ 
            for(int j=1;j<=m;j++){ 
                cin>>x;
                row[i]+=x;
                col[j]+=x;
            }
        }
        for(int i=1;i<=n;i++){ 
            if(row[i]>maxn)
                maxn=row[i];
        }
        for(int j=1;j<=m;j++){ 
            if(col[j]>maxn)
                maxn=col[j];
        }
        cout<<maxn<<endl;
        return 0;
    }

# C - 始战（思维） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3667/C][https_ac.nowcoder.com_acm_contest_3667_C]

*  **思路：**

1.  如果 “ \* ” 的地方同时被两个将军占领则输出该点的坐标，那么我们可以遍历整个二维字符数组，如果是 “ \* ” ，则计算其上下左右有多少个 “ \# ”，如果数量大于等于两个则输出该点的坐标。如果一个点的坐标都没有则输出 -1 。
2.  也可以直接用BFS跑一遍，符合情况的就存入结构体，然后给结构体排个序输出即可。

**Code1（C++）：**

#include <iostream>
    #include <cstring>
    using namespace std;
    char ch[105][105];
    int main(){ 
        int n,m;
        while(cin>>n>>m){ 
            memset(ch,'\0',sizeof(ch));
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    cin>>ch[i][j];
            bool vis=false;
            for(int i=1;i<=n;i++){ 
                for(int j=1;j<=m;j++){ 
                    if(ch[i][j]=='*'){ 
                        int sum=0;
                        if(ch[i-1][j]=='#')    sum++;
                        if(ch[i+1][j]=='#')    sum++;
                        if(ch[i][j-1]=='#')    sum++;
                        if(ch[i][j+1]=='#')    sum++;
                        if(sum>=2){ 
                            vis=true;
                            cout<<i<<' '<<j<<endl;
                        }
                    }
                }
            }
            if(!vis)    cout<<-1<<endl;
        }
        return 0;
    }

**Code2（C++）：**

//bfs做法
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    int n,m,cnt;
    char ch[105][105],vis[105][105];
    int dir[4][2]={ { -1,0},{ 1,0},{ 0,-1},{ 0,1}};
    struct node{ 
        int x,y;
    }a[105];
    bool cmp(node a, node b){ 
        if(a.x==b.x)    return a.y<b.y;
        return a.x<b.x;
    }
    void dfs(int x, int y){ 
        for(int i=0;i<4;i++){ 
            int xx=x+dir[i][0];
            int yy=y+dir[i][1];
            if(!vis[xx][yy] && ch[xx][yy]=='*' && xx>=1 && xx<=n && yy>=1 && yy<=m){ 
                vis[xx][yy]=1;
                continue;
            }
            if(vis[xx][yy]==1 && ch[xx][yy]=='*'){ 
                vis[xx][yy]=2;
                a[cnt].x=xx;
                a[cnt++].y=yy;
            }
        }
    }
    int main(){ 
        while(cin>>n>>m){ 
            memset(vis,0,sizeof(vis));
            for(int i=1;i<=n;i++)
                scanf("%s",ch[i]+1);
            cnt=0;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++){ 
                    if(ch[i][j]=='#')    dfs(i,j);
                }
            sort(a,a+cnt,cmp);
            if(!cnt)    cout<<-1<<endl;
            else{ 
                for(int i=0;i<cnt;i++)
                    cout<<a[i].x<<' '<<a[i].y<<endl;
            }
        }
        return 0;
    }

# D - 秒速五厘米（二分） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3667/D][https_ac.nowcoder.com_acm_contest_3667_D]

*  **思路：** 对于求最小 / 大的符合条件的值的题目，一般都是采取二分答案的做法，然后判断是否符合条件就可以了。注意要多组输入。

**Code（C++）：**

#include <iostream>
    using namespace std;
    const int N=2e6+10;
    int a[N],n,m;
    bool check(int x){ 
        int sum=0;
        for(int i=1;i<=n;i++){ 
            if(a[i]%x==0)    sum+=a[i]/x;
            else    sum+=(a[i]/x+1);
            if(sum>m)    return false;
        }
        return sum<=m;
    }
    int main(){ 
        while(cin>>n>>m){ 
            int maxn=0;
            for(int i=1;i<=n;i++){ 
                cin>>a[i];
                maxn=max(maxn,a[i]);
            }
            int l=1,r=maxn,ans=maxn;
            while(l<=r){ 
                int mid=(l+r)>>1;
                if(check(mid)){ 
                    ans=mid;
                    r=mid-1;
                }
                else    l=mid+1;
            }
            cout<<ans<<endl;
        }
        return 0;
    }

# E - 冬天怎么能够没有辣条（签到） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3667/E][https_ac.nowcoder.com_acm_contest_3667_E]

*  **思路：** 先给数组从小到大排序，然后输出倒数第二个及第二个即可。

**Code（C++）：**

#include <iostream>
    #include <algorithm>
    using namespace std;
    int a[105];
    int main(){ 
        int n;
        while(cin>>n){ 
            for(int i=1;i<=n;i++)
                cin>>a[i];
            sort(a+1,a+1+n);
            cout<<a[n-1]<<' '<<a[2]<<endl;
        }
        return 0;
    }

# H - 小李堆积木（模拟） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3667/H][https_ac.nowcoder.com_acm_contest_3667_H]

*  **思路：** 模拟题，初始化第一阶段，然后把上半部分先写，再写左下部分以及右下部份。

**Code（C++）：**

#include <iostream>
    using namespace std;
    int f[12],ch[12][600][600];
    int main(){ 
        f[1]=1;
        for(int i=2;i<=10;i++)    //第几阶段
            f[i]=f[i-1]*2;    //对应的行列数
        ch[1][1][1]=1;    //第一阶段
        for(int i=2;i<=10;i++){ 
            for(int j=1;j<=f[i-1];j++){     //上半部分
                for(int k=1,l=1;k<=f[i];k++,l++){ 
                    if(l>f[i-1])    l=1;
                    ch[i][j][k]=ch[i-1][j][l];
                }
            }
            for(int j=f[i-1]+1,row=1;j<=f[i],row<=f[i-1];j++,row++){     //下半部分
                for(int k=1;k<=f[i-1];k++)    //左下部分
                    ch[i][j][k]=!ch[i-1][row][k];
                for(int k=f[i-1]+1,l=1;k<=f[i];k++,l++)    //右下部分
                    ch[i][j][k]=ch[i-1][row][l];
            }
        }
        int t;    cin>>t;
        while(t--){ 
            int n;    cin>>n;
            for(int i=1;i<=f[n];i++){ 
                for(int j=1;j<=f[n];j++){ 
                    cout<<ch[n][i][j]<<' ';
                }
                cout<<endl;
            }
        }
        return 0;
    }

# I - Y 老师的乐高小镇（数学） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3667/I][https_ac.nowcoder.com_acm_contest_3667_I]

*  **思路：** 将输入的 k 转换为二进制数，然后计算含 1 的数量。

**Code（C++）：**

#include <iostream>
    #define ll long long
    using namespace std;
    int main(){ 
        ll k;
        while(cin>>k){ 
            int ans=0;
            while(k){ 
                ans+=(k%2);
                k/=2;
            }
            cout<<ans<<endl;
        }
        return 0;
    }

# J - 小阳排队（思维 + DP） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3667/J][https_ac.nowcoder.com_acm_contest_3667_J]

*  **思路：** 这道题排队只能插入队头或者队尾，要求最小操作数。那么我们假设全部进行插入队头操作或者插入队尾操作，则该问题就成了求最小连续子序列长度。

**Code（C++）：**

#include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int N=5e5+10;
    int a[N],dp[N];
    inline int read(){ 
        char c=getchar();    int num=0;
        for(;!isdigit(c);c=getchar());
        for(;isdigit(c);c=getchar())
            num=num*10+c-'0';
        return num;
    }
    int main(){ 
        int t;    t=read();
        while(t--){ 
            memset(dp,0,sizeof(dp));
            int n;    n=read();
            for(int i=1;i<=n;i++)
                a[i]=read();
            int ans=0;
            for(int i=1;i<=n;i++){ 
                dp[a[i]]=dp[a[i]-1]+1;
                ans=max(ans,dp[a[i]]);
            }
            cout<<n-ans<<endl;
        }
        return 0;
    }

# K - 小阳数数（并查集 + set） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3667/K][https_ac.nowcoder.com_acm_contest_3667_K]

*  **思路：** 把每一个字符串的字符转换为数字，然后同一个字符串的数字祖先弄成相同的，并标记为已出现过，这样子只要出现有相同数字的字符串就有相同的祖先了。然后再把每一个出现过的数字的祖先放入 set，因为 set 不能存放相同的数值，就不会出现重复的情况，再输出它的长度即可。

**Code（C++）：**

#include <iostream>
    #include <cstring>
    #include <set>
    using namespace std;
    char str[1010];
    int vis[10],fa[10];
    int find(int x){ 
        while(x!=fa[x])
            x=fa[x];
        return x;
    }
    int main(){ 
        int t;    cin>>t;
        while(t--){ 
            int n;    cin>>n;
            memset(vis,0,sizeof(vis));
            for(int i=0;i<10;i++)
                fa[i]=i;
            for(int i=1;i<=n;i++){ 
                scanf("%s",str);
                int t = str[0]-'0';
                vis[str[0]-'0']=1;
                int len=strlen(str);
                for(int i=1;i<len;i++){ 
                    vis[str[i]-'0']=1;
                    int x=find(t);
                    int y=find(str[i]-'0');
                    if(x!=y)    fa[x]=y;
                }
            }
            set<int> s;
            for(int i=0;i<10;i++){ 
                if(vis[i])    s.insert(find(i));
            }
            cout<<s.size()<<endl;
        }
        return 0;
    }

[https_ac.nowcoder.com_acm_contest_3667_B]: https://ac.nowcoder.com/acm/contest/3667/B
[https_ac.nowcoder.com_acm_contest_3667_C]: https://ac.nowcoder.com/acm/contest/3667/C
[https_ac.nowcoder.com_acm_contest_3667_D]: https://ac.nowcoder.com/acm/contest/3667/D
[https_ac.nowcoder.com_acm_contest_3667_E]: https://ac.nowcoder.com/acm/contest/3667/E
[https_ac.nowcoder.com_acm_contest_3667_H]: https://ac.nowcoder.com/acm/contest/3667/H
[https_ac.nowcoder.com_acm_contest_3667_I]: https://ac.nowcoder.com/acm/contest/3667/I
[https_ac.nowcoder.com_acm_contest_3667_J]: https://ac.nowcoder.com/acm/contest/3667/J
[https_ac.nowcoder.com_acm_contest_3667_K]: https://ac.nowcoder.com/acm/contest/3667/K