联想嵌入式软件实习笔试编程题

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《软件开发笔试汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

第一题

在一些大学里，学生发表论文的话会有一定的奖学金加分。另外，对于一篇论文，其作者的顺序不同，加分也不相同。在本题中，一篇论文最多仅三个作者，其中第一作者加3分，第二作者加2分，第三作者加1分。在这一年，学校一共有n篇论文发表。你需要输出按照字典序从小到大输出每一名作者以及其对应的加分总数是多少。

输入描述

第一行输入一个正整数n(1≤n≤100)，表示论文数量。

接下来n行，每一行第一个数字表示该篇论文的作者数，之后输入对应个数的仅由小写英文字母组成的字符串，每两个字符串用空格隔开。分别表示这一篇论文的第一作者，第二作者，....的名字。每一个作者的名字长度不超过 20。每一篇论文最多三个作者，且这三个作者名字都不同。

输出描述

按照字典序从小到大输出每个作者的名字以及其对应的加分总数，中间用空格隔开。每一个作者的信息单独输出一行。

样例输入

4

3 george annie jack

2 jack peter

2 peter bakh

1 zack

样例输出

annie 2

bakh 2

george 3

jack 4

peter 5

zack 3

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

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

    map<string, int> authorScores;
    for (int i = 0; i < n; ++i) {
        int authorCount;
        cin >> authorCount;
        
        for (int j = 0; j < authorCount && j < 3; ++j) {
            string authorName;
            cin >> authorName;
            
            // 根据作者顺序加分，第一作者3分，第二作者2分，第三作者1分
            authorScores[authorName] += 3 - j;
        }

        // 跳过多余的作者名（如果一篇论文有超过三名作者的情况）
        for (int j = 3; j < authorCount; ++j) {
            string tmp;
            cin >> tmp; // 仅读取并忽略这些作者的名字
        }
    }

    for (const auto& authorScore : authorScores) {
        cout << authorScore.first << " " << authorScore.second << endl;
    }

    return 0;
}

第二题

定义f(A)表示将序列A进行unique操作之后的序列的元素个数。unique 操作是指将相邻且相同的元素合成个元素，再按照原序列的相对顺序进行排列之后得到的序列。例如，[1,1,2,2,3,1]进行unique操作之后的序列为[1,2,3,1]; [1,2,3,3,2,1]进行unique操作之后的序列为[1,2,3,2,1]; [1,1,1,1,1,1]进行unique操作之后的序列为[1].

现在，输入一个长度为n的序列S，你需要将其划分为k段，使得每段都不为空，且你需要最大化所有段的f函数的值之和。你只需要输出这个最大值就行。

输入描述

第一行两个正整数n,k(1<=k≤n≤10000);

第二行n个由空格隔开的正整数...(1≤ai<=10000)，表示输入的序列S。

输出描述

输出一个整数，表示所求的最大值。

样例输入

8 3

1 1 1 2 2 3 3 1

样例输出

6

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

// 计算子序列s从start到end的f函数值
int f(const vector<int>& s, int start, int end) {
    int uniqueCount = 1; // 至少有一个元素
    for (int i = start + 1; i <= end; ++i) {
        if (s[i] != s[i-1]) uniqueCount++;
    }
    return uniqueCount;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> s(n+1);
    for (int i = 1; i <= n; ++i) cin >> s[i];

    vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
    // 初始化，每个位置划分为1段的情况
    for (int i = 1; i <= n; ++i) dp[i][1] = f(s, 1, i);

    // 动态规划求解
    for (int j = 2; j <= k; ++j) { // 从2段开始
        for (int i = j; i <= n; ++i) { // 至少需要j个元素才能划分为j段
            for (int m = j-1; m < i; ++m) {
                dp[i][j] = max(dp[i][j], dp[m][j-1] + f(s, m+1, i));
            }
        }
    }

    cout << dp[n][k] << endl; // 输出结果
    return 0;
}