Znzryb's Blog
0%

Posted on Edited on

思路讲解

我们先考虑不向左循环移动的情况，那么实际上这个块要么从左边转移过来，要么从上边转移过来。

那么如果加了向左循环移动那？首先dp里存的东西变成了到达此块的总代价即题目中的（kx+y）（y即经过之点的权重之和）

转移的话，从上面转移还是简单，就是要多加一个 K* 向左循环移动次数就行。

如果需要从左边转移，那么要注意，此时只有第一个块需要加一个 K* 向左循环移动次数，后面的块是不需要的，这个要小心一点。

（其实严格来说只有第一行第一个块需要加，因为后面的块都是先从上面转移下来，已经加过一个这个了，不过我也懒得这么严格，因为我的左边界是无穷大除了第一行第一个块旁边是0）

AC代码

https://codeforces.com/contest/2049/submission/299989686

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#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>

typedef long long ll;
const ll MAXDP=1e15+7;
ll n,T,m,K;
ll maze[210][210];
ll dp[210][210][210],dpUp[210][210];
// dpUp是指无视向左循环移动次数的最优解

// move函数是以该位置为主体的，即移动
inline ll move(ll x, ll step){
    if(x+step<=m){
        return x+step;
    }else{
        return (x+step)%m;
    }
}
inline void init() {
    for(int i=0;i<=n;++i) {
        for(int j=0;j<=m;++j) {
            dpUp[i][j]=MAXDP;
            for(int k=0;k<=m;++k) {
                dp[i][j][k]=MAXDP;
            }
        }
    }
}


inline void solve(){
    std::cin>>n>>m>>K;
    // memset(maze,0,sizeof(maze));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            std::cin>>maze[i][j];
        }
    }
    // memset(dp, 0x3f, sizeof(dp));
    // memset(dpUp, 0x3f, sizeof(dpUp));
    init();
    for(int i=0;i<m;++i) {  // 第1行左边的数我们全部设为0，否则没法推
        dp[1][0][i]=0;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            for(int k=0;k<m;++k){ //k是循环移动次数，K时全局系数
                //    横向k要相等（向左循环移动次数要相等），纵向k不用相等
                if(j==1) {
                    dp[i][j][k]=std::min({dp[i][j][k],dpUp[i-1][j]+maze[i][move(j,k)]+k*K,
                        dp[i][j-1][k]+maze[i][move(j, k)]+K*k});
                }else {
                    dp[i][j][k]=std::min({dp[i][j][k],dpUp[i-1][j]+maze[i][move(j,k)]+k*K,
                        dp[i][j-1][k]+maze[i][move(j, k)]});
                }
            }
            for(int k=0;k<m;++k){
                dpUp[i][j]=std::min(dp[i][j][k],dpUp[i][j]);
            }
        }
    }
    std::cout<<dpUp[n][m]<<std::endl;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);std::cout.tie(0);
    std::cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}
/*
AC https://codeforces.com/contest/2049/submission/299989686
*/

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

这个转移公式不是每一次都要+kK，如果是从一个已经加过kK的地方转移过来的，那么就不用加了

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
        for(int k=0;k<m;++k){ //k是循环移动次数，K时全局系数
            //    横向k要相等，纵向k不用相等
            dp[i][j][k]=std::min({dp[i][j][k],dpUp[i-1][j]+maze[i][move(j,k)]+k*K,
                dp[i][j-1][k]+maze[i][move(j, k)]+K*k});
        }
        for(int k=0;k<m;++k){
            dpUp[i][j]=std::min(dp[i][j][k],dpUp[i][j]);
        }
    }
}

https://codeforces.com/contest/2049/submission/299988064

TLE，因为memset()。

1
2
// memset(dp, 0x3f, sizeof(dp));
// memset(dpUp, 0x3f, sizeof(dpUp));

Posted on Edited on

思路讲解

数位dp记忆化搜索做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// dp装的在top位为n的情况下，第i位符合要求的数字数量
ll L,R,digit[25],dp[15][25];
// 为什么要开两维？因为top位不同的情况下，结果没有加和性
//                                isTop是指该位是不是最高位
ll dfs(ll len,ll isMax,ll top,bool isTop){
	if(len==0)
		return 1;
	if(dp[top][len]!=-1 && !isMax)
		return dp[top][len];
	ll maxx,res=0;
	maxx= isMax ? digit[len]:9;
	for(int i=0;i<=maxx && i<top;++i){
		if(isTop){ // 是首数，再考虑0和非0的情况
			if(i==0){
				//                                  top=10 就是指不限制
				res+=dfs(len-1,isMax && i==digit[len],10,true);
				// 不限制的原因是前导为0，没有资格作首数
			}else{
				// 是top数，可以改top
				res+=dfs(len-1, isMax && i==digit[len], i, false);
			}
		}else{
			// 不是top数，没有资格改top
			res+=dfs(len-1, isMax && i==digit[len], top, false);
		}
	}
	if(!isMax)
		dp[top][len]=res;
	return res;
}

