笔试时间：2023年3月29日 春招实习

第一题

题目：数字的圆圈

游游拿到了一串数字，她想知道这串数字一共有多少个圆圈？

提示：数字0，6，9这三种数字各有一个圆圈，数字8共有两个圆圈。

输入描述

一个字符串，仅有数字字符组成。

长度不超过100000。

输出描述

该字符串包含的圆圈的数量。

样例输入

123457890

样例输出

4

参考题解

直接枚举计算就行了。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    string s;
    cin >> s;

    unordered_map<char, int> dic;

    for (char c : s) {
        dic[c]++;
    }

    int res = 0;
    res += dic['0'] + dic['6'] + dic['9'] + dic['8'] * 2;
    cout << res << endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();

        Map<Character, Integer> dic = new HashMap<>();

        for (char c : s.toCharArray()) {
            dic.put(c, dic.getOrDefault(c, 0) + 1);
        }

        int res = 0;
        res += dic.getOrDefault('0', 0) + dic.getOrDefault('6', 0) + dic.getOrDefault('9', 0) + dic.getOrDefault('8', 0) * 2;
        System.out.println(res);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

s = input()
from collections import Counter
dic = Counter(s)

res = 0
res += dic['0'] + dic['6'] + dic['9'] + dic['8']*2
print(res)

第二题

题目：好元素

游游定义一个排列中，满足以下条件的元素为”好元素“：对于第i个元素ai 而言，ai 是前i个元素的最大值。例如，[3,1,5,2,4]，第一个和第三个元素是好元素。游游希望你构建一个长度为n的排列，其中有k个好元素，且任意两个好元素相邻。你能帮帮她吗？

排列的定义：由1到n的所有正整数组成的长度为n的数组，每个正整数正好出现一次。

输入描述

两个正整数n，k，用空格隔开。

1<=n<=105

1<=k<=[n//2]

输出描述

一行n个正整数，代表游游构造的排列。有多解的时候输出任意即可。

样例输入

5 2

样例输出

4 2 5 1 3

参考题解

贪心算法。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> ans(n);

    for (int i = 0; i < n; i++) {
        ans[i] = i + 1;
    }

    int j = n - k;
    int i = 0;
    int pos = 0;

    while (pos < k) {
        swap(ans[i], ans[j]);
        i += 2;
        pos++;
        j++;
    }

    for (int r : ans) {
        cout << r << " ";
    }

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        int[] ans = new int[n];

        for (int i = 0; i < n; i++) {
            ans[i] = i + 1;
        }

        int j = n - k;
        int i = 0;
        int pos = 0;

        while (pos < k) {
            int temp = ans[i];
            ans[i] = ans[j];
            ans[j] = temp;
            i += 2;
            pos++;
            j++;
        }

        for (int r : ans) {
            System.out.print(r + " ");
        }
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n, k = map(int, input().split(" "))

ans = [i for i in range(1, n + 1)]
j,i = n - k, 0
pos = 0

while pos < k:
    ans[i], ans[j] = ans[j], ans[i]
    i += 2
    pos += 1
    j += 1

for r in ans:
    print(r, end=" ")

第三题

题目：树上的染色

游游拿到一棵树，树的每条边有边权。游游准备选择一些边染成红色，她希望不存在两条染红的边共用同一个点，且最终染红边的边权之和尽可能大。你能帮帮她吗？

注：所谓树，即不包含重边、自环和回路的无向连通图。

输入描述

第一行输入一个正整数n，代表节点的数量。

接下来n-1行，每行输入三个正整数u,v,w，代表点u和点v之间有一条权值为w的无