2025年复旦大学计算机保研复试机试真题

2025年复旦大学计算机保研复试上机真题

历年复旦大学计算机保研复试上机真题

历年复旦大学计算机保研复试机试真题

更多学校题目开源地址：https://gitcode.com/verticallimit1/noobdream

N 诺 DreamJudge 题库：输入 “学校名称” 即可筛选该校历年机试真题，题目均在考纲范围内，按难度自动排序。还可搭配《计算机考研机试攻略》刷题，书中题目可通过题号直接在题库中查找。

回文字符子序列

题目描述

Time Limit: 1000 ms
Memory Limit: 256 mb

给定一个由小写英文字母组成的字符串 `s` 和一个整数 `mode`（取值为 1 或 2），请完成如下任务：

- 当 `mode = 1` 时，计算并输出字符串 `s` 的最长回文子序列的长度；

- 当 `mode = 2` 时，找出并输出 `s` 的其中一个最长回文子序列的字符串（若存在多个最长回文子序列，输出字典序最小的那个）。

注：子序列是指从原字符串中删除部分字符（也可以不删除）后，剩余字符保持原有相对顺序组成的新字符串；回文是指正读和反读都相同的字符串。

输入输出格式

输入描述:

第一行输入一个非空字符串 `s`，字符串仅由小写英文字母构成； 第二行输入一个整数 `mode`（取值为 1 或 2）。

输出描述:

根据 `mode` 的值输出对应结果。

输入输出样例

输入样例#:

bbbab
1

输出样例#:

4

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

// 计算最长回文子序列的长度
int longestPalindromeSubseq(const string& s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                dp[i][j] = (len == 2) ? 2 : dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[0][n - 1];
}

// 获取字典序最小的最长回文子序列
string getLexicographicallySmallestLPS(const string& s) {
    int n = s.size();
    
    // 计算最长回文子序列长度
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                dp[i][j] = (len == 2) ? 2 : dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // 使用动态规划存储每个区间的最优字符串
    vector<vector<string>> strDP(n, vector<string>(n, ""));
    
    // 初始化单个字符
    for (int i = 0; i < n; i++) {
        strDP[i][i] = string(1, s[i]);
    }
    
    // 填充 strDP 表格
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            
            if (s[i] == s[j]) {
                if (len == 2) {
                    strDP[i][j] = string(1, s[i]) + s[j];
                } else {
                    strDP[i][j] = s[i] + strDP[i + 1][j - 1] + s[j];
                }
            } else {
                if (dp[i + 1][j] > dp[i][j - 1]) {
                    strDP[i][j] = strDP[i + 1][j];
                } else if (dp[i][j - 1] > dp[i + 1][j]) {
                    strDP[i][j] = strDP[i][j - 1];
                } else {
                    // 长度相等，选择字典序较小的
                    strDP[i][j] = min(strDP[i + 1][j], strDP[i][j - 1]);
                }
            }
        }
    }
    
    return strDP[0][n - 1];
}

int main() {
    string s;
    int mode;
    
    cin >> s;
    cin >> mode;
    
    if (mode == 1) {
        cout << longestPalindromeSubseq(s) << endl;
    } else {
        cout << getLexicographicallySmallestLPS(s) << endl;
    }
    
    return 0;
}