以下为思维做法，了解数位dp后觉得有点玄学

我的思路就是先算出1～两个数之间的snake number数量，再将两者相减。

我们以1～90011来解释我们的运算过程

90011可以拆成首位为0～9的情况，其中2～8的计算相对简单，首位已经确定，后面每位有首位种选择，snake number 数量就是 首位^后面的位子数

0的情况就是

1
2
3
4
5
6
7
8
// 假设首位为0情况
if(i==0){
	for(int j=0;j<s.size()-1;++j){
		for(int k=1;k<=9;++k){
			res+=pown[k][j];
		}
	}
}

9的情况就是和2～8一样正常算，然后把不可行的情况数剪掉

1
2
3
4
5
if(i==s[0]-'0'){
	for(int j=0;j<s.size()-1;++j){
		res-=(s[0]-'0'-1-(s[s.size()-j-1]-'0'))*pown[i][j];
	}
}

具体而言如下图

image

AC代码

AC https://atcoder.jp/contests/abc387/submissions/61678607

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10;

// dp装的在top位为n的情况下，第i位符合要求的数字数量
ll L,R,digit[25],dp[15][25];
// 为什么要开两维？因为top位不同的情况下，结果没有加和性
//                                isTop是指该位是不是最高位
ll dfs(ll len,ll isMax,ll top,bool isTop){
	if(len==0)
		return 1;
	if(dp[top][len]!=-1 && !isMax)
		return dp[top][len];
	ll maxx,res=0;
	maxx= isMax ? digit[len]:9;
	for(int i=0;i<=maxx && i<top;++i){
		if(isTop){
			if(i==0){
				//                                  top=10 就是指不限制
				res+=dfs(len-1,isMax && i==digit[len],10,true);
				// 不限制的原因是前导为0，没有资格作首数
			}else{
				// 是top数，可以改top
				res+=dfs(len-1, isMax && i==digit[len], i, false);
			}
		}else{
			// 不是top数，没有资格改top
			res+=dfs(len-1, isMax && i==digit[len], top, false);
		}
	}
	if(!isMax)
		dp[top][len]=res;
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>L>>R;
	L-=1;
	ll idx=0;
	while(L){
		digit[++idx]=L%10;
		L/=10;
	}
	memset(dp, -1, sizeof(dp));
	// 刚传进去该位肯定是最高位
	ll lRes=dfs(idx,true,10,true);
	idx=0;
	while(R){
		digit[++idx]=R%10;
		R/=10;
	}
//	memset(dp, -1, sizeof(dp));
	ll rRes=dfs(idx,true,10,true);
	cout<<rRes-lRes<<'\n';
	return 0;
}

AC https://atcoder.jp/contests/abc387/submissions/61423141

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#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 unsigned long long ll;
string L,R;
string Ls,Rs;
ll pown[11][21];

