poj 4044 Score Sequence（暴力）-白红宇

poj 4044 Score Sequence（暴力）

阅读量：793 次

发布时间：2023-03-03

本文共 2711 字，大约阅读时间需要 9 分钟。

为了解决这个问题，我们需要找到两个班级成绩的最长公共子序列，并按照特定规则输出。以下是详细的解决思路和实现步骤：

步骤 1：读取输入并处理

读取输入，获取两个班级的成绩。

对两个班级的成绩进行排序，按降序排列。

去重处理，将每个班级的成绩转换为唯一的降序数组。

步骤 2：去重处理

遍历成绩数组，记录出现过的成绩，并跳过重复的。

生成两个去重后的数组，每个数组中的元素按降序排列。

步骤 3：寻找最长公共子序列

使用暴力枚举的方法，寻找两个数组中的最长公共子序列。

遍历每个可能的起始点，检查是否存在一个匹配的子序列。

记录最长的子序列及其具体数字。

步骤 4：排序输出

将最长公共子序列的数字按个位递增排序。

如果个位相同，按整体数字递增排序。

步骤 5：输出结果

输出最长公共子序列的数字，按照排序后的顺序。

代码实现

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
using namespace std;
// 去重并排序
void uniqueAndSort(vector
        
         & arr) { vector
         
           uniqueArr; if (arr.empty()) return uniqueArr; uniqueArr.push_back(arr[0]); for (int i = 1; i < arr.size(); ++i) { if (arr[i] != uniqueArr.back()) { uniqueArr.push_back(arr[i]); } } sort(uniqueArr.begin(), uniqueArr.end(), greater
          
           ()); } // 判断是否有公共子序列 bool hasCommonSubsequence(const vector
           
            & a, const vector
            
             & b, int len) { for (int i = 0; i < len; ++i) { if (a[i] != b[i]) { return false; } } return true; } // 找到最长公共子序列 vector
             
               findLCS(const vector
              
               & a, const vector
               
                & b) { vector
                
                  lcs; int len = 0; for (int i = 0; i < a.size(); ++i) { for (int j = 0; j < b.size(); ++j) { int currentLen = 0; while (currentLen < a.size() - i && currentLen < b.size() - j && a[i + currentLen] == b[j + currentLen]) { currentLen++; } if (currentLen > len) { len = currentLen; lcs.clear(); for (int k = 0; k < currentLen; ++k) { lcs.push_back(Node{a[i + k], a[i + k] % 10}); } } } } return lcs; } // 去重后的数组 struct Node { int num; int dig; bool operator<(const Node& other) const { if (dig == other.dig) { return num < other.num; } return dig < other.dig; } }; int main() { int test; scanf("%d", &test); while (test--) { int n1, n2; scanf("%d %d", &n1, &n2); vector
                 
                   aa(n1); vector
                  
                    bb(n2); for (int i = 0; i < n1; ++i) { scanf("%d", &aa[i]); } for (int i = 0; i < n2; ++i) { scanf("%d", &bb[i]); } // 去重排序 uniqueAndSort(aa); uniqueAndSort(bb); // 去重后的数组长度 aa.erase(remove_if(aa.begin(), aa.end(), [](int x) { return x == aa[0]; }), aa.end()); bb.erase(remove_if(bb.begin(), bb.end(), [](int x) { return x == bb[0]; }), bb.end()); // 继续处理去重后的数组 vector
                   
                     a = aa; vector
                    
                      b = bb; vector
                     
                       lcs = findLCS(a, b); if (lcs.empty()) { printf("NONE\n"); continue; } // 排序 sort(lcs.begin(), lcs.end()); // 输出 for (int i = 0; i < lcs.size(); ++i) { if (i > 0) { printf(" "); } printf("%d", lcs[i].num); } printf("\n"); } return 0; }