Znzryb's Blog
0%

ABC-381-E - 11/22 Subsequence

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……）