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

WonderStone_ · 2025-10-25 21:24:07 · 题解

题目传送门

题目大意

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

核心思路

要判断小 A 中位置 i 的车辆是否符合条件，需满足两个核心条件：

• 车辆类型匹配：a_i 必须和小 B 看到的某位置 j 的类型相同（即 a_i=b_j）。

• 位置合法性：i 可作为子序列中 b_j 的对应位置，即：

看到这，应该不难看出：可以 O(n) 预处理并计算答案。因此，为高效验证上述条件，引入两个关键数组：

最终判断规则：若存在 j 使得 a_i=b_j 且 l_j≤i≤r_j，则 a_i 可能被记录（输出 1），否则输出 0（详见代码）。

代码详解

#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;
}