阿里灵犀互娱秋招 2023.08.20 机试题目与题解

发表于 2023-08-21 分类于笔试阅读次数：本文字数： 2k 阅读时长 ≈ 2 分钟

1、prime

给到一个字符串(由a-z组成)，统计每个字符出现的次数，判断出现次数最多的字符的出现此时是否为质数。

输入

第一行为一个整数\(n\)，表示有多少个字符串。

然后是\(n\)行，表示需要求解的字符串，字符串长度大于\(1\)小于\(10000\)。

输出

出现次数最多的字符的出现次数为质数输出YES，否则输出NO

样例

输入：
2
abccckjskw
qwqwtttqqttttt

输出：
YES
NO

提示：

解答

直接暴力枚举字符串出现的次数，统计出最大次数\(c\)后，暴力判断\(c\)是否为质数即可。

代码

#include <bits/stdc++.h>
using namespace std;

bool is_prime(int n){
    if(n==1) return 0;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}
int c[26];
int main() {
    int T;
    string s;
    cin >> T;
    while(T--){
        cin >> s;
        memset(c,0,sizeof(c));
        for(char ch:s) ++c[ch-'a'];
        int mx=*max_element(c,c+26);
        printf("%s\n",is_prime(mx)?"YES":"NO");
    }
}

2、rank

小明想在游戏比赛中获得较高的名次，但是又担心自己实力不足而导致不能获奖，

因此他制定一个策略，查看往届游戏排名第三的人的分数，通过这个分数来制定自己的目标，如果游戏中不同分数只有两个或者更少(往届比赛一定会有人参加)，则直接将最大的分数作为自己的目标。但是游戏公布的分数是乱序的，你能帮帮小明吗?

输入

第一行输入为数组长度，第工行为数组元素

\(1 \le nums.length \le 10000\)
\(-2^{31} \le nums[i] \le 2^{31} - 1\)

输出

最大分数

样例

输入：
3
3 2 1

输出：
1

提示：
第三大的数是1

输入：
2
1 2

输出：
2

提示：
第三大的数不存在，所以返回最大的数2

输入：
4
2 2 3 1

输出：
1

提示：
注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。

解答

按照题意模拟即可，读入所有整数后去重，再排序，按要求输出倒数第一大或者是第三大的数。

代码

1
2
3

input()
a = sorted(set(map(int,input().split())))
print(a[-3] if len(a) >= 3 else a[-1])

3、replace

张三在一块白板上写了\(n\)个数字，记作\(a_i\)，李四对白板上的数字进行了\(m\)次修改，每次修改李四会将白板上的一个数字修改成\(b_j\)。张三想知道经过这\(m\)次修改，白板上所有数字之和可能的最大值是多少。

输入

第一行输入两个整数\(n,m(1\le n,m\le 1000)\)

第二行输入\(n\)个整数\(a_1,a_2,\dots,a_n(1\le a_i\le 10^9)\)

第三行输入\(m\)个整数\(b_1,b_2,\dots,b_m(1\le b_j\le 10^9)\)

输出

输出白板上所有数字之和的最大值

样例

输入：
2 3
1 2
3 4 5

输出：
9

解答

需要注意的是，这道题想表达的是第\(j\)次操作取\(b_j\)替换\(a\)中的某个数，总共进行\(m\)次。

为了保证\(a\)中的数和最大，每次只需要将\(a\)中最小的数进行替换即可。

代码

from queue import PriorityQueue

n, m = map(int, input().split())
a = map(int, input().split())
b = map(int, input().split())
q = PriorityQueue()
for x in a:
    q.put(x)
for x in b:
    w = q.get()
    q.put(x)
s = 0
while q.qsize() > 0:
    s += q.get()
print(s)

4、world

小杰在凌晨打游戏的时候被一股神秘力量牵引，进入了一个魔幻世界。

魔幻世界中危险遍布，刚落地的小杰听到恶龙咆哮已经瑟瑟发抖了。

为了能在异世界中活下来，小杰希望你能帮他计算异世界中安全区的个数。

已知小杰能力值为\(X\)，异世界是一个\(n\)行\(m\)列二维数组\(a,a[i][j]\)表示该地方的危险程度。

当小杰的能力值大于等于该地方的危险程度则表示该地方安全。安全区由一个或多个安全的地方组成，且这些地方互相连通。

