ZeroJudge 解題筆記：a676. 00111 - History Grading

作者：王一哲
日期：2026年1月15日


ZeroJudge 題目連結：a676. 00111 - History Grading

解題想法

寫法1，找正確的事件編號排序與學生作答的編號排序最長共同子序列長度 (longest common subsecquence, LCS)。寫法2，找最長遞增子序列 (longest increasing subsecquence, LCS)。

Python 程式碼

使用時間約為 0.9 s，記憶體約為 4.7 MB，通過測試。

import sys

def length_LCS(a, b):  # 輸入串列 a, b，回傳 LCS 長度
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

n = int(input())  # n 個事件
ans = [0]*n  # 事件編號正確的排序
for i, a in enumerate(map(int, input().split()), start=1): ans[a-1] = i
for line in sys.stdin:  # 讀取學生的答案
    stu = [0]*n  # 學生回答的事件編號排序
    for i, a in enumerate(map(int, line.split()), start=1): stu[a-1] = i
    print(length_LCS(ans, stu))  # 找 ans, stu 的 LCS 長度

使用時間約為 0.2 s，記憶體約為 4.7 MB，通過測試。

import sys
from bisect import bisect_left

def length_LIS(nums):  # 找最長遞增子序列長度
    tails = []
    for num in nums:
        idx = bisect_left(tails, num)
        if idx == len(tails): tails.append(num)
        else: tails[idx] = num
    return len(tails)

n = int(input())  # n 個事件
ans = dict()  # 事件編號: 正確排序的索引值
for i, a in enumerate(map(int, input().split()), start=1): ans[i] = a-1
for line in sys.stdin:  # 讀取學生的答案
    stu = [0]*n  # 學生回答的事件編號換成正確答案對應的索引值，如果全對為 0, 1, ..., n-1
    for i, a in enumerate(map(int, line.split()), start=1): stu[a-1] = ans[i]
    print(length_LIS(stu))

C++ 程式碼

使用時間約為 22 ms，記憶體約為 288 kB，通過測試。

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

int length_LCS(vector<int>& a, vector<int>& b) {  // 輸入串列 a, b，回傳 LCS 長度
    int m = (int)a.size(), n = (int)b.size();
    vector<vector<int>> dp (m+1, vector<int> (n+1, 0));
    for(int i=1; i<=m; i++) {
        for(int j=1; j<=n; j++) {
            if (a[i-1] == b[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

int main() {
    int n; scanf("%d", &n);  // n 個事件
    vector<int> ans (n);  // 事件編號正確的排序
    for(int i=1; i<=n; i++) {
        int a; scanf("%d", &a);
        ans[a-1] = i;
    }
    int s;  // 暫存學生答案用的變數
    while(scanf("%d", &s) != EOF) {  // 讀取學生的答案
        vector<int> stu (n);  // 學生回答的事件編號排序
        stu[s-1] = 1;  // 順序第 s-1 的事件編號為 1 
        for(int i=2; i<=n; i++) {  // 處理剩下的 n-1 個事件
            scanf("%d", &s);
            stu[s-1] = i;
        }
        printf("%d\n", length_LCS(ans, stu));  // 找 ans, stu 的 LCS 長度
    }
    return 0;
}

使用時間約為 16 ms，記憶體約為 268 kB，通過測試。

#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int length_LIS(vector<int>& nums) {  // 找最長遞增子序列長度
    vector<int> tails;
    for(int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) tails.push_back(num);
        else tails[it - tails.begin()] = num;
    }
    return (int)tails.size();
}

int main() {
    int n; scanf("%d", &n);  // n 個事件
    map<int, int> ans;  // 事件編號: 正確排序的索引值
    for(int i=1; i<=n; i++) {
        int a; scanf("%d", &a);
        ans[i] = a-1;
    }
    int s;  // 暫存學生答案用的變數
    while(scanf("%d", &s) != EOF) {  // 讀取學生的答案
        vector<int> stu (n);  // 學生回答的事件編號換成正確答案對應的索引值，如果全對為 0, 1, ..., n-1
        stu[s-1] = ans[1];  // 順序第 s-1 的事件編號為 1 
        for(int i=2; i<=n; i++) {  // 處理剩下的 n-1 個事件
            scanf("%d", &s);
            stu[s-1] = ans[i];
        }
        printf("%d\n", length_LIS(stu));  // 找 stu 的 LIS 長度
    }
    return 0;
}