void init(){
	Ls.assign(L);
	Rs.assign(R);
	bool isChange=false;
	// 通过这种方法可以得到最靠近原数的snake number
	for(int i=1;i<Rs.size();++i){
		if(Rs[i]<Rs[0] && !isChange){
			continue;
		}
		isChange=true;
		Rs[i]=static_cast<char> (Rs[0]-1);
	}
	isChange=false;
	for(int i=1;i<Ls.size();++i){
		if(Ls[i]<Ls[0] && !isChange){
			continue;
		}
		isChange=true;
		Ls[i]=static_cast<char> (Ls[0]-1);
	}
	// 通过递推得到pow数组，方便后续计算
	for(int i=1;i<=10;++i){
		pown[i][0]=1;
		for(int j=1;j<=19;++j){
			pown[i][j]=i*pown[i][j-1];
		}
	}
}
inline ll getAns(string &s){
	ll res=0;
	for(int i=0;i<=s[0]-'0';++i){
		// 假设首位为0情况
		if(i==0){
			for(int j=0;j<s.size()-1;++j){
				for(int k=1;k<=9;++k){
					res+=pown[k][j];
				}
			}
		}else{
			// 首数为i，后面有i^(size-1)种选择
			res+=pown[i][s.size()-1];
		}
		if(i==s[0]-'0'){
			for(int j=0;j<s.size()-1;++j){
				res-=(s[0]-'0'-1-(s[s.size()-j-1]-'0'))*pown[i][j];
			}
		}
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>L>>R;
	init();
	// 先算出1-R，再算出1-L,两者相减
	ll Rto1=0,Lto1=0;
	Rto1=getAns(Rs);
	Lto1=getAns(Ls);
	if(L==Ls){
		cout<<Rto1-Lto1+1<<endl;
	}else{
		cout<<Rto1-Lto1<<endl;
	}
	return 0;
}
/*
AC https://atcoder.jp/contests/abc387/submissions/61423141
29 55

90011 98888

*/

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

Posted on Edited on

思路讲解

就是把D的连续改成了不一定连续

image

这个dp里存的是什么？

这个具体怎么想到这个dp里存的是什么要看这个视频，这个视频这方面讲的很清楚。

这个状态转移到底在干什么？其实是这样的，我们自然是枚举这个状态的最后一位是什么，这样我们才知道现在的状态是从哪里来的。

那么怎么状态转移？定义去掉最后一位的状态为pre，这个最后一位的数字肯定不会出现在dp[pre]之前，因为在dp[pre]之前，必然会截断一个成形的AA序列，无法正确形成这个状态。

image

故就是直接在dp[pre]这个位置后直接看有没有两位B，如果有，就是第二位B的位置，如果没有，就跳过。

1
2
3
4
5
6
7
if(((i>>j)&1)==1){	// 说明该位有一
	ll pre=i-(1<<j);
	ll res=upper_bound(pos[li[j]].begin(), pos[li[j]].end(), dp[pre])-pos[li[j]].begin()+1;
	if(res>=pos[li[j]].size())	// 超界
		continue;
	dp[i]=min(dp[i],pos[li[j]][res]);
}

AC代码

https://atcoder.jp/contests/abc381/submissions/61352128

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#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,maxStatus=2e6+7;
ll n,T,A[N],kind;
// dp[S] 像这样的S序列需要至少多少个A序列元素（从1开始）才能组成
int dp[maxStatus];
set<ll> diff; 
ll li[25];	// 类离散化数组，代表该索引数代表实际数组是什么
vector<int> pos[25];	// 存该值的出现位置
inline void init(){
	ll idx=0;
	// 实现离散化(使用0-based索引，与状态存储保持一致)
	for(set<ll>::iterator it=diff.begin();it!=diff.end();it++){
		li[idx++]=*it;
	}
	dp[0]=0;
	for(int i=1;i<=1<<kind;++i){
		dp[i]=9999999;
	}
}
inline ll popcount(int x){
	ll cnt=0;
	while (x) {
		x&=x-1;
		++cnt;
	}
	return cnt;
}

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];
		diff.insert(A[i]);
		pos[A[i]].push_back(i);
	}
	kind=diff.size();
	init();
	for(int i=1;i<=(1<<kind)-1;++i){
		// 
		for(int j=0;j<kind;++j){
			if(((i>>j)&1)==1){	// 说明该位有一
				ll pre=i-(1<<j);
				ll res=upper_bound(pos[li[j]].begin(), pos[li[j]].end(), dp[pre])-pos[li[j]].begin()+1;
				if(res>=pos[li[j]].size())	// 超界
					continue;
				dp[i]=min(dp[i],pos[li[j]][res]);
			}
		}
	}
	ll ans=0;
	for(int i=(1<<kind)-1;i>0;--i){	// 这个顺序不重要
		if(dp[i]==9999999)
			continue;
		ans=max(ans,popcount(i));
	}
	cout<<ans*2<<endl;
	return 0;
}
/*
AC https://atcoder.jp/contests/abc381/submissions/61352128
2
2 2

*/

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

https://atcoder.jp/contests/abc381/submissions/61352084

问题出在这个<号，应该是≤

