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

题目传送门

题目大意

题目核心是判断小 A 记录的每辆车是否 “可能被小 B 记录”—— 即存在包含该车辆的子序列，与小 B 的记录完全一致。已知小 B 的记录一定是小 A 记录的子序列，需对小 A 的每辆车输出

1

（可能被记录）或

0

（不可能被记录）。

核心思路

要判断小 A 中位置

i

的车辆是否符合条件，需满足两个核心条件：

车辆类型匹配： $a_i$ 必须和小 B 看到的某位置 $j$ 的类型相同（即 $a_i=b_j$ ）。
位置合法性： $i$ $i$ 可作为子序列中 $b_j$ $b_{j}$ 的对应位置，即：
- $i$ 左侧有足够元素匹配 $b_{i,...,j-1}$ （保证前半段子序列存在）。
- $i$ 右侧有足够元素匹配 $b_{j+1,..,m}$ （保证后半段子序列存在）。

看到这，应该不难看出：可以

O(n)

预处理并计算答案。因此，为高效验证上述条件，引入两个关键数组：

$l_i$ ：小 B 看到的第 $i$ 个元素在小 A 看到的中最早能匹配的位置下标（构建“最左子序列”）。
$r_i$ ：小 B 看到的第 $i$ 个元素在小 A 看到的中最晚能匹配的位置下标（构建“最右子序列”）。

最终判断规则：若存在

j

使得

a_i=b_j

且

l_j≤i≤r_j

，则

a_i

可能被记录（输出

1

），否则输出

0

（详见代码）。

代码详解

CPP

#include<bits/stdc++.h>
using namespace std;
//l[i]：b[i]在a中最早匹配的位置
//r[i]：b[i]在a中最晚匹配的位置
//v[i]: 计数标记当前有效b[i]的类型
int n,m,k,a[300005],b[300005],p,d;
int l[300005],r[300005],v[300005];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	p=1; //指向小B当前需匹配的位置
	for(int i=1;i<=n;i++)
		if(a[i]==b[p]){
			l[p]=i; //记录最早位置
			p++; //匹配下一个b元素
		}
	p=m; //指向小B当前需匹配的位置（从后往前）
	for(int i=n;i>=1;i--)
		if(a[i]==b[p]){
			r[p]=i; //记录最晚位置
			p--; //匹配前一个b元素
		}
	p=1,d=1; //p为遍历l数组的指针，d为遍历r数组的指针
	for(int i=1;i<=n;i++){
        //加入所有以i为最早位置的b[j]类型（此时i>=l[j]）
		while(p<=m&&l[p]==i) v[b[p]]++,p++;
		if(v[a[i]]) cout<<"1 ";
		else cout<<"0 ";
        //移除所有以i为最晚位置的b[j]类型（此时i>r[j]）
		while(d<=m&&r[d]==i) v[b[d]]--,d++;
	}
	return 0;
}

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

文章操作

题目传送门

题目大意

核心思路

代码详解

相关推荐

评论

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