求助！

P1439 【模板】最长公共子序列

DreamTsinghua @ 2023-09-26 08:33:36

#include <bits/stdc++.h>

using namespace std ;
int len ;
const int N = 1e5 + 10 ;

int a[N] ;
int n ;
int p[N], f[N] ;

int bound(int x) {

    int l = 1, r = len ;
    while (l < r) {
        int mid = l + r >> 1;
        if (p[f[mid]] > p[x])
            r = mid ;
        else
            l = mid + 1 ;
    }
    return l;

    int l = 1 , r = len ;
    while(l < r)
    {
        int mid = l + r + 1 >> 1 ;
        if (p[f[mid]] < p[x])
        l = mid ;
        else r = mid - 1 ;
    }

    return r + 1 ;
}

int main() {
    cin >> n ;

    for (int i = 1 ; i <= n ; i ++)
        cin >> a[i] ;

    for (int i = 1 ; i <= n ; i ++) {
        int x ;
        cin >> x ;
        p[x] = i;
    }

    for (int i = 1 ; i <= n ; i ++) {
        if (p[a[i]] > p[f[len]])
            f[++len] = a[i] ;
        else
            f[bound(a[i])] = a[i] ;
    }

    cout << len ;
    return 0 ;
}

bound 函数里面的二分有什么区别吗？第一个100 第二个20

by small_john @ 2023-09-26 09:05:16

@DreamTsinghua 毒瘤二分捏，建议使用 upper_bound

by Terrible @ 2023-09-26 10:48:18

一些整数二分的关键点： https://www.luogu.com.cn/blog/Terrible/zheng-shuo-er-fen

同上面的文章的分析：

最上面的那个相当于 check 函数依次返回 [0,0,0,...,0,1,1，...] 第一个二分是找到第一处为 1 的位置。

第二个二分的 check 函数取反了（< 改成 <=），check 函数依次返回 [1,1,1,...,1,0,0，...] 这时相当于找到第一个 0 的位置，第二个二分是找到最后一个 1 的位置，从而推导出第一个 0 我的位置，但是有一个问题，如果这个序列里全是 0 呢？得到的结果 l=r=1，推导出来的岂不是 r+1=2？因而两者是不等价的。

改成下面这个，强行补充一个 1

int bound(int x) {
    int l = 0, r = len ;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (mid==0||p[f[mid]] <= p[x])
            l = mid ;
        else
            r = mid - 1 ;
    }
    return l + 1;
}

改之后是可以通过的，但是依然不一定等价。

by Terrible @ 2023-09-26 10:56:08

还是尽量不要用推导的方法，用我文章种给出的 4 种区间框定概念最后框定出唯一的值还是比较靠谱的。

by DreamTsinghua @ 2023-09-26 12:22:23

@Terrible Thanks♪(･ω･)ﾉ大佬