true
Erasing Numbers
2019-2020 ICPC Asia Hong Kong Regional Contest
none
none
题目大意是，给定我们一个序列，我们每次可以选择相邻的三个数，去掉一个最高分，去掉一个最低分，留下三个数中的中位数，操作之后产生的空位会被左右的元素填充。
我们需要对于序列中的每一个数，判断其是否能够在若干次操作之后留下来。
考虑对于每一个数，设其为 $x$，我们将小于其的数字设为 $0$，大于其的数字设为 $1$，可以发现这样是不会对最终结果产生影响的。
那我们考虑我们三消之后会留下什么：
| 原序列 |
剩下的数 |
| 000 |
0 |
| 001 |
0 |
| 010 |
0 |
| 011 |
1 |
| 100 |
0 |
| 101 |
1 |
| 110 |
1 |
| 111 |
1 |
可以发现消除的结果只跟数字的个数有关。
简要总结就是，三个 $0$ 会变成 $0$，三个 $1$ 会变成 $1$，剩下的情况就会消去一对 $0$ 和 $1$。
那么我们执行这个策略，能消除则消除，最后只会剩下如下的几种情况：
- 空
- $0$
- $1$
- $00$
- $11$
然后对两侧分类讨论即可。
时间复杂度 $O(n^2)$，可以通过。
但是实际上实现的时候需要麻烦一点，采用不同的策略。
具体来说，因为成对的 $0$ 和 $1$ 对答案是没有影响的，我们就可以考虑把 $0$ 和 $1$ 的数量消到尽量相同。
我们统计出来较多的那一个数字，忽略成对的 $0$ 和 $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
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5010;
int n;
int a[N], b[N];
bool chq(int x)
{
int les = 0, gre = 0;
if(a[x] == 1 || a[x] == n)return false;
for(int i = 1; i <= n; i++)
{
if(i == x)continue;
if(a[i] > a[x])
{
gre++;
b[i] = 1;
}
else
{
les++;
b[i] = 0;
}
}
int sum = 0, c = 0, del;
if(les < gre)c = 1;
del = abs(les - gre);
for(int i = 1; i < x; i++)
{
if(b[i] == c)sum++;
else sum = max(sum - 1, 0);
if(sum == 3)
sum = 1, del -= 2;
}
sum = 0;
for(int i = x + 1; i <= n; i++)
{
if(b[i] == c)sum++;
else sum = max(sum - 1, 0);
if(sum == 3)
sum = 1, del -= 2;
}
return del <= 0;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = 1; i <= n; i++)
{
if(chq(i))putchar('1');
else putchar('0');
}
putchar('\n');
}
return 0;
}
|