Znzryb's Blog
0%

2025牛客WC1-F-双生双宿之探

Posted on Edited on

思路讲解

说是双指针，但是实际上是用双指针求出一个最长的好区间（同起点中），然后运用一些其他方法求出该最长双生数组中包含几个双生数组（用的是下面的前缀和）

image

这个问题转化还是很厉害的

所谓的好区间就是只有两种数的区间

至于题解讲的什么区间重叠问题好像无所谓？反正以我的统计方法，两区间统计出来的答案不会有重叠。

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74994669

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10;
ll N,T,A[MAXN];
inline void rightJ(int &j,map<ll,ll> &Cnt) { // 右移j
	++j;
	if(Cnt.find(A[j])!=Cnt.end()) {
		Cnt[A[j]]+=1;
	}else {
		Cnt[A[j]]=1;
	}
}
inline void  rightI(int &i,map<ll,ll> &Cnt) { // 右移i
	Cnt[A[i]]-=1;
	if(Cnt[A[i]]==0) Cnt.erase(A[i]);	// 这个数被减没了
	++i;
}

void solve(){
	cin>>N;
	for(int i=1;i<=N;++i) {
		cin>>A[i];
	}
	map<ll,ll> Cnt;
	Cnt[A[1]]=1;
	vector<ll> end(N+1);	// 以该点为起点的极大好区间（只含两种数数组的）的最大终点（只有是最长双生数组的起点，其值才有意义）
	fill(end.begin(),end.end(),0);
	// 双指针
	for(int i=1,j=1;j<=N && i<=N && i<=j;) { // 用双指针求最长好区间
		//cout<<i<<' '<<j<<'\n';
		// 看了一眼题解，发现是这样的，这个双指针只是用来统计极长含两种数数组的
		if(Cnt.size()==2) {
			end[i]=max(end[i],j*1LL);
			rightJ(j,Cnt);
		}else if(Cnt.size()==1) {
			rightJ(j,Cnt);
		}else {	// 不满足条件，即是size>2，需要减少区间
			rightI(i,Cnt);
		}
	}
	ll ans=0;
	vector<ll> sumA(N+10);
	// 答案统计阶段
	for(int i=1;i<=N;++i) {
		if(end[i]!=0) {	// 把不同的两种元素看成1，-1，只有前缀和相减等于0的区间才是双生数组
			// 前缀和计数数组
			unordered_map<ll,ll> sumCnt;
			sumA[i-1]=0;
			sumCnt[0]=1;	// sum为0的肯定有一个（就是起始前面一个嘛，你也可以理解为空）
			ll flag=0;	// 用来实现上面的画的辅助变量
			for(int j=i;j<=end[i];++j) {
				if(flag==A[j] || flag==0) {
					sumA[j]=sumA[j-1]+1;
					flag=A[j];
					// 查找在他之前的区间和为sumA[j](和sumA[j]相同的才相减为0，是双生数组)的数量
					ans+=sumCnt.find(sumA[j])==sumCnt.end()? 0:sumCnt[sumA[j]];
					sumCnt[sumA[j]]= sumCnt.find(sumA[j])==sumCnt.end()? 1:sumCnt[sumA[j]]+1;
				}else {
					sumA[j]=sumA[j-1]-1;
					ans+=sumCnt.find(sumA[j])==sumCnt.end()? 0:sumCnt[sumA[j]];
					sumCnt[sumA[j]]= sumCnt.find(sumA[j])==sumCnt.end()? 1:sumCnt[sumA[j]]+1;
				}
			}
		}
	}
	cout<<ans<<endl;
	// for(int i=1;i<=N;++i) {
	// 	cout<<end[i]<<' ';
	// }
	// cout<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		solve();
	}
	return 0;
}
/*
1
7
1 2 1 1 3 3 4

*/

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