洛谷数据有没有素质?

B3637 最长上升子序列

5ab_juruo @ 2023-01-05 16:55:44

前情提要:https://www.luogu.com.cn/discuss/show?postid=553164

我以下面这段代码测试,注意被注释的那一行:

#include <cstdio>
using namespace std;

const int max_n = 100000;
int dp[max_n+1] = {-2147483648}, arr[max_n], ans = 1;

int ser(int low)
{
    int l = 0, r = ans + 1, mid, ret;

    while (l < r)
    {
        mid = (l + r) >> 1;

        if (dp[mid] < low)
            ret = mid, l = mid + 1;
        else
            r = mid;
    }

    return ret + 1;
}

int main()
{
    int n, pos;

    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", arr + i);

    dp[1] = arr[0];
    for (int i = 1; i < n; i++)
    {
        // if (arr[i] >= dp[ans])
        if (arr[i] > dp[ans])
        {
            dp[++ans] = arr[i];
            continue;
        }
        pos = ser(arr[i]);

        dp[pos] = arr[i];

        if (pos > ans)
            ans++;
    }

    printf("%d\n", ans);

    return 0;
}

显然,被注释的部分是错误的,可以被下面这组数据卡掉:

6
1 1 1 1 1 1

正确的输出是 1,上面那份错误的代码显然会输出 6

然后改成被注释的部分能过,实在是离了个大谱。

已经有人反馈过这个问题了:https://www.luogu.com.cn/discuss/show?postid=518643


by lfxxx @ 2023-01-05 16:56:51

B 开头的题目,应该不会加强数据。。。


by Feng_Jing @ 2023-01-05 17:00:54

addd


by fjy666 @ 2023-01-05 17:03:21

荔枝,你让我怎么荔枝?????


by __Dinic__ @ 2023-01-05 17:11:40

建议把标题改为树枝


by SDqwq @ 2023-01-05 17:16:44

荔枝,你让我怎么荔枝


by 5ab_juruo @ 2023-01-05 20:38:47

@chen_zhe


by Baoqiancheng11 @ 2023-07-10 16:30:13

有素质 ——小粉兔


|