洛谷P9741 翻转与反转 题解

2023 年 10 月 27 日

凡 1284 言，一盏茶可读

题解

题目传送门

洛谷P9741 翻转与反转

题目分析

数据范围是1≤n≤2×1061\le n \le 2\times 10^6 ，首先想到的是将如题的两个操作——翻转和反转模拟求解，但是会超时，于是有了第二种方法，规律通过每个数下标位置的变化和反转变化可得。

算法一

分析

看了数据范围就是到，O(n2)O(n^2)的算法肯定会超时，奈何本人太菜，先写一个吧。首先用序列 [1,1,1][1,1,1]（样例1） 举个例子

操作次数序列aa的变化
1[1,1,1]→[1,1,1]→[0,1,1][1,1,1]→{\color{red} [1,1,1]} →{\color{purple} [0,1,1]}
2[0,1,1]→[1,0,1]→[0,1,1][0,1,1]→{\color{red} [1,0,1]} →{\color{purple} [0,1,1]}
3[0,1,1]→[1,1,0]→[0,0,1][0,1,1]→{\color{red} [1,1,0]} →{\color{purple} [0,0,1]}

这是题目中所给的样例1的解释，上面的表格中，红色表示的是翻转后的结果，而紫色表示的是反转后的结果。在i=1i=1的时候可以发现第11个数进行了翻转与反转，它的下标没有发生变化，在i=2i=2时，第11个和第22个数进行了翻转，且第22个数反转为11第11个数反转为00，i=3i=3时从第33个数翻转到第11个数，且第33个数原本为11，反转为00，第22个数字原本为11反转为00，第11个数原本为00反转为11，可以分析出规律：从第ii个数到第11个数进行翻转，且翻转同时将原本的数进行取反。

Code

#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++)
        {
            //从从第i个数到第1个数进行翻转，且翻转同时将原本的数进行取反。
            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

算法二

因为暴力枚举的算法是过不了的，所以我们需要找规律。首先找翻转的规律，其次找反转的规律。

翻转

首先我们观察样例一，一个长度为33的序列，这个序列的下标也就是 [1,2,3][1,2,3] 它在翻转时的变化如下：

[1,2,3]→[1,2,3]→[2,1,3]→[3,1,2]{\large [1,2,3]\to {\color{blue} [1,2,3]}\to {\color{green} [2,1,3]}\to {\color{orange}[3,1,2]} }

初步发现当nn为奇数时，下标为奇数的跑到了前面，偶数的跑到了后面，自行举几个例子也是如此。

接着观察样例二，因为样例2有点长，我们用nn也为偶数的序列研究。当序列长度为nn时，序列下标为 [1,2,3,4][1,2,3,4] 它在翻转时的变化如下：

[1,2,3,4]→[1,2,3,4]→[2,1,3,4]→[3,1,2,4]→[4,2,1,3]{\large [1,2,3,4]\to {\color{blue}[1,2,3,4]}\to{\color{green}[2,1,3,4]}\to{\color{orange}[3,1,2,4]}\to{\color{red}[4,2,1,3]}}

发现当nn为偶数时，下标为偶数的跑的了前面，奇数的跑的了后面，自行举几个例子也是如此。

整理发现，当nn为偶数时，如果ii为偶数时会在前n/2n/2项，并且ii越大越靠前。当ii为奇数时会在后n/2n/2项，且ii越大越靠后

当nn为奇数时，如果ii为偶数时会在后n/2n/2项，并且ii越大越靠后。当ii为奇数时会出现在前n/2+1n/2+1项，且ii越大越靠前。

也就是说第ii个数最后的落脚点与nn和ii的奇偶性，长度都有关系。

整理可得：

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];
       }
 }

反转

反转我们可以发现：当nn为偶数时，前n/2n/2项需要取反，后面的不变；当nn为奇数时，前n/2+1n/2+1项需要取反，后面的不必。

可得代码：

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] << ' ';
    }
 }

代码

#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记录

二〇二三年十月xuesj谨识
洛谷P9741 翻转与反转 题解
https://blog.xuesj.top/blog/luogu-p9741/
作者
xuesj
发布时间
2023 年 10 月 27 日
许可协议
CC BY-NC-SA 4.0
目录

输入关键词开始搜索