ABC-381-D - 1122 Substring · znzryb

## 思路讲解

我是没想到这么简单就AC了

主要思路就是一直遍历，遇到完全不对的直接截断，遇到重复的把之前的去掉重新开始计数，当然有一些小的需要搞一搞的地方，比如

6
1 2 2 2 3 3

这个需要2 2 3 3

所以当步长为2往前发现不行的时候，看看可不可以回退

## AC代码

[https://atcoder.jp/contests/abc381/submissions/61291304](https://atcoder.jp/contests/abc381/submissions/61291304)

```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,A[N];
ll ans;
// 题意就是找出最长的像1122的序列
ll pos[N];	// 位置数组，该值上次出现的位置

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>A[i];
	}
	if(n==1){
		cout<<0<<endl;
		return 0;
	}
	ll cnt=0,i=2,start=1;	// start 为当前substring的起始位置
	while(i<=n){
		if(A[i-1]!=A[i]){
			ans=max(ans,cnt);
			cnt=0;
			if(A[i-1]==A[i-2]){
				i-=1;
				cnt+=2;
				start=i-1;
			}else{
				i+=1;
				start=i-1;
			}
		}else{
			if(pos[A[i]]>start){
				ans=max(ans,cnt);
				start=pos[A[i]]+1;
				cnt=i-pos[A[i]];
				pos[A[i]]=i;
				i+=2;
			}else if(pos[A[i]]==start){
				ans=max(ans,cnt);
				start=pos[A[i]];
				cnt=i-pos[A[i]]+1;
				pos[A[i]]=i;
				i+=2;
			}else{
				pos[A[i]]=i;
				cnt+=2;
				i+=2;
			}
		}
	}
	ans=max(cnt,ans);
	cout<<ans<<endl;
	return 0;
}
/*
6
1 2 2 2 3 3
AC https://atcoder.jp/contests/abc381/submissions/61291304
*/
```

## 心路历程（WA，TLE，MLE……）