面经25届秋招-科大讯飞研发岗笔试真题卷（3）
25届秋招-科大讯飞研发岗笔试真题卷（3）

第一题：树的排列
在线测评链接：https://www.sspnote.com/oj/3/339
题目描述
给定一棵树，每个节点有一个权值。现在每次可以交换任意两个节点的权值，请问最少需要多少次交换可以使得每个节点的权值等于它的
编号？保证给出的权值是一个排列，也就是说保证一定有解。
输入描述
第一行输入一个正整数  $n(2\le n\le 1000)$ ，代表树上的节点数量。
第二行输入  $n$  个正整数  $a_1, a_2, ..., a_n$ ，第  $i$  个数字表示节点  $i$  的权值，这  $n$  个数互不相同。
接下来的  $n - 1$  行，每行输入两个正整数  $u,v(1\le u,v\le n)$ ，代表节点  $u$  和节点  $v$  有一条边相连。
输出描述
一个整数，代表最小的交换次数。
样例
输入
4
2 1 4 3
1 2
2 3
2 4
输出
2
题解：模拟
注意，这是笔试第一题！！不是第三题，所以不要被题目图论的背景所迷惑，其实这道题和树结构一点关系都没有，就是纯纯迷惑作用。
由于可以交换任意两个节点，因此我们从第一个位置开始遍历，当有 $a_i\ne i$ 的时候，直接交换 $(a_i,a_{a_i})$ 的位置即可，大家可以手动模拟一
下。
C++
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,a[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        while(a[i]!=i){
            swap(a[i],a[a[i]]);
            cnt++;
        }
    }
    cout<<cnt<<endl;
    
    return 0;
}
Java
import java.util.Scanner;

