Algorithm

#include <iostream> #include <string> #include <vector> using namespace std; class Solution { public: string shortestCommonSupersequence(string a, string b) { int m = a.size(); int n = b.size(); vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) continue; 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]); } } } int i = m; int j = n; string res; while (i > 0 && j > 0) { if (a[i-1] == b[j-1]) { res += a[i-1]; --i; --j; } else { if (dp[i-1][j] < dp[i][j-1]) { res += b[--j]; } else { res += a[--i]; } } } while (i > 0) res += a[--i]; while (j > 0) res += b[--j]; reverse(res....

Version Query Hardness: \(\color{red}\textsf{Hard}\) Ralated Topics: Binary Search、Segment Tree、Heap (Priority Queue、Hash Table 一、題目 Given an information of application(APK) about its range of versions, find its corresponding OS version. If APK versions are probable for two or more OS versions, it must be belong to the latest OS version. The given apk_info structure is given as below. struct apk_info { int apk_version; int min_version = 1; int max_version = INT_MAX; }...