2022年4月15日算法练习题

2022年4月15日算法练习题

最长公共子序列

题目来源：Daimayuan Online Judge

题目描述：给定两个从1到n的排列P1和P2，请求出这两个排列的最长公共子序列的长度。

输入格式：

第一行包含一个正整数n；接下来两行，每行包含n个数字，表示1至n的一个排列。

输出格式：

输出一个整数，表示最长公共子序列的长度。

数据范围：

1 ≤ n ≤ 10^5

示例：

输入：
5
3 2 1 4 5
2 1 3 4 5
输出：
4

解析：此题初看似乎是一个标准的动态规划问题，但由于数据规模较大（最高可达10^5），传统的二维动态规划方法（时间复杂度O(n^2)）并不适用。因此，需要寻找一种更为高效的方法来解决这个问题，理想情况下，将时间复杂度降至O(n log n)或更低。

解题思路：由于给定的两个排列仅是1至n的自然数的不同排序形式，我们可以利用这一点，通过构建一个新的数组来转换问题。具体来说，可以通过记录第二个排列中每个元素在第一个排列中的位置，将问题转化为求解这个新数组的最长递增子序列。这样，原问题就被简化为一个已知有高效解法的问题。

代码实现：

#include 
#include 

const int MAX_N = 100010;
int a[MAX_N], b[MAX_N], dp[MAX_N];
std::unordered_map pos;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    for (int i = 0; i         std::cin >> a[i];
        pos[a[i]] = i;
    }
    for (int i = 0; i         int x;
        std::cin >> x;
        b[i] = pos[x];
    }
    dp[0] = -1e9;
    int len = 0;
    for (int i = 0; i         int l = 0, r = len;
        while (l             int mid = (l + r + 1) / 2;
            if (dp[mid]             else r = mid - 1;
        }
        dp[++r] = b[i];
        len = std::max(len, r);
    }
    std::cout <    return 0;
}

线段树应用：嵌套段计数

题目来源：CodeForces

题目描述：给定一个包含2n个数字的数组，其中1至n的每个数字恰好出现两次。定义一个段为一个数字的两个出现位置之间的部分。如果一个段的所有部分都在另一个段内，则称前者被后者嵌套。对于每个段，计算其内部嵌套的段的数量。

输入格式：

第一行包含一个整数n；第二行包含2n个数字，保证1至n的每个数字恰好出现两次。

输出格式：

输出n个数字，第i个数字表示第i个段内部嵌套的段的数量。

示例：

输入：
5
5 1 2 2 3 1 3 4 5 4
输出：
1 0 0 0 3

解析：此题可以通过构建线段树来解决。线段树的每个叶子节点初始化为0，遍历数组时，记录每个数字第一次出现的位置。当遇到该数字第二次出现时，查询从第一次出现位置到当前位置之间的区间和，该区间和即为嵌套段的数量。最后，将该数字第一次出现的位置对应的叶子节点值更新为1。

代码实现：

#include 
#include 
#include