public class Main {
    private static final int N = 1010;
    private static int[] a = new int[N];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }
        for (int i = 1; i < n; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            while (a[i] != i) {
                int temp = a[i];
                a[i] = a[a[i]];
                a[temp] = temp;
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}
Python
n = int(input())
a = [0] + list(map(int, input().split()))
for _ in range(n - 1):
    x, y = map(int, input().split())
cnt = 0
for i in range(1, n + 1):
    while a[i] != i:
        temp=a[i]
        a[i]=a[a[i]]
        a[temp]=temp
        cnt += 1
print(cnt)
第二题：东八区时间
在线测评链接：https://www.sspnote.com/oj/3/340
题目描述
东八区(UTC/GMT+08:00)是比世界协调时间(UTC)/格林尼治时间(GMT)快8小时的时区，理论上的位置是东经112.5度至127.5度之间。在
此15度的范围内，统一采用以东经120度中心线的地方时间为准。是东盟标准的其中一个候选时区。当格林尼治标准时间为00:00时东八
区的标准时间为08:00。
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数 $T(1\le T\le 10^4)$ 代表数据组数，每组测试数据描述如下：
在一行上输入一个格式为"小时:分钟"的北京时间(24小时制)
输出描述
对于每一组测试数据，在一行上输出对应的世界协调时间，注意小时和分钟都应当补0至两位数。
样例
输入
2
8:30
00:00
输出
00:30
16:00
题解：模拟
本题的题意其实就是把当前的时间减去8小时，然后输出新的时间。
我们可以根据传入的字符串，处理出当前时间的小时和分钟，记为 $hour,mintue$ 
其实只需要将 $hour$ 减去8即可，不过需要注意 $hour$ 变成负数的情况，这里有一个小技巧，可以让其对24取模。
然后最终需要判断是否需要对 $hour$ 和 $mintue$ 补前导0。
C++
#include<bits/stdc++.h>
using namespace std;
void solve(){
    string s;
    cin>>s;
    int pos=s.find(':');  //时间和分钟的分割线
    int hour=stoi(s.substr(0,pos)),mintue=stoi(s.substr(pos+1)); 
    hour=(hour-8+24)%24;
    string left=to_string(hour),right=to_string(mintue);
    if(left.size()<2){
        left="0"+left;
    }
    if(right.size()<2){
        right="0"+right;
    }
    string t=left+":"+right;
    cout<<t<<endl;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
Java
import java.util.Scanner;

public class Main {
    static Scanner scanner = new Scanner(System.in);
    public static void solve() {
        String s = scanner.next();
        int pos = s.indexOf(':');
        int hour = Integer.parseInt(s.substring(0, pos));
        int minute = Integer.parseInt(s.substring(pos + 1));
        hour = (hour - 8 + 24) % 24;
        String left = String.format("%02d", hour);
        String right = String.format("%02d", minute);
        String t = left + ":" + right;
        System.out.println(t);
    }

    public static void main(String[] args) {
        int T = scanner.nextInt();
        while (T-- > 0) {
            solve();
        }
    }
}
Python
def solve():
    s = input()
    pos = s.index(':')
    hour = int(s[:pos])
    minute = int(s[pos + 1:])
    hour = (hour - 8 + 24) % 24
    left = str(hour).zfill(2)
    right = str(minute).zfill(2)
    t = left + ":" + right
    print(t)

T = int(input())
for _ in range(T):
    solve()
第三题：最长树链
在线测评链接：https://www.sspnote.com/oj/3/341
题目描述
给出 $n$ 个点的树，节点编号为 1 到  $n$ ，根节点为 1，每个节点有一个权值。
我们想在这棵树上找一条最长的链，使得这个链上的节点均满足  $a_{f_n} \le a_i$  或者均满足  $a_{f_n} \ge a_i$ ，其中  $fa_i$  表示的父亲节点，我们假定 $fa_1 = 1$ 。
输出这个最长链的节点数。
输入描述
第一行输入一个整数  $n(1 \leq n \leq 10^5)$ 代表树上的节点个数。
第二行输入  $n$  个整数  $a_1, a_2,..., a_n(1 \leq a_i \leq 10^5)$ 代表每一个节点的权值。
此后  $n-1$  行，每行输入两个整数  $u_i,v_i(1 \leq u_i, v_i \leq n; u_i \neq v_i)$ 表示树上第 $i$  条边连接节点  $u_i$  和  $v_i$ 。保证树是联通的，没有重边。
输出描述
在一行上输出一个整数代表最长链的节点个数。
样例
输入
5
1 2 3 4 5
1 2
2 3
1 4
4 5
输出
5
样例解释
最长的链是  $3\to 2\to 1\to 4\to 5$ 
题解：树形DP
本题可以说又是咱们OJ的一道模板题的改编，大家可以先去做一下这道题：树的直径-内推鸭 (sspnote.com)
然后，我们根据动态规划的三要素：状态方程定义、状态转移方程、状态初始化来分析这道题
状态方程定义
定义 $f[i][0/1]$ 表示以 $i$ 为根节点的子树中，(子树所有节点的权值都 $\le a[i]$ ),从子树某个节点到达 $i$ 的最长路径为 $f[i][0]$ ，次长路径为 $f[i][1]$ （这个路径是不包含 $i$ 节点本身的路径）
状态初始化
所有状态初始化为0即可。
状态转移方程
根据树形DP的核心思想：利用子节点的信息来更新父节点的信息可以得出
我们先考虑 $f$ 数组的状态转移方程，如果对于 $i$ 的子节点 $u$ 满足 $a[u]\le s[i]$ 
情况1： $f[u][0]+1\ge f[i][0]$ ，说明当前以 $i$ 为根节点的子树的最长路径可以更新，最长路径如果更新了，那么次长路径一定也会更新为旧的最长路径，因此有 $f[i][1]=f[i][0],f[i][0]=f[u][0]+1$ 
情况2： $f[u]0]+1>f[i][1]$ ，说明当前以 $i$ 为根节点的子树的次长路径可以更新，因此有 $f[i][1]=f[u][0]+1$ 
在递归处理完 $i$ 的所有子节点之后，就可以更新最大值 $res=max(res,f[i][0]+f[i][1]+1)$ （加1是因为需要加上 $i$ 节点本身）
同理我们可以得到 $g$ 数组的状态转移方程
C++
#include<bits/stdc++.h>
using namespace std;

const int N = 1E5 + 10;
vector<int> edges[N];
int n, a[N];
int f[N][2];  // 以i为根节点的子树中(子树所有节点的权值都<=a[i]),从子树某个节点到达i的最长路径为f[i][0]，次长路径为f[i][1]
int g[N][2];  // 以i为根节点的子树中(子树所有节点的权值都>=a[i]),从子树某个节点到达i的最长路径为f[i][0]，次长路径为f[i][1] 
int res;   // 最大值

void dfs(int u, int fa) {
    for(int& x : edges[u]) {
        if(x == fa) continue;
        dfs(x, u);  // 更新子节点信息
        if(a[u] >= a[x]) {
            if(f[x][0] + 1 >= f[u][0]) {  // 最长路径要更新，次长路径更新为旧的最长路径
                f[u][1] = f[u][0];  // 先更新次长路径
                f[u][0] = f[x][0] + 1;  // 在更新最长路径
            } else if(f[x][0] + 1 > f[u][1]) {  // 仅更新次长路径即可
                f[u][1] = f[x][0] + 1;
            }
        }
        if(a[u] <= a[x]) {
            if(g[x][0] + 1 >= g[u][0]) {  // 最长路径要更新，次长路径更新为旧的最长路径
                g[u][1] = g[u][0];  // 先更新次长路径
                g[u][0] = g[x][0] + 1;  // 在更新最长路径
            } else if(g[x][0] + 1 > g[u][1]) {  // 仅更新次长路径即可
                g[u][1] = g[x][0] + 1;
            }
        }
    }
    res = max(res, f[u][0] + f[u][1] + 1);
    res = max(res, g[u][0] + g[u][1] + 1);
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    dfs(1, 0);
    cout << res << endl;
    return 0;
}
Java
import java.util.*;

public class Main {
    static final int N = (int)1e5 + 10;
    static List<Integer>[] edges = new ArrayList[N];
    static int n;
    static int[] a = new int[N];
    static int[][] f = new int[N][2];  // 以i为根节点的子树中(子树所有节点的权值都<=a[i]),从子树某个节点到达i的最长路径为f[i][0]，次长路径为f[i][1]
    static int[][] g = new int[N][2];  // 以i为根节点的子树中(子树所有节点的权值都>=a[i]),从子树某个节点到达i的最长路径为f[i][0]，次长路径为f[i][1] 
    static int res;   // 最大值

    static void dfs(int u, int fa) {
        for(int x : edges[u]) {
            if(x == fa) continue;
            dfs(x, u);  // 更新子节点信息
            if(a[u] >= a[x]) {
                if(f[x][0] + 1 >= f[u][0]) {  // 最长路径要更新，次长路径更新为旧的最长路径
                    f[u][1] = f[u][0];  // 先更新次长路径
                    f[u][0] = f[x][0] + 1;  // 在更新最长路径
                } else if(f[x][0] + 1 > f[u][1]) {  // 仅更新次长路径即可
                    f[u][1] = f[x][0] + 1;
                }
            }
            if(a[u] <= a[x]) {
                if(g[x][0] + 1 >= g[u][0]) {  // 最长路径要更新，次长路径更新为旧的最长路径
                    g[u][1] = g[u][0];  // 先更新次长路径
                    g[u][0] = g[x][0] + 1;  // 在更新最长路径
                } else if(g[x][0] + 1 > g[u][1]) {  // 仅更新次长路径即可
                    g[u][1] = g[x][0] + 1;
                }
            }
        }
        res = Math.max(res, f[u][0] + f[u][1] + 1);
        res = Math.max(res, g[u][0] + g[u][1] + 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            edges[i] = new ArrayList<>();
        }
        for(int i = 1; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            edges[a].add(b);
            edges[b].add(a);
        }
        dfs(1, 0);
        System.out.println(res);
    }
}
Python
import sys
from collections import defaultdict

N = int(1e5) + 10
edges = defaultdict(list)
n = 0
a = [0]*N
f = [[0]*2 for _ in range(N)]  # 以i为根节点的子树中(子树所有节点的权值都<=a[i]),从子树某个节点到达i的最长路径为f[i][0]，次长路径为f[i][1]
g = [[0]*2 for _ in range(N)]  # 以i为根节点的子树中(子树所有节点的权值都>=a[i]),从子树某个节点到达i的最长路径为f[i][0]，次长路径为f[i][1] 
res = 0   # 最大值

def dfs(u, fa):
    global res
    for x in edges[u]:
        if x == fa:
            continue
        dfs(x, u)  # 更新子节点信息
        if a[u] >= a[x]:
            if f[x][0] + 1 >= f[u][0]:  # 最长路径要更新，次长路径更新为旧的最长路径
                f[u][1] = f[u][0]  # 先更新次长路径
                f[u][0] = f[x][0] + 1  # 在更新最长路径
            elif f[x][0] + 1 > f[u][1]:  # 仅更新次长路径即可
                f[u][1] = f[x][0] + 1
        if a[u] <= a[x]:
            if g[x][0] + 1 >= g[u][0]:  # 最长路径要更新，次长路径更新为旧的最长路径
                g[u][1] = g[u][0]  # 先更新次长路径
                g[u][0] = g[x][0] + 1  # 在更新最长路径
            elif g[x][0] + 1 > g[u][1]:  # 仅更新次长路径即可
                g[u][1] = g[x][0] + 1
    res = max(res, f[u][0] + f[u][1] + 1)
    res = max(res, g[u][0] + g[u][1] + 1)


n = int(input())
a = [0]+list(map(int, input().split()))
for _ in range(n - 1):
    u, v = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)
dfs(1, 0)
print(res)