题解：P9806 [POI 2022 ~2023R1] poc

Yxa_Sheep · 2025-06-11 21:04:20 · 题解

upd on 2025/6/15：修改了代码。

题意

从 a 数组里挑出 b 数组。对于第 i 项，如果可以被选中就输出 1，否则输出0。

思路

一开始想用深搜，当看到 n,m,k\le3\times10^5 这里就立刻放弃了。从后往前遍历，找到 b_i 在 a 序列中最后出现的地方，存入数组 lst。再从前往后遍历，用 fst 数组存储这个数是从左往右满足的第几个数，如果第 i 个数已经满足条件并且在最后一次出现之前，就输出 1，否则输出 0。

代码（就不放注释了）

#include <bits/stdc++.h>
using namespace std;
int n, m, k, tot, a[300010], b[300010], lst[300010], fst[300010];
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++)
        scanf("%d", &b[i]);
    for (int i = n, j = m; i >= 1; i--)
        if (a[i] == b[j])
            lst[j--] = i;
    for (int i = 1, j = 1; i <= n; i++)
    {
        if (a[i] == b[j])
            fst[a[i]] = j++;
        printf("%d ", fst[a[i]] && i <= lst[fst[a[i]]]);
    }
    return 0;
}

完结!!!求过。