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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
| \documentclass{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{xeCJK}
\usepackage{multicol}
\usepackage{tocloft}
\usepackage{xcolor}
\usepackage[cachedir=_minted-main]{minted}
\usepackage[a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}
\setminted{
breaklines=true,
breakanywhere=true,
fontsize=\small,
frame=single,
bgcolor=gray!5,
tabsize=2,
}
\renewcommand{\cftsecleader}{\cftdotfill{\cftdotsep}}
\usepackage[colorlinks=true, linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black, menucolor=black, runcolor=black, urlcolor=blue]{hyperref}
\title{Good Array 1 - Upsolve}
\author{znzryb}
\date{\today}
\begin{document}
\maketitle
我发现，并不是每道题目都是要去对拍的。\\
不过，其实，我们可以想一下，采用一个这个贪心做法是显然可以的：\\
就是只要这个前缀不是好数组，我们就把这个前缀的最大值加一，改成一个新的数。
\begin{minted}{cpp}
bool check(const vector<ll> &a) {
for (int l = 0; l < SZ(a); ++l) {
for (int r = l; r < SZ(a); ++r) {
map<ll, ll> mp;
for (int i = l; i <= r; ++i) {
mp[a[i]]++;
}
bool ok = false;
for (auto [u,cnt]: mp) {
if (cnt == 1) {
ok = true;
}
}
if (!ok) {
return false;
}
}
}
return true;
}
Solve() {
cin >> N;
A.resize(N);
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
ll cur = *max_element(all(A));
ll ans = 0;
for (int i = 0; i < N; ++i) {
if (!check(vector<ll>(A.begin(), A.begin() + i + 1))) {
++cur;
A[i] = cur;
++ans;
}
}
cout << ans << "\n";
}
\end{minted}
不过这个东西比较慢，\\
\href{https://www.codechef.com/viewsolution/1263049370}{TLE 提交记录} \\
当然，我们可以稍微优化一下我们的这个 \texttt{check} 函数，\textbf{我们不需要每次都从头检查到尾}，我们只需要检查这个前缀的最后一个数就好了。\\
当然，他好像卡了 log，最后一个这个两个点还是过不了。\\
\href{https://www.codechef.com/viewsolution/1263059974}{TLE 提交记录 2}
\begin{minted}{cpp}
bool check(const vector<ll> &a) {
for (int l = 0; l < SZ(a); ++l) {
int r = SZ(a) - 1;
map<ll, ll> mp;
for (int i = l; i <= r; ++i) {
mp[a[i]]++;
}
bool ok = false;
for (auto [u,cnt]: mp) {
if (cnt == 1) {
ok = true;
}
}
if (!ok) {
return false;
}
}
return true;
}
\end{minted}
当然，这个 check 函数还可以继续优化，这个 map 没有必要每次都重建，可以继续进行增量维护。\\
\href{https://www.codechef.com/viewsolution/1263070965}{AC 提交记录}
\begin{minted}{cpp}
bool check(const vector<ll> &a) {
mp.clear();
// 反方向遍历
for (int l = SZ(a) - 1; l >= 0; --l) {
// int r = SZ(a) - 1;
// mp 进行增量维护
mp[a[l]]++;
bool ok = false;
for (auto [u,cnt]: mp) {
if (cnt == 1) {
ok = true;
}
}
if (!ok) {
return false;
}
}
return true;
}
\end{minted}
\end{document}
|