本文最后更新于 2024年7月29日 下午
题目传送门
洛谷P9741
翻转与反转
题目分析
数据范围是
，首先想到的是将如题的两个操作——翻转和反转模拟求解，但是会超时，于是有了第二种方法，规律通过每个数下标位置的变化和反转变化可得。
算法一
分析
看了数据范围就是到，的算法肯定会超时，奈何本人太菜，先写一个吧。首先用序列
（样例1） 举个例子
这是题目中所给的样例1的解释，上面的表格中，红色表示的是翻转后的结果，而紫色表示的是反转后的结果。在的时候可以发现第个数进行了翻转与反转，它的下标没有发生变化，在时，第个和第个数进行了翻转，且第个数反转为第个数反转为，时从第个数翻转到第个数，且第个数原本为，反转为，第个数字原本为反转为，第个数原本为反转为，可以分析出规律：从第个数到第个数进行翻转，且翻转同时将原本的数进行取反。
Code
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
| #include <bits/stdc++.h>
#define ll long long int
using namespace std;
const int N((2 * (1e6)) + 1);
bool a[N], b[N];
int main()
{
ll n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], b[i] = a[i];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
if (i % 2 != 0)
a[j] = !(b[i - j + 1]);
else
b[j] = !(a[i - j + 1]);
}
}
if (n % 2 == 0)
for (int i = 1; i <= n; i++)
cout << b[i] << ' ';
else
for (int i = 1; i <= n; i++)
cout << a[i] << ' ';
return 0;
}
|
超时30pts
算法二
因为暴力枚举的算法是过不了的，所以我们需要找规律。首先找翻转的规律，其次找反转的规律。
翻转
首先我们观察样例一，一个长度为的序列，这个序列的下标也就是 它在翻转时的变化如下：
初步发现当为奇数时，下标为奇数的跑到了前面，偶数的跑到了后面，自行举几个例子也是如此。
接着观察样例二，因为样例2有点长，我们用也为偶数的序列研究。当序列长度为时，序列下标为 它在翻转时的变化如下：
发现当为偶数时，下标为偶数的跑的了前面，奇数的跑的了后面，自行举几个例子也是如此。
整理发现，当为偶数时，如果为偶数时会在前项，并且越大越靠前。当为奇数时会在后项，且越大越靠后
当为奇数时，如果为偶数时会在后项，并且越大越靠后。当为奇数时会出现在前项，且越大越靠前。
也就是说第个数最后的落脚点与和的奇偶性，长度都有关系。
整理可得：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| if (n % 2 == 0)
{
for (int i = 1; i <= n; i++)
{
if (i % 2 == 0)
b[(n / 2) - (i / 2) + 1] = a[i];
else
b[(n / 2) + (i / 2) + 1] = a[i];
}
}
else
{
for (int i = 1; i <= n; i++)
{
if (i % 2 == 0)
b[(n / 2) + (i / 2) + 1] = a[i];
else
b[(n / 2) - (i / 2) + 1] = a[i];
}
}
|
反转
反转我们可以发现：当为偶数时，前项需要取反，后面的不变；当为偶数时，前项需要取反，后面的不必。
可得代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| for (int i = 1; i <= n; i++)
{
if (n % 2 == 0)
{
if (i <= n / 2)
cout << !b[i] << ' ';
else
cout << b[i] << ' ';
}
else
{
if (i <= n / 2 + 1)
cout << !b[i] << ' ';
else
cout << b[i] << ' ';
}
}
|
代码
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
| #include <bits/stdc++.h>
#define ll long long int
using namespace std;
const int N((2 * (1e6)) + 1);
int a[N], b[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
if (n % 2 == 0)
{
for (int i = 1; i <= n; i++)
{
if (i % 2 == 0)
b[(n / 2) - (i / 2) + 1] = a[i];
else
b[(n / 2) + (i / 2) + 1] = a[i];
}
}
else
{
for (int i = 1; i <= n; i++)
{
if (i % 2 == 0)
b[(n / 2) + (i / 2) + 1] = a[i];
else
b[(n / 2) - (i / 2) + 1] = a[i];
}
}
for (int i = 1; i <= n; i++)
{
if (n % 2 == 0)
{
if (i <= n / 2)
cout << !b[i] << ' ';
else
cout << b[i] << ' ';
}
else
{
if (i <= n / 2 + 1)
cout << !b[i] << ' ';
else
cout << b[i] << ' ';
}
}
return 0;
}
|
AC记录