Znzryb's Blog
0%

ABC-391-E - Hierarchical Majority Vote（三叉线段树）

Posted on Edited on

思路讲解

就是这么说那，还是不要省一些东西，lson简写成 l 容易导致误解使自己写错

然后三分可以这么写

1
2
3
4
5
6
7
8
m1=l+(r-l)/3;
m2=l+2*(r-l)/3;
tr[++tot].st=l,tr[tot].ed=m1;
tr[x].l=tot;
tr[++tot].st=m1+1,tr[tot].ed=m2;
tr[x].m=tot;
tr[++tot].st=m2+1,tr[tot].ed=r;
tr[x].r=tot;

AC代码

AC

https://atcoder.jp/contests/abc391/submissions/62327989

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
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef pair<ll,bool> plb;
typedef double DB;
const ll MAXN=static_cast<ll>(2e6)+10,MAXval=static_cast<ll>(1e18)+3;

ll N;
ll pow3[18];
// vector<ll> needChange[2][15];
bool stand;
bool A[MAXN];	// 经过修改的字符串（N即是未修改）
ll tot;

struct Tree{
	ll l,m,r;
	// bool val;
	ll st,ed;
}tr[MAXN*4];

inline plb buildTree(ll x){
	if(tr[x].st==tr[x].ed) {
		// cout<<tr[x].st<<' '<<tr[x].ed<<'\n';
		return {1,A[tr[x].st]};
	}
	ll l=tr[x].st,r=tr[x].ed;
	ll m1,m2;
	m1=l+(r-l)/3;
	m2=l+2*(r-l)/3;
	tr[++tot].st=l,tr[tot].ed=m1;
	tr[x].l=tot;
	tr[++tot].st=m1+1,tr[tot].ed=m2;
	tr[x].m=tot;
	tr[++tot].st=m2+1,tr[tot].ed=r;
	tr[x].r=tot;
	// needChange 如果要改动需要改动多少
	vector<ll> needCh[2];
	// cout<<tr[x].st<<' '<<tr[x].ed<<'\n';
	plb rec1=buildTree(tr[x].l);
	needCh[rec1.second].push_back(rec1.first);
	plb rec2=buildTree(tr[x].m);
	needCh[rec2.second].push_back(rec2.first);
	plb rec3=buildTree(tr[x].r);
	needCh[rec3.second].push_back(rec3.first);
	if(needCh[0].size()>needCh[1].size()){
		if(needCh[0].size()-needCh[1].size()==1){
			return {min(needCh[0][0],needCh[0][1]),false};
		}else{
			sort(all(needCh[0]));
			return {needCh[0][0]+needCh[0][1],false};	
		}
	}else{
		if(needCh[1].size()-needCh[0].size()==1){
			//           改动该点值的代价             该点的值
			return {min(needCh[1][0],needCh[1][1]),true};
		}else{
			sort(all(needCh[1]));
			return {needCh[1][0]+needCh[1][1],true};	
		}
	}
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	pow3[0]=1;
	FOR(i, 1, 15){
		pow3[i]=pow3[i-1]*3;
	}
	FOR(i, 1, pow3[N]){
		char a;
		cin>>a;
		if(a=='1') A[i]=true;
		else A[i]=false;
	}
	
	tr[++tot].st=1,tr[tot].ed=pow3[N];
	plb rec=buildTree(tot);
	cout<<rec.first<<'\n';
	// cout<<A[0][1]<<'\n';
	return 0;
}

/*
AC
https://atcoder.jp/contests/abc391/submissions/62327989
*/

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