1
for(int i=1;i<<=(1<<kind)-1;++i){

Posted on Edited on

思路讲解

需要动点脑子的二分，调了比较久

我的方法就是跑两遍二分，这样避免有情况漏考虑

跑两遍二分，因为上面的二分相当于否决了r=x-1是最优解的可能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
while(l<r){
	ll x=l+r+1>>1;
	ll cnt1=freq1[pos[x]]-freq1[down-1];
	ll cnt2=freq2[up]-freq2[pos[x]];	//这里不用减1
	ans=max(min(cnt1,cnt2)*2+1,ans);
	if(cnt1==cnt2){
		cout<< ans <<endl;
		return;
	}
	if(cnt1<cnt2){
		l=x;
	}else{
		r=x-1;
	}
}
ans=max(min(freq1[pos[l]]-freq1[down-1],freq2[up]-freq2[pos[l]]),ans);
// 跑两遍二分，因为上面的二分相当于否决了r=x-1是最优解的可能
// 下面一个二分与他互补
l=lower_bound(pos.begin(), pos.end(), down)-pos.begin();
r=upper_bound(pos.begin(), pos.end(), up)-pos.begin()-1;
while(l<r){
	ll x=l+r>>1;
	ll cnt1=freq1[pos[x]]-freq1[down-1];
	ll cnt2=freq2[up]-freq2[pos[x]];	//这里不用减1
	ans=max(min(cnt1,cnt2)*2+1,ans);
	if(cnt1==cnt2){
		cout<< ans <<endl;
		return;
	}
	if(cnt1<cnt2){
		l=x+1;
	}else{
		r=x;
	}
}
ans=max(min(freq1[pos[l]]-freq1[down-1],freq2[up]-freq2[pos[l]]),ans);

当然一些常见的优化自不必多说

AC代码

https://atcoder.jp/contests/abc381/submissions/61320459

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#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>(1e5)+10;
ll n,T;
char s[N];
ll freq1[N],freq2[N];
vector<ll> pos;	// /的位置
ll down=0,up=0;
ll ans;

void solve(){
	cin>>down>>up;
	// 二分
	ll l=lower_bound(pos.begin(), pos.end(), down)-pos.begin();
	if(pos[l]>up || l==pos.size()){// 防止pos[l]超界(以这种方法找出来的l都超界，那必然没/在里面)
		cout<<0<<endl;
		return;
	}
	ll r=upper_bound(pos.begin(), pos.end(), up)-pos.begin()-1;
	// 避免起始l==r导致WA
	ans=min(freq1[pos[l+r>>1]]-freq1[down-1],freq2[up]-freq2[pos[l+r>>1]])*2+1;
	while(l<r){
		ll x=l+r+1>>1;
		ll cnt1=freq1[pos[x]]-freq1[down-1];
		ll cnt2=freq2[up]-freq2[pos[x]];	//这里不用减1
		ans=max(min(cnt1,cnt2)*2+1,ans);
		if(cnt1==cnt2){
			cout<< ans <<endl;
			return;
		}
		if(cnt1<cnt2){
			l=x;
		}else{
			r=x-1;
		}
	}
	ans=max(min(freq1[pos[l]]-freq1[down-1],freq2[up]-freq2[pos[l]]),ans);
	// 跑两遍二分，因为上面的二分相当于否决了r=x-1是最优解的可能
	// 下面一个二分与他互补
	l=lower_bound(pos.begin(), pos.end(), down)-pos.begin();
	r=upper_bound(pos.begin(), pos.end(), up)-pos.begin()-1;
	while(l<r){
		ll x=l+r>>1;
		ll cnt1=freq1[pos[x]]-freq1[down-1];
		ll cnt2=freq2[up]-freq2[pos[x]];	//这里不用减1
		ans=max(min(cnt1,cnt2)*2+1,ans);
		if(cnt1==cnt2){
			cout<< ans <<endl;
			return;
		}
		if(cnt1<cnt2){
			l=x+1;
		}else{
			r=x;
		}
	}
	ans=max(min(freq1[pos[l]]-freq1[down-1],freq2[up]-freq2[pos[l]]),ans);
	cout<< ans <<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>T;
	for(int i=1;i<=n;++i)
		cin>>s[i];
	ll cnt1l =0,cnt2l=0;
	for(int i=1;i<=n;++i){
		if(s[i]=='1')
			cnt1l+=1;
		else if(s[i]=='2')
			cnt2l+=1;
		else
			pos.push_back(i);
		freq1[i]=cnt1l;
		freq2[i]=cnt2l;
	}
	while (T--) {
		if(pos.empty()){
			cout<<0<<endl;
			continue;
		}
		solve();
	}
	return 0;
}
/*
50 10
/211//2///1212/212/12/12/1//11111/12121//22/122221
16 19
27 45
12 32
45 49
33 42
7 9
18 46
1 5
44 45
3 23

*/

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

Posted on Edited on

思路讲解

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

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

6
1 2 2 2 3 3

这个需要2 2 3 3

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

AC代码

https://atcoder.jp/contests/abc381/submissions/61291304

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#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……）