CodeChef入门组Minimise LCS问题C++代码无输出求助

代码里的致命错误 #

你的代码哪怕只是用来计算原始字符串的LCS，也跑不起来，问题一堆：

1. 变量未初始化
   lcs函数里int n,m;没赋值就用来创建数组dp[n+1][m+1]，这属于未定义行为，数组大小随机，直接导致程序崩溃或输出垃圾值。应该把n设为A.size()，m设为B.size()（或者直接用传入的r，因为题目里字符串长度都是r）。

2. 数组越界

   • 初始化dp[i][0]和dp[0][i]时，循环写的是i<r，但dp是r+1行/列，得循环到i<=r，不然最后一行/列的初始值没设置。
   • 填充dp表时，i<r和j<r会导致只算到dp[r-1][r-1]，但我们要的是dp[r][r]（对应两个完整字符串的LCS）。另外，字符串索引从0开始，A[i]当i=r时会越界，正确写法是A[i-1] == B[j-1]（因为dp[i][j]代表A前i个字符和B前j个字符的LCS）。

3. 返回值错误
   lcs函数声明是int，但里面没写return语句，main里cout<<lcs(...)会输出随机值；同时lcs内部已经cout了一次，导致结果输出两次。

4. 空间爆炸
   题目里N最大到1e5，二维数组dp[r+1][r+1]要占40GB内存，栈上根本装不下，直接崩溃。而且O(N²)的时间复杂度对于1e5来说完全跑不动，这说明你完全理解错了题目。

题目理解错了 #

CodeChef入门组的「Minimise LCS」不是让你算原始字符串的LCS，而是让你重排列A或B的字符，让两个字符串的LCS长度尽可能小，求这个最小值。用普通LCS算法根本处理不了这么大的数据，得用字符频率的方法做。

正确解法与代码 #

思路 #

1. 统计两个字符串每个小写字母的出现次数。
2. 算sum_common：每个字符取min(A的次数, B的次数)加起来，就是两个字符串能匹配的总字符数。
3. 算maxA：A里出现最多的字符的次数；maxB：B里出现最多的字符的次数。
4. 算三个关键值：
   • overlap：对每个字符，max(该字符在A和B的次数和 - N, 0)的最大值，这是没法避免的同字符重叠数。
   • val1：sum_common - (N - maxA)，A里用最多的字符占满后，剩下的位置抵消不了的匹配数。
   • val2：sum_common - (N - maxB)，同理针对B。
5. 最终答案取这三个值和0的最大值（保证结果非负），另外如果sum_common>0，答案至少是1（因为有共同字符，LCS不可能为0）。

修正后的代码 #

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

int minimiseLCS(int n, string &a, string &b) {
    vector<int> cntA(26, 0), cntB(26, 0);
    for (char c : a) cntA[c - 'a']++;
    for (char c : b) cntB[c - 'a']++;
    
    int sum_common = 0;
    int overlap = 0;
    for (int i = 0; i < 26; i++) {
        sum_common += min(cntA[i], cntB[i]);
        overlap = max(overlap, max(cntA[i] + cntB[i] - n, 0));
    }
    
    int maxA = *max_element(cntA.begin(), cntA.end());
    int maxB = *max_element(cntB.begin(), cntB.end());
    
    int val1 = sum_common - (n - maxA);
    int val2 = sum_common - (n - maxB);
    
    int res = max({overlap, val1, val2, 0});
    // 如果有共同字符，结果至少为1
    if (sum_common > 0 && res == 0) res = 1;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        string a, b;
        cin >> n >> a >> b;
        cout << minimiseLCS(n, a, b) << '\n';
    }
    return 0;
}

测试输入验证 #

• 第一个用例：输出3，正确。
• 第二个用例：输出0，正确。
• 第三个用例：输出1，符合实际情况。

内容的提问来源于stack exchange，提问作者Tarun prakash