[Atcoder Beginner Contest 381 D]1122 Substring 题解

这道题在赛场上没调过，本蒟蒻想纪念一下。

题目翻译

一个数字串 $S$ 是 1122 串，需要满足：

1. $|S|$，即 $S$ 的长度是偶数。
2. 对于每一个满足 $1\le i\le \frac{|S|}{2}$整数 $i$，$S_{2i-1}=S_{2i}$。
3. 每个在 $S$ 中出现过的数字都恰好出现两次。

用人话来说，就是有一个串长成这样：AABBCC，然后不能出现重复的对子，比如 AABBCCAA 就不合法。现在给你一个长度为 $N$ 的数组 $A_i$，请问其中最长的 1122 串的长度是多少？

思路

由于 1122 串是成双成对出现的，分成两种情况讨论。

1. 从一个奇数下标开始的 1122 串。
2. 从一个偶数下标开始的 1122 串。

我们可以枚举右端点 $i$，用 $l$ 维护左端点。$i$ 每次加 $2$，如果遇到 $A_i$ 和 $A_{i+1}$ 不等的情况，就将 $l$ 赋值为 $i+2$，表示 $A_i$ 和 $A_{i+1}$ 不能被包含在一个 1122 串里。如果遇到一个 $A_i$ 与之前的某个 $A_j$ 相等，那么就得把之前的 $A_j$ 排除到 1122 串外面，所以还得用 $p{s}_i$ 记录值为 $i$ 的上一个下标，如果发现 $i\ge l$，那么 $l=i+2$。注意这里不会出现将一对的 $A_i$ 判断为重复的情况，因为 $i$ 每次加 $2$，跳过了 $i+1$。$ans$ 就取 $i+1-l+1$ 的最大值。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxlog 63
int n,a[400005],ps[400005],ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],ps[a[i]]=-10;
	int l=1;
	for(int i=1;i<=n;i+=2){
	//不需要特判i+1大于n的情况，因为a[i]>=1而a[n+1]=0，会被a[i]!=a[i+1]这一条卡掉
		if(a[i]!=a[i+1]) l=i+2;
		if(ps[a[i]]+2>l) l=ps[a[i]]+2;
		ps[a[i]]=i;
		ans=max(ans,i+1-l+1);//1.注意末端是i+1不是i
	}
	for(int i=1;i<=n;i++) ps[a[i]]=-10;
	l=2;//2.注意从2开始
	for(int i=2;i<=n;i+=2){
		if(i+1>n) continue;
		if(a[i]!=a[i+1]) l=i+2;
		if(ps[a[i]]+2>l) l=ps[a[i]]+2;
		ps[a[i]]=i;
		ans=max(ans,i+1-l+1);
	}
	cout<<ans<<endl;
	return 0;
}

其实还有一种思路，但是本人的代码目前还过不了，如果有哪位大佬看出问题了，欢迎留言

把连续的相同的数字缩成一个，并记录是几个数字缩成的，用 $fl$ 表示，当 $fl=0$ 时就是单个数字，$fl=1$ 时就是两个数字，$fl>1$ 就是多个数字。比如：

18
1 1 1 2 2 3 3 3 4 4 1 1 3 3 3 3 1 2

就会变成：(右边一列是 $fl$，左边是 $v$）

1 2
2 1
3 2
4 1
1 1
3 3
1 0
2 0

观察一下可以发现，如果 $fl=0$，就不能包含在 1122 串里面，如果 $fl=1$ 就可以包含在 1122 串里面，如果 $fl>1$ 就只能在 1122 串的头或者尾，取这些相同的数字中的前两个或者后两个，但不能让 1122 串跨过这些数字，否则一个数字出现的次数就不符合标准了。仍旧以相同的方式维护 $l$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxlog 63
int n,a[400005],tot,ps[400005],ans;
struct node{
	int v,f;
} b[400005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		if(i>1&&a[i]==a[i-1]) b[tot].f++;
		else b[++tot].v=a[i],b[tot].f=0;
	}
	int l=1;
	for(int i=1;i<=tot;i++){
		if(b[i].f==0) l=i+1;
		if(b[i].f>1){
			ans=max(ans,i-l+1);
			l=i;
		}
		if(ps[b[i].v]>=l) l=ps[b[i].v]+1;
		ps[b[i].v]=i;
		ans=max(ans,i-l+1);
	}
	cout<<ans*2<<endl;
	return 0;
}