自动搬运

查看原文

来自洛谷，原作者为

	Yxa_Sheep 打表过样例，暴力出奇迹，搜索真牛逼，骗分进省一||深搜 MLE，广搜 TLE，打表 RE，退火又 CE||删掉 display 看主页||被封取关（解封后私信）||六年级蒟蒻 ，代词请用“他”||当前状态：<离线>

搬运于2025-08-24 22:52:00，当前版本为作者最后更新于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;
}

完结!!!求过。