打卡信奥刷题（3233）用C++实现信奥题 P8445 射命丸文的取材之旅

rogeliu

363人浏览 · 2026-05-09 08:38:48

rogeliu · 2026-05-09 08:38:48 发布

P8445 射命丸文的取材之旅

题目背景

射命丸文（Syameimaru Aya）是一只鸦天狗。她不定期制作名为「文文。新闻」的报纸，而为此，她需要对她收集到的新闻进行剪裁。

题目描述

射命丸文现在收集到了 $2 n$ 条新闻。她想要将其刊登于自己的报刊之上。然而，自己的报刊最多只能刊登 $n$ 条新闻。

为了能在 $n$ 条新闻的篇幅中让自己的报刊得到最大的吸引力，她将这 $2 n$ 条新闻等分成两份，即每一份中均有 $n$ 条新闻。

每一条新闻自然有着其吸引力。在第一份中，第 $i$ 条新闻有着吸引力 $a_i$ ，而在第二份中，第 $i$ 条新闻有着吸引力 $b_i$ 。这两份新闻的划分在输入时已经给定。

现在射命丸文要从中选取新闻放入自己的报刊。报刊上的第 $i$ 条新闻，将选择第一份新闻的第 $i$ 条或第二份新闻的第 $i$ 条。这样，报刊上的新闻就可以构成一个长度为 $n$ 的序列，第 $i$ 项也就是第 $i$ 条新闻有着吸引力 $ci∈{ai,bi}c_i \in \{a_i,b_i\}$ 。

而这样的一份报刊有着其综合影响力。根据射命丸文的经验，对于她这样的一份含有 $n$ 条新闻的报刊，其综合影响力为：

$max⁡{r−l+1−mex⁡{cl,cl+1,…,cr−1,cr}}(1≤l≤r≤n)\max\{r-l+1-\operatorname{mex}\{c_l,c_{l+1},\dots, c_{r-1},c_r\}\}(1\le l\le r\le n)$

其中 $mex⁡{cl,cl+1,…,cr−1,cr}\operatorname{mex}\{c_l,c_{l+1},\dots,c_{r-1},c_r\}$ 指的是 $cl,cl+1,…,cr−1,crc_l,c_{l+1},\dots,c_{r-1},c_r$ 中没有出现过的最小非负整数。

现在她希望知道，在进行这些操作之后，自己的报刊的最大的综合影响力会是多少呢？由于她还要继续取材，因此她把这个任务交付给了你。

【形式化题意】

给定序列 ${a_n\},\{b_n\}$ ，求一个序列 ${c_n\}$ 满足 $∀i∈[1,n],ci∈{ai,bi}\forall i\in[1,n],c_i\in\{a_i,b_i\}$ ，最大化

$max⁡{r−l+1−mex⁡{cl,cl+1,…,cr−1,cr}}(1≤l≤r≤n)\max\{r-l+1-\operatorname{mex}\{c_l,c_{l+1},\dots, c_{r-1},c_r\}\}(1\le l\le r\le n)$

并输出该式子可能的最大值。

输入格式

第一行一个正整数 $n$ ，表示每一份新闻中的新闻条数。

第二行 $n$ 个非负整数表示第一份新闻中每一条新闻的吸引力，即 $a1,a2…,an−1,ana_1,a_2\dots ,a_{n-1},a_n$ 。

第三行 $n$ 个非负整数表示第二份新闻中每一条新闻的吸引力，即 $b1,b2…,bn−1,bnb_1,b_2\dots ,b_{n-1},b_n$ 。

输出格式

输出一个整数，表示报刊的最大的综合影响力会是多少。

输入输出样例 #1

输入 #1

5
0 1 0 1 2
0 2 0 1 0

输出 #1

说明/提示

【样例解释和说明】

射命丸文可以让自己的 $5$ 条新闻分别取第二份的第 $1$ 条，第一份的第 $2$ 条，第一份的第 $3$ 条，第一份的第 $4$ 条和第二份的第 $5$ 条。这样一来，她的报刊每条新闻的吸引力 $c_i$ 分别为 $0, 1, 0, 1, 0$ 。令 $l = 1, r = 5$ ，则 $mex⁡{c1,c2,c3,c4,c5}=2\operatorname{mex}\{c_1,c_2,c_3,c_4,c_5\}=2$ ， $r−l+1−mex⁡{c1,c2,c3,c4,c5}=3r-l+1-\operatorname{mex}\{c_1,c_2,c_3,c_4,c_5\}=3$ ，不难证明其为数列 $c$ 的综合影响力，也是所有的可能的 $c$ 的最大综合影响力。

【数据范围】

对于 $20%20\%$ 的数据，满足 $\leq n\leq 10$ 。

另外 $40%40\%$ 的数据满足 $a_i=b_i$ 。

对于 $100%100\%$ 的数据，满足 $\leq n\le 10^6$ ， $\leq a_i,b_i\leq n$ 。

C++实现

#include<bits/stdc++.h>
#define N 1000005
#define ll long long
using namespace std;

int n,a[N],ans=-1e9;
vector<int> pos[N];

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1,b;i<=n;i++){
		b=read();
		if(b==a[i])pos[b].push_back(i); //记录x=b时的屏障的位置
	}
	for(int i=0;i<=n;i++){
		pos[i].push_back(n+1); //对所有的x在区间末尾加一个屏障，方便计算
		for(int j=0,before=1;j<pos[i].size();j++){
			ans=max(ans,pos[i][j]-before-i);
			before=pos[i][j]+1;
		}
	}
	cout<<ans;
	return 0;
}