输入

第一行包含一个正整数\(T(T\le 1000)\)，\(T\)代表数据组数

接下来\(T\)组数据，每组测试数据第一行三个正整数\(n,m,x\)

第二行开始为异世界不同地方的危险程度\(a[i][j]\)

\(1\le n\le 1000，1\le m\le 1000，1\le X\le 1000，1\le a[i][j] \le 1000\)

题目保证: \(T*N*M\le 10^7\)

输出

对于每组输入输出一个安全区的个数，如果没有满足要求的安全区则输出"Orz"! (不包括引号)

样例

输入：
3
1 1 1
5
3 3 4
2 3 3
3 3 3
3 3 3
2 3 5
1 2 6
4 6 5

输出：
Orz
1
2

提示：
1.第一个样例小杰的能力值1小于5，所以没有安全区，输出Orz
2.第三个样例小杰的能力值为5，则可以去值为(1，2，4，5)四个地方，而 (1，2，4) 三个地方互相连通组成一个安全区，5自己所以答案为2

解答

一道中规中矩的BFS题目。判断矩阵的每个元素是否超过\(X\)，从而将其处理成一个01矩阵，再通过BFS来寻找这个矩阵中的连通块数量即可。

代码

# include <bits/stdc++.h>
# define pi pair<int,int>
using namespace std;

const int N=1004;
int n,m,a[N][N],vis[N][N];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
void bfs(int sx,int sy){
    queue<pi>q;
    q.push(pi(sx,sy));
    while(!q.empty()){
        auto [px,py]=q.front();q.pop();
        for(int i=0;i<4;i++){
            int x=px+dx[i],y=py+dy[i];
            if(x<1||y<1||x>n||y>m||vis[x][y]||a[x][y]==0) continue;
            vis[x][y]=1;
            q.push(pi(x,y));
        }
    }
}
int main() {
    int T,x,y;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d %d",&n,&m,&x);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&y);
                a[i][j]=(x>=y);
                vis[i][j]=0;
            }
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(a[i][j]&&!vis[i][j]){
                    bfs(i,j);
                    ++cnt;
                }
            }
        }
        if(cnt==0) puts("Orz");
        else printf("%d\n",cnt);
    }
}

5、line

假设平面上有\(n\)条直线，且不存在三条或以上直线共点的情况，求这\(n\)条直线可能存在多少种不同交点数。

例\(n=2\),则可能的交点数量为\(0\)(平行)或者\(1\)(不平行)。

输入

输入数据包含多个测试实例，每个测试实例占一行。每行包含一个正整数\(n(n\le 20),n\)表示直线的数量。

输出

每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数，每行的整数之间用一个空格隔开。

样例

输入：
2
3

输出：
0 1
0 2 3

解答

首先回顾一下这个观点：两条直线如果没有交点，当且仅当它们是平行的。

这意味着我们可以对这些直线划分成多个组，组内的直线是平行的，组间的直线是不平行的。因此可以考虑使用动态规划的思想解决，每次为当前的直线添加\(j\)条相互平行的直线，并且这\(j\)条直线和原来的直线相交，从而产生交点。

更具体的来说，令\(S_i\)表示有\(i\)条直线时，它们的交点个数的集合。如果\(x\in S_{i-j}\)，并且为这个方案再添加\(j\)条平行线（它们和原来的直线都不平行），那么就会和原来的\(i-j\)条直线总共产生\(j(i-j)\)个新交点。因此\(S_i\)的递推式可以形式化地写出为：

\[S_i=\bigcup_{j=1}^i\{x+j(i-j)\mid x\in S_{i-j}\}\]

其中\(S_0=\{0\}\)，因为没有直线就不会有交点。最终只需要打印集合\(S_n\)中的所有数即可。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=20;
vector<int>g[N+4];
int main() {
    int T,n;
    g[0].push_back(0);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=i;j++){
            for(int x:g[i-j]){
                g[i].push_back(x+j*(i-j));
            }
        }
        sort(g[i].begin(),g[i].end());
        g[i].resize(unique(g[i].begin(),g[i].end())-g[i].begin());
    }
    while(~scanf("%d",&n)){
        for(int i=0;i<g[n].size();i++){
            printf("%d%c",g[n][i], " \n"[i+1==g[n].size()]);
        }
    }
}