题目传送门

题目大意

令

m

e

x

mex

mex 为序列中最小的没有出现的数。

给你一个长度为

n

n

n 的序列

a

a

a，你可以进行不超过

2

×

n

2\times n

2×n 次操作，使得序列

a

a

a 单调不降。每次操作你可以选定一个位置

p

p

p，并将

a

p

a_p

ap​ 赋值为

m

e

x

mex

mex。请你输出总共的操作次数与每次操作的位置。

解题思路

题目说了，

∀

x

∈

a

,

0

≤

x

≤

n

\forall x \in a,0\le x\leq n

∀x∈a,0≤x≤n。所以，我们考虑将

a

a

a 变为

0

,

1

,

⋯

,

n

−

1

0,1,\cdots,n-1

0,1,⋯,n−1。

我们在进行操作时，需分成两种情况讨论。

若

m

e

x

≠

n

mex \neq n

mex=n，由于最后的序列要满足

a

i

=

i

−

1

a_i=i-1

ai​=i−1，所以我们这里就将

a

m

e

x

+

1

a_{mex+1}

amex+1​ 赋值为

m

e

x

mex

mex。若

m

e

x

=

n

mex = n

mex=n，那我们就找到序列中任意一个满足

a

i

≠

i

−

1

a_i \neq i - 1

ai​=i−1 的数，然后将其赋值为

m

e

x

mex

mex。如果没有找到，说明现在的序列已经满足题意，不需要再进行操作了。

大概思路就是这样。瞟了一眼数据范围，发现

n

n

n 比较小，于是我们在求

m

e

x

mex

mex 的值时可以暴力求解。

CODE：

<code>#include <bits/stdc++.h>

using namespace std;

#define int long long

int a[1010], b[2010], vis[1010];

signed main() { -- -->

ios::sync_with_stdio(false);

cin.tie(0), cout.tie(0);

int t, n;

cin >> t;

while (t--) {

memset(vis, 0, sizeof vis);

cin >> n;

for (int i = 1; i <= n; i++) {

cin >> a[i];

vis[a[i]]++;

}

int ans = 0; //总共的操作次数

/*

最后

a[i] = i - 1

*/

while (1) {

int mex = 0;

for (int i = 0; i <= n; i++) { //查找 mex

if (!vis[i]) {

mex = i;

break;

}

}

if (mex != n) {

vis[a[mex + 1]]--;

b[++ans] = mex + 1;

a[mex + 1] = mex;

vis[mex]++;

} else {

bool f = 0;

for (int i = 1; i <= n; i++) {

if (a[i] != i - 1) {

f = 1;

vis[a[i]]--;

a[i] = mex;

vis[mex]++;

b[++ans] = i;

break;

}

}

if (!f) //序列合法，不需要再进行操作了

break;

}

}

cout << ans << endl;

for (int i = 1; i <= ans; i++)

cout << b[i] << ' ';

cout << endl;

}

return 0;

}

总了个结

这题非常水，建议评绿。简单构造，建议尝试。

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

∈

\tiny\color{white}{\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum\sum_{\sum_{\sum}^{\sum}\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in\in}}

∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑​∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈∈​